Editorial for TLE '16 Contest 6 (Mock CCC) S4 - Bubble Sort

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: d

For the first subtask, $N=1$ ~N=1~ is possible and the answer is 0. All other odd $N$ ~N~ are impossible to sort. For even values of $N$ ~N~, the problem can be solved like this:

Sort the first $\frac N 2$ ~\frac N 2~ elements of the array with bubble sort
Sort the last $\frac N 2$ ~\frac N 2~ elements of the array with bubble sort
Merge these elements together to get a fully sorted array, which can be done with bubble sort

Time complexity: $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~

For the second subtask, only every continuous sequence of 5 elements need to be sorted, plus the array at the very end. Make sure every continuous sequence contains the correct elements, which rejects impossible arrays such as $\{0,1,2,3,4,7,6,5\}$ ~\{0,1,2,3,4,7,6,5\}~. Next, make sure it is possible to sort each continuous sequence.

Time complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

For the third subtask, it is possible to brute force all possible ways of swapping. If the sorted array is reached, print the sequence of swaps leading to the sorted array. Otherwise, it is impossible.

Time complexity: $\mathcal{O}(N\cdot N!)$ ~\mathcal{O}(N\cdot N!)~

The fourth subtask is intended to reward submissions that could not pass the fifth subtask.

Isn't this trivial?

- William Zhao

Define a bad pair to be a pair $(i, j)$ ~(i, j)~ with these properties:

$i < j$ ~i < j~
$A[i] = i$ ~A[i] = i~
$i > A[j]$ ~i > A[j]~

Then $A[j]$ ~A[j]~ cannot move to its correct index because $A[i]$ ~A[i]~ is blocking the path. If a bad pair exists, print Give up.

If no bad pairs exist, a sequence of swaps can always be created to sort the array. This can be proved by construction.

For $N = 1$ ~N = 1~, the sequence of swaps is empty. Otherwise, it is enough to construct a sequence of swaps to make $A[N] = N$ ~A[N] = N~ (or $A[1] = 1$ ~A[1] = 1~) while not creating any bad pairs (for obvious reasons).

The explanation for the fifth subtask is a work in progress, and may never be posted. An "avoidance" selection sort is the intended way of solving the problem.

Also, Jason is too lazy to finish the editorial. If you wish to receive an editorial, please report an issue on the main problem and ask for a full editorial.

Time complexity: $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~

Comments

There are no comments at the moment.