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: Riolku
Hint 1
If there were no swaps allowed, what would be the optimal strategy?
Hint 2
Can you brute force all swaps?
Subtask 1
Brute force all possible swaps. For each resulting array, it is optimal to move the 
~1~ to the front. Compare all the 
~N^2~ arrays together, and pick the smallest. Note that < is defined between vectors in C++.
Hint
If rotating was not allowed, what would be the optimal strategy?
Subtask 2
Try all 
~N~ 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 
~5~, since it is in position ~1~, so we swap it.
Hint
If 
~2~ is after ~1~ in the input, what should we do? What if it isn't?
Hint 2
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.
Hint 3
Obviously we can move the ~1~ before the ~2~ or the ~2~ after the ~1~. The last case is that if ~1~ is after ~2~, we can swap them.
Full Solution
If ~1~ and ~2~ are in order, find the first incorrect number and fix it with a swap.
If ~1~ and ~2~ 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.
Comments