PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
If there is a number that occurs more than N/K times, then there is no solution, because otherwise there will be a subsequence that contains more than one occurence of the number, by pigeonhole principle.
If all numbers occur at most N/K times, then there is always a solution. Because we want the lexicographically smallest solution, it is easy to see that the following greedy algorithm works.
Repeat N/K times:
· M := number of remaining elements of the sequence
· While there is an element x that occurs exactly M/K times:
o Remove x from the sequence
· While the number of removed elements < K
o Remove the smallest element of the sequence
· Print the removed elements in this iteration in increasing order
To make the algorithm run within the time limit, we should use a balanced tree to store the number of occurrences of each number and to store the elements that occur M/K times. C++'s maps and sets are sufficient to store those information.
The idea is rather easy to come up with but the efficient implementation is somewhat harder that expected, so the number of TLE and WA solutions were large (as expected, too).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.