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 \le K \le 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)$ ~\mathcal 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 \bmod K~, for all $i$ ~i~, $1 \le i \le N$ ~1 \le i \le 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)$ ~\mathcal O(N)~

Comments

There are no comments at the moment.