PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES
Sorting
EXPLANATION
Assume that P_1, P_2,\dots, P_N is a good ranking.
Then:
-
Each of the top \lfloor\frac N2\rfloor players P_1,P_2,\dots, P_{\lfloor \frac N2\rfloor} won at least \lceil \frac N2 \rceil games.
-
Each of the bottom \lfloor\frac N2\rfloor players P_{N-(\lfloor \frac N2\rfloor-1)}, \dots, P_{N-1}, P_N lost at least \lceil \frac N2 \rceil games. In particular each of them won strictly less than \lfloor \frac N2\rfloor (since each player played exactly N-1 games).
-
If N is odd, P_{\lceil \frac N2 \rceil} won exactly \lfloor \frac N2\rfloor games and lost exactly \lfloor \frac N2\rfloor games.
Therefore the number of won and lost games is sufficient to determine whether a player is in the top half of the ranking or in the bottom half (or in the middle).
Now it remains to determine the relative order of the players in the top half and in the bottom half of the ranking.
Notice that, due to the definition of good ranking, the outcome of a game between two players in the top half of the ranking is consistent with their ranking position (i.e., the one ranked better wins). The same holds for games between players in the bottom half of the ranking.
Thus we can obtain the order of the players in the top half of the ranking by sorting by the number of wins considering only games they played with another player in the top half of the ranking. The same holds for the bottom half of the ranking.
We have described an algorithm that uniquely identifies the good ranking P_1, P_2,\dots, P_N (notice that, as a byproduct of the solution, if a good ranking exists is unique).
In the end, we shall check that the resulting ranking is a good ranking. The overall complexity is O(N^2).
SOLUTION
The author’s solution can be found here.