Problem analysis: Meteor Showers (stage III, XXXIII OI)

Problem statement

The situation described in the problem can be visualized as a rectangle of dimensions \(n \times 86\,400\,000\), as shown in the figure in the statement. Let the \(x\)-axis be horizontal and the \(y\)-axis vertical. Inside the rectangle, we have \(m\) pairwise disjoint vertical strips, i.e., vertical rectangles of width 1. Let \(P(x,y)\) denote the maximum number of consecutive painted cells upwards from \((x,y)\), i.e., \((x,y),(x+1,y),(x+2,y),\ldots\). For each \(x \in \{1,\ldots,n\}\), we want to find a value of \(y\) that maximizes \(P(x,y)\). In fact, it suffices to know the value \(\max_y P(x,y)\) for a given \(x\), without necessarily computing the corresponding \(y\).

Initial observations and simpler solutions

Suppose we explicitly mark the painted cells in the rectangle as described above. Let \(Y\) be the maximum \(y\)-coordinate of a painted cell.

If we solve the problem by directly implementing the definition, then for each of the \(O(nY)\) cells \((x,y)\), we may need to scan up to \(n\) steps upward, yielding a time complexity of \(O(n^2 Y)\). Such a solution was sufficient to pass the second subtask.

It is convenient to process the \(x\)-coordinates from right to left, using dynamic programming to compute the values \(P(x,y)\). If the cell \((x,y)\) is not painted, then \(P(x,y)=0\); otherwise, \(P(x,y)=P(x+1,y)+1\). In this way, each value \(P(x,y)\) can be computed in constant time. This improves the complexity to \(O(nY)\), which was sufficient to pass the third subtask.

There are many possible values of \(y\), but at most \(2m\) of them are actually relevant. We can initially compress all \(y\)-coordinates of the vertical strips to values in the range \(1\) to \(2m\) (in \(O(m \log m)\) time). From now on, we may assume that \(Y \le 2m\). Then the previous solution runs in time \(O(n\min(Y,m)\,+\,m \log m)\), which is sufficient to pass subtasks 1 through 4.

Efficient solution

To speed up the dynamic programming approach, we can use a segment tree. The tree is indexed by \(y\)-coordinates. For a given \(y\), the tree stores the value \(P(x,y)\) for the currently processed \(x\). Such a tree must support the following operations on indices from a range of size \(O(m)\):

• add 1 on an interval (corresponding to a vertical strip)
• set 0 on an interval (corresponding to a gap between vertical strips)
• return the maximum value stored in the tree (i.e., \(\max_y P(x,y)\))

It is possible to implement such a tree so that each operation runs in \(O(\log m)\) time, although it requires some experience. Since there are \(O(n+m)\) operations, the total time complexity is \(O((n+m) \log m)\). This solution passes all subtasks.

Improved solution

We can significantly simplify the required operations on the segment tree by storing, for each cell, the value \(P'(x,y)=P(x,y)+x\). Then, for a given \(x\), it suffices to take the maximum stored value and subtract \(x\).

If the cell \((x,y)\) is painted, then we have

\[ P'(x,y)\,=\,P(x,y)+x\,=\,P(x+1,y)+1+x\,=\,P'(x+1,y) \]

so the value \(P'(x,y)\) does not change when moving from \(x+1\) to \(x\). If the cell is not painted, then \(P'(x,y)=0+x=x\). Thus, for each maximal unpainted vertical segment, it suffices to set the value \(x\) for all its cells.

Therefore, we need to implement a segment tree supporting the following operations:

• assign a given value to an interval
• return the maximum value stored in the tree

This is a fairly standard range-update segment tree (with lazy propagation). Each operation runs in \(O(\log m)\) time, yielding overall complexity \(O((n+m) \log m)\), while the implementation is significantly simpler than in the previous solution.