Editorial for COCI '16 Contest 6 #3 Turnir

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

First, we need to notice that the only relevant information for each number X is the number of numbers larger than it. This is relevant because only the larger numbers will continue to the next level, and all the other numbers will accompany the current number X to the top. This information is easily obtained by sorting the numbers.

Let's try to calculate the highest level X can reach. For the zeroth level, there obviously cannot be a single larger number than X, i.e., the number of numbers larger than it must be 0. In order to reach the first level, there must be at most N/2 numbers larger than it, because otherwise, at least one number larger than X will 'fight' with it, which will result in X not passing to the next level. In the case when there are more than N/2 numbers larger than X, X should be at a level below the first one. Now, in order for X to be at the second level, the number of numbers larger than it must not exceed N/2 + N/4. Why?

It is easy to see that N/2 numbers can be left on the level above at the other side of the tree, then we are left with N/2 numbers with X in there. On the current second level, we make the same decision where we see whether we can leave all larger numbers in the second subtree sized N/4, in order for X to freely rise to the top of its subtree, to level 2. We follow this algorithm, subtracting the descending powers of 2 from the number of numbers larger than X.

The total complexity of the algorithm is \mathcal O(N \log N).


There are no comments at the moment.