Editorial for DMOPC '18 Contest 1 P5 - Sorting

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.

Author: r3mark

For Subtask 1, we binary search for the best value of $C$ ~C~. To check if a value of $C$ ~C~ is possible, brute force all pairs of elements to see if they may be swapped. Note that if $X$ ~X~ and $Z$ ~Z~ can be swapped and $Y$ ~Y~ and $Z$ ~Z~ can be swapped, then $X$ ~X~ and $Y$ ~Y~ 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: $\mathcal O(QN^2 \log N)$ ~\mathcal O(QN^2 \log N)~

For Subtask 2, consider the numbers bit by bit. Consider the largest bit $b$ ~b~ in any of the numbers. If $C$ ~C~ 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 $C$ ~C~ contains this largest bit, note that $C$ ~C~ will only be $2^b$ ~2^b~. Also consider the indices $\ge 2^b$ ~\ge 2^b~ and the indices $<2^b$ ~<2^b~ ( $0$ ~0~-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 $2^b$ ~2^b~. This is because $2^b+x$ ~2^b+x~ can be paired with $x$ ~x~ to yield a swap of cost exactly $2^b$ ~2^b~ for $x<2^b$ ~x<2^b~ (if $x$ ~x~ is not in the set of indices that $2^b+x$ ~2^b+x~ is trying to get to, then $x$ ~x~ 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 $C$ ~C~, 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 $C$ ~C~, it can actually be completely ignored. So each bit can be simply checked in $\mathcal O(N)$ ~\mathcal O(N)~.

Time Complexity: $\mathcal O(QN \log N)$ ~\mathcal O(QN \log N)~

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 $i \oplus P_i$ ~i \oplus P_i~ (where indices are $0$ ~0~-indexed). It turns out that $C$ ~C~ is simply the highest bit in $i \oplus P_i$ ~i \oplus P_i~ for all $i$ ~i~ from $0$ ~0~ to $N-1$ ~N-1~. Then updating this maximum quickly can be easily done.

Time Complexity: $\mathcal O((N+Q) \log N)$ ~\mathcal O((N+Q) \log N)~

Comments

There are no comments at the moment.