Editorial for DMOPC '21 Contest 7 P4 - Rocket Race

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 4fecta

Subtask 1

The key observation is that after fixing the last rocket used to complete the race, the previous rockets can be determined greedily in decreasing order of $a_i - b_i$ ~a_i - b_i~. For this subtask, it is sufficient to explicitly maintain an array of the rockets sorted in decreasing order of $a_i - b_i$ ~a_i - b_i~, binary searching on the prefix sums of this array for each of the $N$ ~N~ candidate last rockets. One detail to note is that the prefix sum array may not be in increasing order because $a_i - b_i$ ~a_i - b_i~ could be negative, so binary search may fail to give the correct answer. To fix this, we may simply set $b_i = \min(a_i, b_i)$ ~b_i = \min(a_i, b_i)~ for every single rocket. This is valid because the only case we would ever use a rocket where $a_i < b_i$ ~a_i < b_i~ is as the last rocket, in which case the value of $b_i$ ~b_i~ is of no significance.

Time Complexity: $\mathcal{O}(QN \log N)$ ~\mathcal{O}(QN \log N)~

Subtask 2

We can no longer loop through every possible last rocket. Instead, let's binary search on the minimum number of rockets that can be used to complete the race. Once again, we store the rockets in decreasing order of $a_i - b_i$ ~a_i - b_i~. If we consider using $k$ ~k~ rockets, the maximum forward distance can be calculated by considering the two following cases:

The last rocket is some rocket in the range $[1, k]$ ~[1, k]~. The maximum forward distance is then $\sum_{i=1}^k (a_i - b_i) + \max_{i=1}^k b_i$ .
The last rocket is some rocket in the range $[k+1, N]$ ~[k+1, N]~. The maximum forward distance is then $\sum_{i=1}^{k-1} (a_i - b_i) + \max_{i=k+1}^N a_i$ .

All the required values can be precomputed in $\mathcal{O}(N)$ ~\mathcal{O}(N)~ and accessed in $\mathcal{O}(1)$ ~\mathcal{O}(1)~, leaving us with $\mathcal{O}(\log N)$ ~\mathcal{O}(\log N)~ time per query.

Time Complexity: $\mathcal{O}((N+Q) \log N)$ ~\mathcal{O}((N+Q) \log N)~

Subtask 3

We must now consider how to maintain the array stored in the previous subtask as updates are performed. There are many possible methods, but the simplest of them is to use a segment tree indexed by coordinate-compressed $a_i - b_i$ ~a_i - b_i~. If we store the number of rockets, sum of $a_i - b_i$ ~a_i - b_i~, maximum $a_i$ ~a_i~, and maximum $b_i$ ~b_i~ in each node of the segment tree, we can obtain the required values for each binary search iteration by walking down the segment tree. This allows us to perform updates in $\mathcal{O}(\log N)$ ~\mathcal{O}(\log N)~ and answer queries in $\mathcal{O}(\log^2 N)$ ~\mathcal{O}(\log^2 N)~, sufficient for full marks.

Time Complexity: $\mathcal{O}(N \log N + Q \log^2 N)$ ~\mathcal{O}(N \log N + Q \log^2 N)~

Remark: It is also possible to answer queries with a single walk down the segment tree obtaining $\mathcal{O}((N+Q) \log N)$ ~\mathcal{O}((N+Q) \log N)~ time complexity, although this is not necessary at all given the lenient constraints on $N$ ~N~ and $Q$ ~Q~.

Comments

0

demidenko commented on March 30, 2022, 4:43 a.m.

can't figure how to answer case 2 by binary search

3

4fecta commented on March 30, 2022, 7:34 p.m.

Do you mean the fact that the formula for the second case where the last rocket is in the range $[k + 1, N]$ ~[k + 1, N]~ does not exhibit monotonic properties? In that case, we do not really mind, because the maximum forward distance is calculated by taking the maximum of case 1 and case 2. We can't get a worse answer using $k+1$ ~k+1~ rockets instead of $k$ ~k~ rockets because every rocket has a non-negative net distance traveled, remembering that we set $b_i = \min(a_i, b_i)$ ~b_i = \min(a_i, b_i)~ from before.