USACO Gold 2022 Open - Apple Catching

Official Analysis (Java)

Explanation

In order for a cow to catch an apple, it must arrive before the apple hits the number line. Let item $i$ represent the cow and item $j$ represent the apple. Therefore, to catch the apple, $|x_i - x_j| \le t_j - t_i$ must be satisfied. After extracting the absolute value, we get these two inequalities.

We represent each item as a point $(x_i - t_i, x_i + t_i)$. According to the inequalities above, in order for a cow to catch an apple, the point of the apple must be to its top-left. Thus we can sort in ascending order based off $x_i - t_i$ and greedily assign apples with larger $x_i + t_i$ values to each cow. To maximize the number caught, we must pair each cow with the lowest y-coordinate apples that still meet above conditions.

Implementation

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

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 2e5;

struct Item {
	int q;  // type (cow or apple)
	int t;  // time of entry
	int x;  // position
	int n;  // amount