AtCoder Grand Contest 032 Announcement

6 years ago, # ^ |

Clearly you don't know anything about hacking. For example, here are instructions for hacking an ATM:

get a car, a laptop and a pickaxe
drive to the ATM
break it open with the pickaxe
load the money to the car and get away

In case you're asking what the laptop is for: what sort of hacker doesn't have one?

→ Reply

a_journey

6 years ago, # ^ |

-15

what u said , i didnt understood . so , anyone can hack anyone's password ?

→ Reply

6 years ago, # ^ |

Phishing, lists of leaked passwords, guessing, etc.

→ Reply

a_journey

6 years ago, # ^ |

← Rev. 2 →

-28

yes , i also did hacking beginners course , i am not an expert or not ever near to it , but phishing only happens when u urself submit ur paswword to some fake sites . they save ur password .

regarding guessing , brute force will take years , if ur password is strong , and https is much secure . thats why i am surprised as the same guy hacked dotorya yesterday at edu. round , now today .

→ Reply

6 years ago, # ^ |

only happens when u urself submit ur paswword to some fake sites
if ur password is strong

You might as well expect that if you tried competing here in rating contests you'd no doubt crush tourist.

→ Reply

amnesiac_dusk

6 years ago, # ^ |

Maybe that hacker hacked passwords from CodeForces and users had same passwords in AtCoder or vice-versa.

→ Reply

6 years ago, # ^ |

How exactly does that happen? How can an attacker who gains access to CodeForces' databases actually get users' passwords? Aren't these things usually hashed before they are stored?

Sorry if it's a dumb question, I don't know too much about computer security.

→ Reply

dalex

6 years ago, # ^ |

He got a database of leaked passwords.

→ Reply

6 years ago, # ^ |

← Rev. 3 →

-18

Right, but I guess the question I'm asking is: Why does there even exist a database of unhashed user passwords? What would be the origin of this database?

Edit: I'm probably not explaining myself well, based on the response. To my understanding, a website like Google does not actually store anything like "Kognition — 'password' " in their database, but instead will have something like "Kognition — 3f930a9bc27d", corresponding to the hash of my password, which presumably gets hashed client-side. So, my actual password should never be stored anywhere on their servers. Is this understanding correct? If not, what is the misunderstanding? If so, then why exactly is there a database of unhashed Codeforces passwords?

→ Reply

T1duS

6 years ago, # |

How to solve C and D?

→ Reply

6 years ago, # ^ |

D: one can see that rotation left is just moving a single element to the right and vice versa. All untouched elements must represent an increasing subsequence. Now we can calculate dp[i][j] which stands for the minimal cost of rearranging all elements which are initially at the first $$$i$$$ positions in such a way that the rightmost untouched element among them is the $$$j$$$-th.

C: I did the following: remove all vertices with degree $$$2$$$ one by one, ignoring loops, then see if num_loops + remaining_edges / 2 is at least $$$3$$$. Maybe I did something else, I don't remember, my brain has decided to forget this solution.

→ Reply

6 years ago, # ^ |

Wait, quadratic time complexity was enough in D? I knew that the problem asking for the min. number of elements to move is $$$O(N\log)$$$, so I didn't check the constraints at all and just solved it in $$$O(N\log)$$$.

→ Reply

6 years ago, # ^ |

Can you tell that solution or share some resources?

→ Reply

6 years ago, # ^ |

See my solution. I'm just using an interval tree with operations "get minimum of range", "put a fixed value at some position" and "increment all values in a range by x".

→ Reply

Zain

6 years ago, # ^ |

Do you know why this doesn't work for D:

dp[i][j] is the cost to complete the sorting if you know that there are first (1, 2, .... i) brought to the very beginning in sorted way and numbers (j, j+1, .., n) are brought to the very end in sorted way. dp transitions are either bring the number i+1 to left ( with cost A if it is not already in the left) + dp[i+1][j] or bring the number j-1 to the right (with cost B if it is not already in the right) + dp[i][j-1]???

my code

→ Reply

6 years ago, # ^ |

As far as I remember, the last sample test is a counter-test to this solution

→ Reply

