E. Anya's Simultaneous Exhibition
constructive algorithms; graphs; greedy; interactive; sortings
This is an interactive problem.Anya has gathered \(n\) chess experts numbered from \(1\) to \(n\) for which the following properties hold: For any pair of players one of the players wins every game against the other (and no draws ever occur); Transitivity does not necessarily hold — it might happen that \(A\) always beats \(B\), \(B\) always beats \(C\) and \(C\) always beats \(A\). Anya does not know, for each pair, who is the player who beats the other.To organize a tournament, Anya hosts \(n-1\) games. In each game, she chooses two players. One of them wins and stays, while the other one is disqualified. After all the games are hosted only one player will remain. A player is said to be a candidate master if they can win a tournament (notice that the winner of a tournament may depend on the players selected by Anya in the \(n-1\) games).Since Anya is a curious girl, she is interested in finding the candidate masters. Unfortunately, she does not have much time. To speed up the process, she will organize up to \(2n\) simuls (short for ""simultaneous exhibition"", in which one player plays against many).In one simul, Anya chooses exactly one player who will play against some (at least one) of the other players. The chosen player wins all games they would win in a regular game, and the same holds for losses. After the simul finishes, Anya is only told the total number of games won by the chosen player (but not which ones). Nobody is disqualified during a simul.Can you help Anya host simuls and determine the candidate masters?The winning players in each pair could be changed between the simuls, but only in a way that preserves the results of all previous simuls. These changes may depend on your queries.
In the first example, the first query describes a simul in which player \(1\) plays against player \(2\) (and no one else). The answer to the query is \(1\), meaning that player \(1\) won the only game they played. We can conclude that \(1\) beats \(2\). Similarly, the second query tells us that \(2\) beats \(3\) and the third query tells us that \(3\) beats \(1\). All players are candidate masters in this case as Player \(1\) can win the tournament if \(2\) and \(3\) play first. \(3\) loses and leaves, while \(2\) stays. \(1\) then plays against \(2\) and wins; Other players can win in the same fashion. In the second example, the third query describes a simul in which player \(1\) plays against every other player. The answer to the query is \(4\), meaning that they won every game they played. It can be concluded that player \(1\) also beats every other player. They can never lose, hence they are the only player who can remain at the end of every possible tournament, and the only possible candidate master.