Editorial for COCI '19 Contest 5 #2 Političari

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.

It was possible to score of total points on this task simply by implementing what was described in the task statement. In other words, you should have correctly implemented the rules by which politicians blame each other until we reach the show. The time complexity of this solution is .

To score all points on this task, it was necessary to observe that the blaming process is cyclical. Since the next guest on a talk show solely depends on the previous guest and the person who blamed the previous guest, we can conclude that there are at most different shows (states). We consider two shows to be the same if they have the same guest that was blamed by the same politician in the previous show. Otherwise, the shows are considered different.

Since the total number of different shows is considerably less than the maximum episode in which we are interested in, we can simulate the process until we reach the show we have seen before (already visited state). At that moment, assuming that we keep track of some key items that have happened, we can use the power of math to calculate who will be the guest of the show.

Let's assume we have realized that the show will be the same as a (some prior) show. In that case, we have just entered a cycle of length and can conclude that the guest which appeared in show will also appear in the show. Here, we use to denote the modulo operator.

Time complexity of the described solution is .