krijgertje

6 years ago, # ^ |

Try the following test case:

6 1 1
3 1 2 5 6 4

→ Reply

kilotaras

6 years ago, # ^ |

Notice that circuits combined have to be an Euler cycle. Check for that. Now we know that all vertices have even powers.

If there's a vertex with power 6+. Answer is yes.
Else if there're at least 3 vertices with power 4, answer is yes.
Else if there's only one vertice with power=4, answer is no.

Else we have two vertices with power=4 and every other vertex has power=2. Collapse those and we have one of two cases.

1 2, 1 2, 1 2, 1 2,. Answer is no
1 1, 1 2, 1 2, 2 2. Answer is yes.

Note that you don't have to collapse graph explicitly. It's enough to try walking from one of the power 4 vertices and see if we can loop back without hitting other.

→ Reply

6 years ago, # ^ |

Could you please explain why the graph must be eulerian ?

Statement says "Determine if three circuits (see Notes) can be formed using each of the edges exactly once."

What if we take a correct graph G, and add a new vertex connected with a random vertex from G. Now the new G' is not eulerian because the new vertex has degree 1, but it still has three circuits.

What I am missing ?

→ Reply

kilotaras

6 years ago, # ^ |

← Rev. 2 →

Determine if three circuits (see Notes)

Notes

A circuit is a cycle allowing repetitions of vertices but not edges.

Take a look at 1st cycle. As graph is connected it has a shared vertex with some other cycle. We can merge them. Repeat and receive eulerian cycle.

→ Reply

6 years ago, # ^ |

Yea, also I think the key here is that it forces us to take every edge exactly once. With that constrain, probably the new edge (in my example) is never used by any circuit and this is probably the reason that the graph must be eulerian.

I think I got it, thank you.

→ Reply

6 years ago, # ^ |

using each of the edges exactly once

→ Reply

https://codeforces.me/gym/102059/problem/E

6 years ago, # ^ |

Yea, exactly. Thank you !

→ Reply

EnumerativeCombinatorics

6 years ago, # |

+36

AGC is a puzzle contest only for genius, not a programming contest.

... by the way, can you send me a problem list containing a lot of problems about determining whether it's possible to make something from a graph (by looking at degrees or something)? I always have no idea to solve them.

→ Reply

dalex

6 years ago, # ^ |

You may like problem J from here: https://codeforces.me/gym/101341

But it is not very hard, Div 1 B/C I'd say.

→ Reply

chinesecoder

6 years ago, # ^ |

-103

lol , what type of red coder u r ,are u cheater

→ Reply

EnumerativeCombinatorics

6 years ago, # ^ |

+27

No. You are.

→ Reply

ko_osaga

6 years ago, # ^ |

+10

https://codeforces.me/contest/730/problem/K

→ Reply

6 years ago, # ^ |

Lol, I hope you were not serious and wrote this just to trigger me and some other users.

→ Reply

EnumerativeCombinatorics

6 years ago, # ^ |

rng_58 just told me that AtCoder is just about mathematics puzzle ability from red (where ARC becomes unrated)

→ Reply

Clone3

6 years ago, # |

← Rev. 2 →

+18

How to solve A, lol...

I squeezed (2ms running time tho) backtracking but couldn't come up with a solution.

→ Reply

6 years ago, # ^ |

I did the reverse operation. You start from the moment N and greedily remove the largest element where b[i] == i. This is optimal, because size of array will decrease so its always preferable to remove the largest possible element you can.

→ Reply

atlasworld

6 years ago, # ^ |

-37

you cant solve a , its quite surprised , almost a red coder u r

→ Reply

Clone3

6 years ago, # ^ |

That's what fascinates me most about atcoder contests. In many cases problems aren't easily observable, yet contests are really interesting.

→ Reply

voover

6 years ago, # ^ |

Observation

Solution

→ Reply

6 years ago, # |

-10

Quite disappointed with my performance here, I spent about half of the contest on B until I saw the pattern and got an unnecessary WA on C — not because I missed a case, but because I had a small bug and didn't customtest that one case where it appeared.

