Editorial for COCI '22 Contest 2 #4 Prijateljice

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.

Note that if both Leona and Zoe for each letter of the alphabet have at least one word beginning with that letter, then the winner is the player which has the lexicographically greatest word.

That leads us to the following question: what happens if both have words that begin with the first x letters of the alphabet, but only one of them has a word beginning with the x+1-th letter?

Without loss of generality, suppose Leona has a word beginning with the x+1-th letter. Note that if Leona has the lexicographically greatest word beginning with one of the first x letters, then she is the winner. But if Zoe has such a word, then the game continues.

Now, we can conclude the winner is determined by the first letter which a player doesn't have a word beginning with, and the other player has the lexicographically greatest word among all the words beginning with the letters before that letter.

Alternatively, the task can be solved with dynamic programming. This is left as an exercise for the reader.


There are no comments at the moment.