There's some local contest before that.

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

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

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.

C.

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.

You may like problem J from here: https://codeforces.net/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

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

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

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

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 seems like a really wishful thinking to me. Why would such a sequence form a linear recursion?

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

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.

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

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

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

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.