Still, D with costs A and B instead of 1 and 1 is well-known (sort by moving elements) and this version isn't much harder — I solved it in about 5 minutes, complete with copypasting an interval tree and making small changes.

→ Reply

Errichto

6 years ago, # |

Nice problems, as always.

I think F is hard already for $$$n \le 8$$$. I wanted to solve it with dp similar to tourist's atcoder problem about arcs and then run Berlekamp–Massey. I didn't finish in time and wasn't even close. But would that work?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

That seems like a really wishful thinking to me. Why would such a sequence form a linear recursion?

→ Reply

Errichto

6 years ago, # ^ |

← Rev. 2 →

When something is a fraction, numerator and denominator are often some complicated polynomials. But I understand it can also be something of magnitude $$$n!$$$ easily. Then BM doesn't work.

→ Reply

6 years ago, # |

+29

Wow, you've used the same colors in the editorial of E as I did while solving this!

photo

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Editorial says that, we can rearrange the left pairing and get the right one without increasing the larger ugliness of those two pairs.

Now, suppose the larger ugliness is formed by the red pairing then its ugliness is (if we denote the four numbers by $$$w, x, y, z$$$ so that $$$w \le x \le y \le z$$$ and $$$w$$$ pairs with $$$y$$$, $$$x$$$ pairs with $$$z$$$) $$$x + z - M$$$ (in the left pairing). Then when we reassign the pairing as shown in the right one, the ugliness of the blue pairing does not increase like the red one's does not decrease; also now the larger ugliness is formed by the red pairing, it also remains a "red" pairing since $$$M \le x + z \le y + z$$$. On the contrary, the larger ugliness might have increased (since it's less than or equal), the red one's. So, everything is contradicting with each other unless I am missing something (Undeniably, I am). Can you please tell me, what am I missing :(?

→ Reply

dotorya

6 years ago, # ^ |

← Rev. 2 →

+10

the red pairing of the right side has smaller ugliness than the blue pairing of the left side, so the right one always have smaller or equal ugliness than the left one.

UPD: Not blue side, left side.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

What do you mean by blue side?

→ Reply

dotorya

6 years ago, # ^ |

Left side, sorry.

→ Reply

ainta

6 years ago, # |

Editorial of problem F said that "A simple calculation shows that when we divide a segment into $$$k$$$ parts at random, the expected length of the shortest part is $$$\frac{1}{k^2}$$$ times the length of the original segment.

But I feel I'm not good at simple calculation.. how to prove it?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

+25

Wlog assume that the initial segment is $$$1$$$ unit length. The probability that all parts are greater than or equal to $$$s$$$ is $$$(1 - ks)^{k-1}$$$ (since we kinda divide a segment of length $$$1 - ks$$$ and then expand each part by $$$s$$$). Thus the expectation is

$$$\displaystyle \mathsf{E}\int_0^1I(len\ge s)\,ds = \int_0^1\mathsf{P}(len\ge s)\,ds = \int_0^{1/k}(1 - ks)^{k-1}\,ds = \frac{1}{k}\int_0^{1}(1 - x)^{k-1}\,dx = \frac{1}{k^2}$$$

qed.

→ Reply

ksun48

6 years ago, # ^ |

+20

Here's a weird combinatorial argument, not sure if it's correct.

Consider $$$k-1$$$ random numbers in $$$[0,1]$$$, and say they are $$$x_1, \dots, x_{k-1}$$$ after sorted. Let $$$x_0 = 0$$$ and $$$x_k = 1$$$. Additionally, pick a random number $$$y$$$ in $$$[0,1]$$$. The expected value of the minimum segment length is equivalent to the probability that $$$y \le x_{i+1} - x_i$$$ for all $$$i$$$.

First, we must have $$$y \le x_i$$$ for all $$$i$$$, which happens with probability $$$\frac{1}{k}$$$.

