Editorial for DMOPC '18 Contest 1 P3 - Sorting - Olympiads Online Judge

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)$ $O (N^{2})$ or $\mathcal O(N \log N)$ $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$ $i$ to $P_i$ $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$ $1$ operation to sort a cycle. Because we only need to perform a shift operation on cycles of size greater than $1$ $1$ , there are at most $N/2$ $N / 2$ such cycles. This is enough to score full points for the second subtask.

Number of operations: $N/2$ $N / 2$

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

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

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

Suppose the permutation consists of $m \ge 2$ $m \geq 2$ cycles. Let the cycles be $a_1, a_2, \dots, a_m$ $a_{1}, a_{2}, \dots, a_{m}$ and their sizes be $k_1, k_2, \dots, k_m$ $k_{1}, k_{2}, \dots, k_{m}$ . Each cycle can be represented as $[a_{i,1}, a_{i,2}, \dots, a_{i,k_i}]$ $[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}$ $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}$ $a_{m, 1}, a_{m - 1, 1}, \dots, a_{1, 1}$ .

Number of operations: $0$ $0$ , $1$ $1$ , or $2$ $2$

Comments

1

KevinWan commented on Sept. 12, 2018, 4:38 p.m. ← edited →

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