[RMI 2019] Devil

Difficulty Ratings

Idea Creativity: 3/5
Techniques Used: 2/5
Implementation : 3/5

Link

English

Statement

You are given a string of length $1 \le N \le 1e5$ that only consists of digits $1$~$9$. Permutate the given digits to minimize the maximum integer that can be formed by taking a substring of length $K$.

Solution

Firstly, it is obvious that you can move the largest K-1 digits to the back of the string and ignore them. Now, the $K$ is no longer significant and you only have to minimize the lexiographically largest non empty-suffix (here empty string is lexicographically largest :P).
So, let's imagine you have a bunch of strings $s$ where you have to stick them together in some ways to minimize the maximum suffix. Then, you should repeat the following step until only one string remain: append the lexicographically smallest string to the back of the lexicographical string. I uh..., have tried to come up with a proper proof for a while, but I couldn't... So, proof is left as an exercise for readers.
So now you have this thing, and you realise that if you only consider all distinct strings that appear in our list of strings, then you realise every new string formed is always either lexicographically largest or 2nd largest, and you can order them easily. Also, you can use a deque of characters to represent each string, so by small-to-large the complexity is $O(NlgN)$.