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

Editorial for DMOPC '18 Contest 1 P2 - 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: Kirito

For $30\%$ $30 %$ of points, we have $1 \le K \le 2$ $1 \leq K \leq 2$ . If $K = 1$ $K = 1$ , then the list can be sorted for sure. If $K = 2$ $K = 2$ , then we can separate the list into elements with even and odd indices, sort those lists, and check if alternating between the two lists yields a sorted list.

Time Complexity: $\mathcal O(N \log N)$ $O (N \log N)$

For the remaining $70\%$ $70 %$ of points, we can check if $A_i \equiv i \bmod K$ $A_{i} \equiv i mod K$ , for all $i$ $i$ , $1 \le i \le N$ $1 \leq i \leq N$ . This is because in the sorted list, $A_i = i$ $A_{i} = i$ , and the $i$ $i$ th element can only be swapped with elements that are equivalent modulo $K$ $K$ .

Time Complexity: $\mathcal O(N)$ $O (N)$

Comments

There are no comments at the moment.