After this, we can look at the numbers $$$y - x_0, x_1 - y, x_2 - x_1, \dots, x_k - x_{k-1}$$$. Given that $$$y \le x_i$$$ for all $$$i$$$, the distribution on these values is the same distribution as splitting a segment of length $$$1$$$ into $$$k+1$$$ parts. In order for $$$y$$$ to be at most $$$x_{i+1} - x_i$$$ for each $$$i$$$, $$$y$$$ must be the minimum of the elements $$$y, x_2 - x_1, \dots, x_k - x_{k-1}$$$, which happens with probability $$$\frac{1}{k}$$$. (We already know that $$$y \le x_1 - x_0 = x_1$$$.)

Now we can multiply these probabilities together to get $$$\frac{1}{k^2}$$$.

→ Reply

6 years ago, # ^ |

Wow, that's great, I've never seen combinatorial argument for that

→ Reply

6 years ago, # ^ |

← Rev. 2 →

"The expected value of the minimum segment length is equivalent to the probability that $$$y \leq x_{i+1} - x_i$$$ for all $$$i$$$."

Why exactly is this true? It sort of makes sense to me intuitively, but it's the only part of the argument I'm having trouble justifying myself.

→ Reply

6 years ago, # ^ |

I remember that one Petrozavodsk problem asked basically that what is that value for a particular k and many people, including me, just did a Monte Carlo for k=3,4,5 and formula became obvious :p

→ Reply

majk

6 years ago, # |

+53

I don't know why people complain about slow convergence of AtCoder rating. Not only my AtCoder rating converges, it converges towards my Codeforces rating!

→ Reply

cwy

6 years ago, # |

Testcases for C is not strong.

During the contest,I came up with a wrong solution:

Consider graphs that only contains vertices of degree 4 or 2.I find an Eulerian circle and check if there exists something like A...A...B...B in the circle.

In fact,it can be easily hacked.

Input:

It should be Yes,but my submission output No.

My submission

→ Reply

6 years ago, # ^ |

I guess it's because there's a lot of cases and there aren't enough tests for some case to break every solution that only fails this case; also because the answers are just yes/no (I really don't like yes/no outputs). So far, I've noticed that Atcoder doesn't go for really crazy strong tests where a wrong solution probably fails 40 of them, but adds a few tests that break specific wrong ideas that shouldn't pass. It's possible to get lucky, but it's usually not worth the time.

→ Reply

rng_58

6 years ago, # ^ |

Generally speaking, it's impossible to come up with all wrong solutions in advance. Your case can be handled by just counting the number of vertices of degree 4 anyway, so your solution doesn't look very natural.

→ Reply

6 years ago, # ^ |

Well, sure, as long as what really shouldn't pass doesn't pass.

→ Reply

camypaper

6 years ago, # ^ |

In my impression, your solution depends on edge order.

This sort of wrong solution is tough to defend. What's happen if you try to shuffle edge order and find eulerian circuit as long as time allows?

see this https://atcoder.jp/contests/agc032/submissions/4672371

→ Reply

Petr

6 years ago, # ^ |

Note that the "outer2" loop is a leftover from an unsuccessful attempt to apply this shuffling approach :)

In this solution this loop is executed exactly once, and the solution is basically the same as the editorial.

→ Reply

camypaper

6 years ago, # ^ |

I'm terrible at code reading :( I saw that you try to shuffling approach, so I thought you passed with this approach...

→ Reply

bakooora

6 years ago, # |

how to solve first problem ?

→ Reply

xiaoshizhan

6 years ago, # |

For problem D — Rotation Sort, I checked some AC codes, and I found codes similar to the code below. But I don't understand, could anyone help me understand the code plz.

fill(dp+1,dp+n+1,INF);
dp[0]=0;
for(ll i=1;i<=n;i++)
{
    ll cntx=0,cnty=0;
    for(ll j=i-1;j>=0;j--)        
    {
        if(p[j]<p[i]) dp[i]=min(dp[i],dp[j]+cntx*b+cnty*a);
        if(p[j]<p[i]) cntx++; else cnty++;
    }
}

→ Reply

6 years ago, # |

In problem C, I counted how many times a visited vertex gets visited again while running the Euler cycle making algorithm (I guess it's called Hierholzer's algorithm). And if the count is greater than or equal to 3 then output yes, no otherwise. This should be correct, but it's giving wrong answer. Can anyone tell me where am I wrong?

→ Reply