## Editorial for DMOPC '18 Contest 1 P3 - 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: george_chen

For the first subtask, any standard sorting algorithm is enough to score full points.

Number of operations: or For the second subtask, observe that the permutation can be modelled as a graph. Build an "edge" from each element to . After this is done, the permutation can be modelled as a set of disjoint cycles. Each shift operation performs a cyclic shift on some cycle so it takes exactly operation to sort a cycle. Because we only need to perform a shift operation on cycles of size greater than , there are at most such cycles. This is enough to score full points for the second subtask.

Number of operations: For the final subtask, observe that the answer is always , , or .

If the permutation is initially sorted, the number of operations needed is .

If the permutation consists of exactly cycle, the number of operations needed is .

Suppose the permutation consists of cycles. Let the cycles be and their sizes be . Each cycle can be represented as .

The first shift operation is .

The second shift operation sorts each first element of each cycle after it was displaced in the first operation. So the second shift operation is .

Number of operations: , , or 