← All solutions

Solved by 33 teams.

First solved after 72 minutes.

Shortest team solution: 1073 bytes.

Shortest judge solution: 1195 bytes.

The players’ best ranks are determined one player at a time. Let i be the player whose best possible rank we wish to determine. For each other player j 6= i, we find the intervals of ` for which player i strictly beats player j. This can be done by sweeping ` from 0 to infinity, stopping each time it equals a score of either of the players. Between these points, both players’ scores vary linearly, so it is straightforward to identify the critical values of ` at which player i starts or stops beating j.

Once these intervals have been found for all j 6= i, one needs to identify the maximum number of overlapping intervals, which can be done by a second sweep counting the overlap depth.

There can be at most O( p2 h) values of ` at which two players exchange ranks, or O( ph) values of ` at which a single player changes rank. For each player these O( ph) values need to be sorted for the second sweep, leading to a total of O( p2 h log( ph)) time for the algorithm described above. In fact, this can be slightly reduced to O( p2 h log p + ph log h) by noting that these events start as p already-sorted lists, but this was not needed to pass.