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