Problem authors: Pavle Martinović and Mladen Puzić

Two players — ~N = 2~

For each medal we can determine who won more matches after that day and thus receives this medal in the end. If we do this starting with the last match, we can do this for all medals in ~\mathcal{O}(M)~ so the total complexity is ~\mathcal{O}(N+M)~.

Simulation — ~N, M \le 2000~

We can simulate the process by going through matches and maintaining a list of medals for each participant. For each pair of participant and medal we keep the number of nights that that participant held that medal. Then for each medal, we determine who held it the longest. Complexity: ~\mathcal{O}((N+M)M)~.

The winner of the ~i~th match participates in the ~(i+1)~th match for all ~i~

For each medal, we need to determine the participant with the most wins. Observe that as the winner always plays the next match, all medals will always stay together. Like in Subtask 1, we can now go through the days starting at the last day, maintaining the number of wins and keeping track of which participant has the most wins. Complexity: ~\mathcal{O}(N+M)~.

At every match, the winner has at least as many medals as the loser

From the fact that the match is always won by the participant with the larger amount of medals at the moment, we can deduce that each medal will switch hands at most ~\mathcal{O}(\log M)~ times, as if we look at a fixed medal, the number of medals the person who holds this medal has doubles for each change of hands. Thus, we can simulate the process, but this time, in contrast to Subtask 2, we can not keep days held for each medal and participant. However, there will be at most ~\mathcal{O}(\log M)~ medal holders per medal, so we can just remember all of them and find who held it the most nights in the end. Complexity: ~\mathcal{O}(M \log M + N)~.

Once a participant loses, they are never in a match again

Construct a tree where each match is a node. The parent of node ~x~ is the next match where the winner of match ~x~ appears. Add a fake root, so we turn the forest into a tree. The lifetime of each medal is a path from its first match to the root. All matches of a participant are consecutive on the path from the match where she first appeared to the root. This means that we can do DFS on the tree, starting from the root, and maintain who held each medal the longest from the root to the current node and also the current medal holder. Complexity: ~\mathcal{O}(N+M)~.

Full Score

Construct the same tree as in the Subtask 5. Participants' matches are no longer a single path in the tree. Instead of keeping just the current and the longest medal holder, we need to keep the count for every participant and also maintain the longest medal holder. This can be done by keeping track of how many medals on a path a participant has one and reversing the changes when going up in the DFS tree. Complexity: ~\mathcal{O}(N+M)~.