GOODRANKING - Editorial

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

EASY-MEDIUM

DRAFT EXPLANATION:

Note: The editorial is underway. To not keep you waiting however, the draft editorial of the author is attached below.

For a good ranking P_1, P_2,\dots, P_N:

  • The top \frac N2 players P_1,P_2,\dots, P_{\lfloor \frac N2\rfloor} have won at least \lceil \frac N2 \rceil games.

  • The bottom \frac N2 players P_{N-\lfloor \frac N2\rfloor}, \dots, P_{N-1}, P_N have lost at least \lceil \frac N2 \rceil games.

  • If N is odd, P_{\lceil \frac N2 \rceil} has won exactly \lfloor \frac N2\rfloor games and has 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). In the top half of the ranking, any game must be consistent with the ranking positions and thus we can obtain the order of the players in the top half of the ranking by sorting by the number of wins among them. The same holds for the bottom half of the ranking. In the end, we shall check that the resulting ranking is a good ranking, which can be done in O(N^2). Notice that, as a byproduct of the solution, if a good ranking exists is unique.