Editorial for COCI '17 Contest 2 #2 ZigZag


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.

For each given letter, we must find a word from the list that starts with that letter. That word must be used the least amount of times. This algorithm is clear from the task. Given the constraints for the input data, it is necessary to be careful with the solution implementation, since the naive solution has a problem with the time limit.

A helpful trick is to, for each letter, sort the words starting with that letter, and iterate over them in a circular manner using a pointer. It is obvious that the first chosen word will be the least used one, next time we will choose the second word, and when we reach the final words, we will again return to the first word.


Comments

There are no comments at the moment.