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

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

Time Complexity:

Now to obtain on any subtask, consider the smallest possible value such that and the largest possible value such that . 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 can be equal to for . However, this is a programming competition, so submitting this will obtain without any need of understanding it.

Time Complexity:

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 and . It is easy to see that a swap either does not alter or it increases it by exactly . Since it starts at and ends at , then clearly, it reaches every value between and . 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 values are recomputed. For Subtask 4, the values are not recomputed. For Subtask 5, only swaps which affect the values are done.

Time Complexity: , , and

Another approach for Subtask 5 is to sort the frequencies and test every subarray of length as . The proof of this is left to the reader.

Time Complexity: