CLIMBINGRANK Editorial

Origin story: The rules described in the statement are exactly those adopted in the Olympics 2020.
During the sport climbing final (in particular during the last event, that is lead) an infographic showed some data about who could still win the event considering the current partial lead ranking. That was the inspiration for this task.

Reducing to a simpler subproblem.

First of all, if athlete 1 has not competed yet in lead, then we add him as first in the lead ranking (since this is clearly optimal).
Let i_1 be the final ranking position in the lead competition of athlete 1. We will iterate over all possible values of i_1 (not all values are possible since athlete 1 belongs to the partial lead ranking).

For each 2\le i\le n, let a_i be the minimal ranking position in the lead competition that athlete i can achieve in order to get a final score \ge than the score of 1 (which is now fixed, since we have fixed i_1).

Now the problem is equivalent to the following:

Subproblem: We are given a partial ranking a_1,a_2,\dots, a_m and we are given the final position i_1 of athlete 1 (who belongs to the partial ranking). Moreover we are given an array p_2, p_3,\dots, p_n. Among all the valid complete rankings where athlete 1 is in position i_1, find the maximum number of athletes x such that their ranking position is \ge p_x.

We will describe a solution to the subproblem with complexity O(n^2), then we will optimize it to O(n). Hence, the overall complexity of the solution to the whole problem is O(n^2) (since we have to solve O(n) subproblems). Also solutions with complexity O(n^2\log(n)) could get accepted if implemented correctly.

Solving the subproblem in O(n^2).

Let A=\{a_1, a_2,\dots, a_m\} be the set of athletes who belong to the partial ranking.
Let B=\{b_1, b_2,\dots, b_{n-m}\} be the set of athletes who do not belong to the partial ranking, sorted by the value of x\mapsto p_x.

Given a complete ranking, we say that an athlete x\ge 2 loses if his ranking position is \ge p_x, and wins otherwise. We want to maximize the number of losing athletes.

Assume that a_{j_1} = 1, i.e., athlete 1 is the j_1-th in the partial ranking. Then, for j<j_1, athlete a_j will have ranking position \le i_1 - (j_1-j) (since athlete 1 must have ranking position equal to i_1). If p_{a_j} > i_1-(j_1-j), then athlete a_j is a winner in any valid ranking and therefore we set p_{a_j}=n+1 (so that he becomes a winner even in non valid rankings).

Choose the number 0\le q\le n-m of contestants in B who lose.
It is convenient if they are b_1,b_2,\dots, b_q. The remaining b_{q+1}, b_{q+2}, \dots, b_m can be positioned anywhere in the lead ranking. We may assume that b_{q+1}, b_{q+2},\dots, b_m are ranked better than b_1,b_2,\dots, b_q.

Now, the relative order of A and B in the complete ranking is fixed, it remains to choose how to interlace the two groups.
With a simple greedy algorithm with complexity O(n) we are going to create the best ranking such that the ranking of athlete 1 is \ge i_1 and there are at least q losers in B; then we will observe how the condition \ge i_1 is in fact equivalent to =i_1.

Let us iterate over all ranking positions from i=1 to n and we decide if they shall be assigned to A or B. If the first element in B can be placed at position i (always true if he is not among the q losers, true only if i\ge p_b if he is one of the losers) then assign this position to B and remove the corresponding contestant from B; otherwise we assign this position to A.

At the end, we shall do some consistency checks:

  • Did we manage to place all contestants from B? If not, then the value q is not valid.
  • The resulting position of 1 is \ge i_1? If not, then the value q is not valid.

It the consistency checks pass, then we have created the best possible ranking (that is the one where there are the largest possible number of losers in A) such that athlete 1 gets a ranking position \ge i_1 and beats at least q contestants in B.

Why ranking position \ge i_1 is equivalent to =i_1.
We show that this ranking can be modified so that the number of losers in B remains the same or increases, the number of losers in A remains the same and the ranking position of 1 becomes exactly i_1. Notice that in the implementation one does not need to perform this modification, but it is necessary to show the correctness of the algorithm.

Move athletes in B who ranks better than athlete 1 to the position just after athlete 1, starting from those with the highest ranking. Since i_1 is a possible ranking position for athlete 1 taking into account the partial ranking, this process is going to move athlete 1 to position i_1 (as soon as that happens, we stop the process).
It is clear that any athlete in B who was a loser remains a loser (since the ranking position of any athlete in B remains the same or increases). It is less clear why an athlete in A who was a loser remains a loser (since the ranking position of an athlete in A may decrease in the process). Now the change to x\mapsto p_x we performed to take into account athletes in A who are winning no matter what will play a role. The only athletes in A (apart from 1) whose ranking position may decrease in the process are a_j with j<j_1 (recall that a_{j_1}=1). Notice that if the position of a_j decreases, then it becomes exactly i_1-(j_1-j) (because if the position decreases then there are no athletes in B between a_j and 1 in the ranking) and therefore, given the definition of p_{a_j}, athlete a_j remains a loser if he was a loser before the process.

Conclusion.
To conclude, we shall simply check how many contestants from A are losing with this ranking (and add q to get the total number of losing contestants).

Solving the subproblem in O(n).

The crucial part of the previous solution is to produce, greedily, a string of As and Bs which represents how the contestants in A and in B interlace in the ranking (if the first letter is an A then the first contestant in the ranking is a_1).
One can observe (it is hard to notice it, but easy to prove) that:

Crucial observation: When q decreases by 1, the effect on the string is that the first A and the last B gets swapped.

Then, the optimization goes as follows.

We perform the greedy linear scan only for q=n-m (which is the maximum value of q). If the resulting string contains less than n-m Bs, we replace the first As with Bs (and adjust the value of q accordingly) until there are exactly n-m Bs.

Since we know very well what happens to the string when q changes, we can also observe that each contestant x\in A will be losing if and only if q\le q_x, for some q_x. The values q_x for all x\in A can be computed in O(n).
Then, for each 0\le q, one can compute how many contestants in A are losing with a total complexity of O(n).

There is only one missing thing to check, for which values of q the final ranking of 1 is \ge i_1? This can be completely skipped! Indeed if the final ranking of 1 is \tilde i_1<i_1, then the ranking we obtain is valid for the subproblem with \tilde i_1 as ranking position of 1 (and that would give us a larger number of loser contestants).

Implementation: Official solution.

Why is this true? Can’t this violate the partial order? Also, is there solution code? My solution had an extra log factor and I’m not sure how to get rid of it.

You are right, that is just false. The official solution is correct, the editorial is wrong. I will fix it tomorrow, now I am very tired and I would just make a mess.

Sketch: The idea is that you can move people in B after athlete 1 (so that the position of athlete 1 becomes i_1). You might argue that some people in A who are losers may become winners in the process (and this would be bad!). This does not happen if the values x\mapsto p_x are chosen appropriately (see the lines from 140 to 148 in the official solution).

I have added a link to the official O(n^2) solution.

1 Like

Fixed, thank you very much for spotting the error.