Interesting. You constructed the array s,right?

can u explain your approach ? I have tried this question in building the array just like you

I noticed the thing that if we take a given node "X" ,then nodes in the longest path from root to a leaf in a subtree where "X" is root can be made to same value.

so I came up with approach something like this For Each level, For Each node in that level lets say Y, I added up the length of longest path from the node Y to the leaf

After getting answer for all levels, I took the max of them but i am missing something.

Gale–Ryser theorem

Well, the first thing that helps for this problem is to consider that all multisets have the same size, which is $$$n$$$. Simply, add additional zeros representing empty sets until you have $$$n$$$ numbers in the multiset.

One possible way in which we realize that such a condition is equivalent and can prove it is to note the following: If we are able to createe a multiset $$$(M_i)_{i \in [0, n)}$$$ we can always move elements from a bigger set $$$M_i$$$ to a smaller one $$$M_j < M_i$$$ and still maintain a valid configuration. The reason is that in $$$M_i$$$ there are at most $$$M_j$$$ elements that are already in $$$M_j$$$, so the rest, $$$M_i - M_j$$$ can be moved to $$$M_i$$$ if it is necessary.

This implies that if we consider the multisets sorted, which is what makes more sense, we can always move elements from $$$M_i$$$ to $$$M_{i+1}$$$. Thus, if a configuration $$$(M_i)_{i \in [0, n)}$$$ is valid, so is any configuration $$$(N_i)_{i \in [0, n)}$$$ with $$$\sum_{j = 0}^i N_j \le \sum_{j = 0}^i M_j$$$. And this is the key to the problem. We do not need to consider all multisets, only those that are maximal in this sense. And then we can count how many elements they have below them.

By the way, once we get that formula, it makes no sense to keep considering the multisets in the way we are doing it. Instead, use the sequence of accumulated sums to represent the multiset. Then the condition becomes $$$N_i \le M_i$$$ for all $$$i$$$, which reads much better. Hence, our multisets are represented as increasing sequences $$$(M_i)_{i \in [0, n)}$$$ with decreasing $$$M_{i+1} - M_i$$$. Or even better, as increasing sequences $$$(M_i)_{i \in [0, n]}$$$ wiith $$$M_0 = 0$$$, $$$M_n = n$$$ and decreasing $$$M_{i+1} - M_i$$$.

The question is, which multisets are maximal? Two multisets are not comparable if $$$N_i \le M_i$$$ and $$$N_j \le M_j$$$ for some indices $$$i$$$ and $$$j$$$. But... well, this was of little help for me. So, I thought: at the very least I know that the biggest lexicographically is maximal. Which $$$(K_i)_{i \in [0, n]}$$$ is the biggest lexicographically? Well, if we try to fit as many possible numbers in the first set, we will have $$$K_1 = \sum_{j = 0}^n min(\operatorname{cnt}_j, 1)$$$. Then, we will substract $$$1$$$ from every $$$\operatorname{cnt}$$$ and repeat. In the end, we get the multiset $$$K_i = \sum_{j = 0}^n \min(\operatorname{cnt}_j, i)$$$. (And the right hand side is precisely the formula of the statement. This, along with our previous observation, proves that the condition is sufficient.)

However, now that I know the formula I also know that we cannot make another maximal multiset, because for $$$M_i$$$ we can only use at most $$$\min(\operatorname{cnt}_j, i)$$$ occurences of each number $$$j$$$. That means $$$N_i \le \sum_{j = 0}^n$$$ for all multisets $$$(N_i)_{i \in [0,n)}$$$. Thus, the lexicographically biggest multiset is, actually, the only maximal.

Ending note: Yes, we can prove necessity from the very beginning and sufficiency if we consider the lexicographically biggest multiset and the first observation, without any notion of maximal elements. However, I am not sure one would get there magically. Instead, I believe the first observation must lead us to think of maximal elements and then we can either guess that there is just one or simply deduce it as it has been shown.

You can conclude and prove this lemma with mincut maxflow — if you try to find a maximum matching between a chosen multiset of sizes, and the frequencies of the elements, then try to find the condition by which all cuts are of size at least $$$n$$$.

It's pretty lengthy (I can elaborate if you want), but you can arrive at this condition without magically guessing it (the magic here comes from the magic of MCMF).

$$$>$$$ or $$$\geq$$$ ?

Take a look at Ticket 16402 from CF Stress for a counter example.

Now edited to make it clearer.

you can consider a stick tree. where 1->2->3->4 here it always makes sense to select a root node as we can never get the better answer by excluding the root.

Agreed. Now, some of the editorials have been edited to give more explanations about the claims and conclusions. I hope they are more helpful now <3

It is fixed now. Thanks for pointing it out! <3

Yea, my solution also runs in O(n). However, I think the priority queue solution is more intuitive to explain and understand. Thanks for mentioning that!

You can't but you don't need too. Cards only move if they are the current next card going to the exit or as part of a rotation to let another card past (so you'd never need to move from one 2x2 square into the other). As long as there is an empty square any card can reach the exit which is all that matters.

Nice catch! We actually did not realise the possibility of that. The tutorial has been edited to have a more correct claim.

Q: What is the maximum difference you can get?
A: $$$max(a)-min(a)$$$

Let's call this difference $$$maxdiff$$$. You can get $$$maxdiff$$$ for $$$|w_1-w_2|$$$ by placing all elements with value $$$max(a)$$$ in one of the first two slots, then placing all elements with value $$$min(a)$$$ in the other. Now iterate through the array and find the minimum value of $$$|max(a)-a_i|$$$. Let's call this value $$$x$$$. Now iterate through the array and find the minimum value of $$$|min(a)-a_i|$$$. Let's call this value $$$y$$$. The answer is then $$$maxdiff+max(x,y)$$$.

Why? For the second difference ($$$|w2-w3|$$$), to achieve $$$x$$$, you can place all elements with value $$$max(a)$$$ in the second slot, all elements with value $$$min(a)$$$ in the first slot, and the rest of the array elements in the third slot. To achieve $$$y$$$, just interchange the elements in the first two slots.

Edit: there is one case that is not handled — if after selecting the elements for the first two slots, there are no more elements left for the third slot. In this case, for the third slot, we select one of the elements in either the first or second slot, whichever maximizes the second difference. The answer in this case is $$$maxdiff × 2$$$.

In fact, this solution works in $$$O(n)$$$ but the one in the editorial is probably faster in practice.

Yes, it can be done in $$$O(nm)$$$.

6 1 2 2 2 2

Take a look at Ticket 16435 from CF Stress for a counter example.