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

For Subtask 1, you can check every permutation of indices.

Time Complexity: \mathcal O(N \cdot N!)

For Subtask 2, the intended approach is brute-forcing subsets. Another approach that probably works is randomly selecting permutations and checking them.

Time Complexity: \mathcal O(N^2 \cdot 2^N)

Now to obtain 50\% on any subtask, consider the smallest possible value s such that A_K=s and the largest possible value t such that A_K=t. It is not hard to see that these values are obtained when the frequencies are sorted from largest to smallest and smallest to largest respectively.
What is not clear is why A_K can be equal to r for s \le r \le t. However, this is a programming competition, so submitting this will obtain 50\% without any need of understanding it.

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

For Subtask 3, 4, and 5, we prove the above claim. Start with the frequencies sorted from smallest to largest and bubble-sort them until they are from largest to smallest. So two adjacent frequencies get swapped, and only if F_i>F_j and i>j. It is easy to see that a swap either does not alter A_K or it increases it by exactly 1. Since it starts at s and ends at t, then clearly, it reaches every value between s and t. So it is proved.

So for Subtask 3, 4, and 5, we can simulate the bubble sort. For Subtask 3, each swap of the bubble sort is done and each time, all N values are recomputed. For Subtask 4, the N values are not recomputed. For Subtask 5, only swaps which affect the X values are done.

Time Complexity: \mathcal O(N^3), \mathcal O(N^2), and \mathcal O(N \log N)

Another approach for Subtask 5 is to sort the frequencies and test every subarray of length X as F_1, F_2, \dots, F_X. The proof of this is left to the reader.

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


There are no comments at the moment.