AtCoder Grand Contest 032 will be held on Saturday (time). The writers are sugim48 and camypaper.

This is the second GP30-rated contest in this season — see this post for details.

Contest duration: 110 minutes

The point values will be announced later.

Let's discuss problems after the contest.

Why is it one hour later than usual?

There's some local contest before that.

rng_58

Please prepone the contest by 20 mins since the last 20 minutes are clashing with the first match of the Indian Premier League (CSK vs RCB) which means most cricket lovers will not be able to do the contest.

Thanks in advance for your kind co-operation.

I have a solution. Go with whatever comes first in your priority queue.

Who is Makki0? I guess (99% sure) that he is a password-hacking cheater, because I've encountered similar username 0ahmad0makki0 hacking strong-player account in codeforces contests.

Refer to the comment of 300iq

but how its possible, codeforces and atcoder both use https security , its not easy to hack paswsword

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

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

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

Phishing, lists of leaked passwords, guessing, etc.

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 .

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

lol . xd what u mean

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

yaa , u may be right .

How exactly does that happen? How can an attacker who gains access to CodeForces' databases actually

getusers' 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.

He got a database of leaked passwords.

Right, but I guess the question I'm asking is: Why does there even

exista 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?

How to solve C and D?

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.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)$$$.

Can you tell that solution or share some resources?

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".

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

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

Try the following test case:

C.

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

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.

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 ?

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.

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.

Yea, exactly. Thank you !

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.

but tourist and ksun solved them including petr

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

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

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

No.

Youare.first , recover your lost mental balance after today's contest .

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

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

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

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

lol , who r u , that rng_58 will call you and tell you.

How to solve A, lol...

I

squeezed(2ms running time tho) backtracking but couldn't come up with a solution.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.

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

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

solutions are too short also . upto d

ObservationIf, for any

`i`

,`b[i] > i`

, it's not possible (`b[i]`

would have to be inserted at position`b[i]`

and then travel left, which is not possible).SolutionLet's say that in the last step we inserted

`b[i]`

. First of all,`b[i] == i`

. Also, if we also had`b[j] == j, j > i`

, then in the second-to-last step we'd have`b[j-1] == j`

which is contradictory with the observation above. So, in the last step we had to usethe last`i`

such that`b[i] == i`

. Now recurse.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.

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?

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

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.

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

photoEditorial 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 :(?

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.

What do you mean by blue side?

Left side, sorry.

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?

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

qed.

how can one ccome with such maths , many dont know formula . why atcoder contest so inclined on maths side . its like International maths olympiad

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}$$$.

ABRB , what u have written , from where do u learn these things , so hard combinatorics .

u r very brilliant in maths .

https://www.imo-official.org/participant_r.aspx?id=23293

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

"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 ofmakes sense to me intuitively, but it's the only part of the argument I'm having trouble justifying myself.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

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!

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

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.

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.

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

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

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.

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

how to solve first problem ?

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.

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?

Consider the case where you have two nodes of degree 4 (we'll call them $$$A$$$ and $$$B$$$), and all other nodes of degree 2.

There are basically two types of graphs that can be a result of this: one where $$$A$$$ has it's own circuit, $$$B$$$ has it's own circuit, and there is a third circuit containing both $$$A$$$ and $$$B$$$. The other kind of graph has two disjoint circuits, both containing $$$A$$$ and $$$B$$$. The Euler tour will visit $$$A$$$ and $$$B$$$ the same number of times (note that the number of times a vertex gets revisited is just it's degree minus one), but the answers differ in both of these graphs.