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: \mathcal O(N^2) or \mathcal O(N \log N)

For the second subtask, observe that the permutation can be modelled as a graph. Build an "edge" from each element i to P_i. 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 1 operation to sort a cycle. Because we only need to perform a shift operation on cycles of size greater than 1, there are at most N/2 such cycles. This is enough to score full points for the second subtask.

Number of operations: N/2

For the final subtask, observe that the answer is always 0, 1, or 2.

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

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

Suppose the permutation consists of m \ge 2 cycles. Let the cycles be a_1, a_2, \dots, a_m and their sizes be k_1, k_2, \dots, k_m. Each cycle can be represented as [a_{i,1}, a_{i,2}, \dots, a_{i,k_i}].

The first shift operation is a_{1,1}, a_{1,2}, \dots, a_{1,k_1}, a_{2,1}, a_{2,2}, \dots, a_{2,k_2}, \dots, a_{m,k_m}.

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 a_{m,1}, a_{m-1,1}, \dots, a_{1,1}.

Number of operations: 0, 1, or 2


Comments


  • 1
    KevinWan  commented on Sept. 12, 2018, 4:38 p.m.

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