Yes. I did it by Topological Sorting. My code is here 50382490

Actually I think Topological Sorting is just implementing the same method given by the editorial.

Please explain the proof of C.

Roll your own linked lists, and create a map from the DSU to the first and last pointer in the list. Then, to join two lists it's just a single pointer change.

You can use std::list and the splice function. For a reference, take a look at this submission: https://mirror.codeforces.com/contest/1131/submission/50373670

You may want to see my comment below.

Every time when we have to merge sets, all of kittens from one set are in one cell. If you have some order for set a and set b, you just have to ensure that this two sets are adjecent, because no matter you place them ab or ba, after i-th operation they will become one component.

Assume that putting a to the right of b is a valid solution

Then we split the sequence into four parts

c — b — a — d

Where c is the subsequence in front of b and d is subsequence behind a

It is fairly obvious that d’ — a — b — c’ is also a valid solution (d' and c' are the reversed sequence for c and d respectively）

So the order doesn’t matter

I did that, but not sure if the way is what you want, since my DFS is used to travel a tree. My Submission is here, notice that array sz[] is not used and was forgotten to remove.

Simple explanation: when we merge 2 sets, we create a new node stands for the whole set and set its two sons to that 2 sets. After all operations it will become a tree because answer always exists. Use DFS to travel this tree, and every time when we meet a leaf node just print it. It's correct because for every merge operation the 2 operands are sons of a new node and that guarantees the 2 part must be neighbors in the final output.

Hope it helps.

Let’s look on stack of increasing values of dp. Then we count the new value, we need to get the minimum element on the segment, that element should be in the stack, we can go from top and search for it. But this solution is O(m**2). Let’s notice that we can erase elements if we find reachable element earlier. So we can keep in stack only optimums. That gives us O(m).

The solution is a constructive one. Sort the sequence, and append all even-indexed elements reversely to the end of the sequence. Correctness proof is given in the editorial.

I'll do my best to describe the proof in more detail:

We have a problem that requires us to find a configuration that minimizes a value. The general approach used (which can sometimes be applied to other problems too) is the following: We prove that that there's a lower bound on how small the answer can be for a given input and then we figure out a configuration that achieves that exact lower bound.

For this task: First, let's consider the numbers ordered such that a[i] ≤ a[i + 1]. We can then prove that the answer can't be better than a_i + 2 - a_i,  for any i = 1,2,3,...,n-2. ( statement 1 )

If we manage to do that, then we can say that a lower bound for the answer is the maximum of all of those, i.e. max(a_i + 2 - a_i), where . The final step would be to see that the solution provided in the editorial gives that exact lower bound ( statement 2 ).

Proof for statement 1: First imagine that you have a complete graph, where the vertices are the given heights and the edges represent the absolute differences between the two endings. In order to give a solution, we must give for every vertex a "before" neighbour and an "after" neighbour, such that we get a cycle going through all nodes exactly once (a hamiltonian cycle). Now let's prove by contradiction that the solution can't be better than a_i + 1 - a_i for a fixed i. Suppose that it is smaller. Since we want the maximum value of an edge to be stricly less than a_i + 1 - a_i, then it means we can't use any edge between a[m] and a[n], where (let this be the first set) and (let this be the second set), since a[n] - a[m] would be greater or equal to a[i + 2] - a[i]. From this, we can see that if we want to start a path from the first set that goes to the second set and then comes back, then we must use a[i + 1] at least twice. Thus, any cycle will contain a[i+1] more than once, so it can't be hamiltonian, so we can't build a correct configuration => contradiction with our initial hypothesis that there exists a solution.

Therefore any solution can't be better than the mentioned lower bound.

Proof for statement 2: I'll just mention the logic for the example solution given in the editorial: a₁, a₃, a₅|a₆, a₄, a₂. We can see that the difference between two heights in the first part or in the second is one of the those that give the lower bound. The other two are the difference in the middle and the one at the end. But we have that a[6] - a[5] < a[6] - a[4] < lowerBound and a[2] - a[1] < a[3] - a[1] < lowerBound. So the maximum of all values is less or equal to the lower bound, but since the lower bound is the lowest value, it means we get exactly that.

Hope it helped.

You haven't initialised sze with 1.

I think the editorial has a typo. The first situation should be domino falls left.

if a_ij equal to "=" then dish i from the first day and dish j from the second day must be equally good, then you will realize that 2 dishes must be on the same group. When you assign all dishes to the group then you can look at '<' and '>'. So if a_ij equal to '<' then the group of dish i from the first day are worse than the group of dish j from the second day so that makes a graph of the group of dishes, Same as '>'. After that use DFS on that graph to find which group are the worst and which one is better and so on.

Here is my solution : link

PS. Sorry about my English.

Try your original code on your local machine by entering the input values instead of copying the test case. It will output a garbage value. Solution: Replace mp(0, 0) by construct assignment pair<int, int>(0, 0). and mp(x, y) with pair<int, int>(x, y).

In the second loop, i goes up to n,

then in this line, y = min(arr[i+1].ff,arr[i+1].ss);

You try to access the element at arr[n+1] which is some garbage value that you did not set.

Try the following test case it gives a wrong sequence 10 10 6 8 10 6 2 8 7 8 4 1 7 8 5 3 10 10 9

Topological sort.