## Editorial for DMOPC '18 Contest 1 P3 - Sorting

**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:

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

## Comments

Some people got 21 points on this problem by using O(N) swaps to sort the array.