Editorial for TLE '16 Contest 6 (Mock CCC) S4 - Bubble Sort
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
For the first subtask,
- Sort the first
elements of the array with bubble sort - Sort the last
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:
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
Time complexity:
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:
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
Then 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
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:
Comments