Official Analysis (C++)

Explanation

Observation

We can think of the output slots as positions on the number line. Consider a wagon that starts moving at time $0$. Then, that wagon can catch a candy $c_i$ $(s_i, t_i)$ if its position at time $0$ is within the range $[s_i - t_i, s_i + t_i]$. Let's define this range as the range of acceptable wagon positions for $c_i$ at time $0$. With every passing second, this range is reduced by $1$ unit to the left and to the right of $s_i$. Generally, the range of acceptable wagon positions for $c_i$ at time $t$ (where $t \leq t_i$) is:

At time $t_i$ this range has been shrunk to a single point, $s_i$.

A wagon can catch a candy $c_j$ $(s_j, t_j)$ before $c_i$, if the range of acceptable wagon positions for $i$ at time $t_j$ includes $s_j$, (since the wagon will be at $s_j$ to catch $j$). However, at time $t_j$ the range for acceptable wagon positions of $c_i$ will have been reduced to

But $s_j$ needs to be inside this range, therefore:

This is equivalent to saying that the range of acceptable wagon positions of $c_j$ is fully contained within the range of $c_i$.

We have therefore concluded that two candies can be caught by the same wagon if (and only if) their ranges of acceptable wagon positions are nested.

Finding the minimum number of wagons

We can think of each candy as its range of acceptable wagon positions at time 0 $[s - t, s + t]$ (note that each candy corresponds to a unique range and vice versa). We can conclude that a wagon can catch a sequence of candies $c_1, c_2, ..., c_k$, if they form a sequence of nested ranges. It follows that the minimum number of wagons needed is the longest sequence of non-nested ranges.

Two ranges $[l_1, r_1]$, $[l_2, r_2]$ that are not nested adhere to: $l_1 < l_2 \implies r_1 < r_2$.

If we sort the candies by the left endpoint of their ranges such that

then a sequence of non-nested ranges would correspond to an increasing sequence of right endpoints. Therefore, the minimum number of required wagons would correspond to the length of the longest increasing sequence of right endpoints.

Assigning the candies to wagons

By following the binary search algorithm described in the LIS module, we can assign the candies with the same LIS length to the same wagon. The ranges that have the same LIS length cannot be nested. If they were, we could use the inside range to increase the LIS of the outside one by 1.

Implementation

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

Copy
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pi;

int main() {
	int n;
	cin >> n;
	vector<pi> candies(n);