Editorial for DMOPC '18 Contest 1 P5 - Sorting
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
For Subtask 1, we binary search for the best value of . To check if a value of is possible, brute force all pairs of elements to see if they may be swapped. Note that if and can be swapped and and can be swapped, then and can be indirectly swapped. Keeping track of this can be done with a disjoint set, and then it is easy to check if it can be sorted.
Time Complexity:
For Subtask 2, consider the numbers bit by bit. Consider the largest bit in any of the numbers. If contains this bit, then any number less than it may be swapped freely. Also, any number greater or equal to it can also be swapped freely. So we are left with two sets each of whose elements may be swapped freely. However, if contains this largest bit, note that will only be . Also consider the indices and the indices (-indexed). The two sets need to reach these indices to be swapped. But if we have an element in the wrong set of indices, then it can be swapped to the right set of indices at a cost of exactly . This is because can be paired with to yield a swap of cost exactly for (if is not in the set of indices that is trying to get to, then can be swapped into it).
The argument above sounds quite complicated, but it is much simpler than it seems and fairly intuitive after some consideration.
So to find , we only need to find the first bit for which an element is not in the right set of indices. If a bit isn't needed in , it can actually be completely ignored. So each bit can be simply checked in .
Time Complexity:
There is no intended solution for Subtask 3. It was created to reward potentially complex solutions which do not use the observation used for the intended solution to Subtask 4 and may have a suboptimal time complexity.
For Subtask 4, the observations seen in Subtask 2 encourage analyzing (where indices are -indexed). It turns out that is simply the highest bit in for all from to . Then updating this maximum quickly can be easily done.
Time Complexity:
Comments