## 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.

Authors: 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 , so 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 .

If 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