Editorial for DMOPC '21 Contest 10 P2 - Cycle Sort
Submitting an official solution before solving the problem yourself is a bannable offence.
If there were no swaps allowed, what would be the optimal strategy?
Can you brute force all swaps?
Brute force all possible swaps. For each resulting array, it is optimal to move the to the front. Compare all the arrays together, and pick the smallest. Note that
< is defined between vectors in C++.
If rotating was not allowed, what would be the optimal strategy?
Try all possible rotations. For a given rotation, find the first item not in place, and swap it into place. For instance, for the sample, the optimal rotation is
5 2 4 3 1 6, and the first number out of place is , since it is in position , so we swap it.
If is after in the input, what should we do? What if it isn't?
In the first case, find the first incorrect number and fix it with a swap.
In the second, try to make
1 2 with one swap.
Obviously we can move the before the or the after the . The last case is that if is after , we can swap them.
If and are in order, find the first incorrect number and fix it with a swap.
If and are not in order, try all possible ways of getting them in order, and pick the lexicographically smallest option. Casework can avoid some overhead of this solution, but it's not required to pass.