Editorial for COCI '10 Contest 2 #3 Igra
Submitting an official solution before solving the problem yourself is a bannable offence.
Observe that, if Slavko loses the game with the most beautiful word, he could not have won. Therefore, it is sufficient to come up with a strategy which ensures that he constructs the most beautiful word at the end.
To accomplish the above strategy, Slavko is required to take some lexicographically smallest letter from the remaining sequence on each turn. Otherwise, if some other letter is to be taken, it is obvious that the final word cannot be lexicographically smaller than the one obtained by applying the above mentioned strategy.
In case of a tie, the rightmost such letter should be taken. The proof follows.
Proof
Assume that Slavko takes the next move. Let the chosen letter denote the rightmost lexicographically smallest in the remaining sequence, and let be the number of remaining letters to the right. There are three cases:
The number of remaining lexicographically smallest letters in the sequence is less than or equal to .
Mirko has letters to take before reaching the chosen letter. In the meantime, Slavko can take all lexicographically smallest letters (since none of these appear to the right of the chosen one), in arbitrary order.
The number of remaining lexicographically smallest letters in the sequence is greater than and Mirko takes the chosen letter on his next turn.
If Slavko can take all lexicographically smallest letters from the sequence, he must, obviously, take the chosen one as well (otherwise Mirko would take it).
If Slavko cannot take all lexicographically smallest letters from the sequence, it is irrelevant which one of them he takes next (because sooner or later he will be forced to let Mirko take some lexicographically smallest letter, but it need not be now). Thus, he can take the chosen letter.
The number of remaining lexicographically smallest letters in the sequence is greater than and Mirko does not take the chosen letter on his next turn.
Assume that Slavko does not take the chosen letter on his current turn, instead taking another one. Nevertheless, using the strategy above, he will need to take it before Mirko does. Therefore, Slavko can swap the two moves, taking the chosen letter on this turn and taking the other one (which will still be available) later.
Comments