Editorial for DMOPC '18 Contest 1 P3 - Sorting
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
swaps to sort the array.