Home » 国际竞赛 » Details

USACO 2022 US Open Contest, Gold Problem 1. Apple Catching

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午6:36

USACO 2022 US Open Contest, Gold Problem 1. Apple Catching

It's raining apples! At certain points in time, some number of apples will hit the number line. At certain points in time, some of Farmer John's cows will arrive on the number line and start catching apples.

If an apple hits the number line without a cow to catch it, it is lost forever. If a cow and an apple arrive at the same time, the cow catches it. Each cow can travel one unit per second. Once a cow catches a single apple, she exits the number line.

If FJ's cows collaborate optimally, how many apples can they catch in total?

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N$ ( $1 \leq N \leq 2 \cdot 10^{5}$ ), the number of times apples hit the number line or FJ's cows appear.The next $N$ lines each contain four integers $q_{i}$ , $t_{i}$ , $x_{i}$ , and $n_{i}$ ( $q_{i} \in {1, 2}, 0 \leq t_{i} \leq 10^{9}, 0 \leq x_{i} \leq 10^{9}, 1 \leq n_{i} \leq 10^{3}$ ).

If $q_{i} = 1$ , this means that $n_{i}$ of FJ's cows arrive on the number line at time $t_{i}$ at location $x_{i}$ .
If $q_{i} = 2$ , this means that $n_{i}$ apples will hit the number line at time $t_{i}$ at location $x_{i}$ .

It is guaranteed that all of the ordered pairs $(t_{i}, x_{i})$ are distinct.

OUTPUT FORMAT (print output to the terminal / stdout):

The maximum number of apples FJ's cows may collectively catch.

SAMPLE INPUT:

SAMPLE OUTPUT:

In this example, none of the $100$ apples that land at time $t = 5$ may be caught. Here is a way for $10$ apples to be caught:

All six of FJ's cows that arrive at time $t = 4$ catch one of the apples that land at time $t = 8$ .
One of FJ's cows that arrive at time $t = 2$ catches one of the apples that land at time $t = 8$ .
Three of the remaining cows that arrive at time $t = 2$ catch one of the apples that land at time $t = 6$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

Here again, none of the apples that land at time $t = 5$ may be caught. Furthermore, none of the cows that arrive at time $t = 2$ may catch any of the apples that land at time $t = 8$ . Here is a way for $9$ apples to be caught:

All six of FJ's cows that arrive at time $t = 4$ catch one of the apples that land at time $t = 8$ .
Three of the remaining cows that arrive at time $t = 2$ catch one of the apples that land at time $t = 6$ .

Problem credits: Benjamin Qi

USACO 2022 US Open Contest, Gold Problem 1. Apple Catching 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Danny Mittal)

Visualize the cows and apples as being on a plane where position is the $x$ -axis and time is the $y$ -axis. For a given cow that arrives at time $t$ to position $x$ , the possible apples that that cow could catch are the ones landing at time $t^{'}$ at position $x^{'}$ that satisfy $t^{'} \geq t$ and $| x^{'} - x | \leq | t^{'} - t |$ . This region in the plane is a sort of infinite V shape with $45$ degree angles extending upwards from the point $(x, t)$ .

If we rotate the entire plane $45$ degrees clockwise (transform each point $(x, t)$ to $(u, v) = (\frac{t + x}{\sqrt{2}}, \frac{t - x}{\sqrt{2}})$ ), then those infinite V shapes become infinite squares, which means that the condition for a cow $(u, v)$ to be able to catch an apple $(u^{'}, v^{'})$ is simply $u \leq u^{'}$ and $v \leq v^{'}$ .

Let's use that transformation. We can simply ignore the $\sqrt{2}$ factor as it doesn't change the condition. For now, we will assume that $n$ is $1$ , so each line of the input represents a single cow or apple.

We can take a greedy approach to this problem. Consider the apple $a$ with smallest $v$ , assuming that it can be caught by at least one cow, and out of all cows that could catch it, consider the cow $c$ with largest $u$ . There is no apple that $c$ can catch that any other cow that can catch $a$ cannot catch, because all of them have $u$ at most the $u$ of $c$ , and since they can all catch $a$ , all of them have a $v$ not larger than the $v$ of any apple that can be caught at all. Therefore, it is optimal to assign $c$ to catch $a$ .

Based on this greedy principle, we can devise an algorithm to solve this problem. First, sort all the cows and all the apples by $v$ . Now, for each apple in increasing order of $v$ , we will find the optimal cow to catch it. We will do this by maintaining a BST (binary search tree) of the cows that have $v$ at most the $v$ of the current apple, with the BST being sorted by $u$ . For each apple $a$ , we will first add in all the cows with $v$ at most the $v$ of $a$ that haven't been added yet. Then, we will query our BSTs to find the cow in the BST with the largest $u$ such that the $u$ is still small enough to catch $a$ . If there is such a cow, then we use it to catch $a$ , meaning that we remove it from the BST and increment our answer.

This algorithm runs in $O (N \lg N)$ as we add and remove each cow to/from the BST at most once, and we query the BST once for each apple.

It remains to handle the fact that each line of the input can represent multiple cows or apples. To handle this, we modify the part where we find the optimal cow to catch each apple. We will instead repeatedly find the optimal group of cows for the current group of apples, and assign as many cows as possible to apples. At each step of this algorithm, either the group of cows will be exhausted, or the group of apples will be exhausted. Therefore, the amount of steps is $N$ , and so this algorithm still runs in $O (N \lg N)$ .

Java code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class AppleCatching {

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        List<Stuff> cows = new ArrayList<>();
        List<Stuff> apples = new ArrayList<>();
        for (int j = 1; j <= n; j++) {
            StringTokenizer tokenizer = new StringTokenizer(in.readLine());
            int q = Integer.parseInt(tokenizer.nextToken());
            int time = Integer.parseInt(tokenizer.nextToken());
            int location = Integer.parseInt(tokenizer.nextToken());
            int amount = Integer.parseInt(tokenizer.nextToken());
            int y = time - location;
            int x = time + location;
            (q == 1 ? cows : apples).add(new Stuff(amount, y , x));
        }
        Collections.sort(cows, Comparator.comparingInt(cow -> cow.y));
        Collections.sort(apples, Comparator.comparingInt(apple -> apple.y));
        TreeSet<Stuff> treeSet = new TreeSet<>((cow1, cow2) -> {
            if (cow1.x != cow2.x) {
                return cow1.x - cow2.x;
            } else {
                return cow1.y - cow2.y;
            }
        });
        int j = 0;
        int answer = 0;
        for (Stuff apple : apples) {
            while (j < cows.size() && cows.get(j).y <= apple.y) {
                treeSet.add(cows.get(j));
                j++;
            }
            int amount = apple.amount;
            while (amount > 0 && !treeSet.isEmpty() && treeSet.first().x <= apple.x) {
                Stuff cow = treeSet.floor(new Stuff(0, 1000000000, apple.x));
                treeSet.remove(cow);
                int caught = Math.min(amount, cow.amount);
                answer += caught;
                amount -= caught;
                if (caught < cow.amount) {
                    treeSet.add(new Stuff(cow.amount - caught, cow.y, cow.x));
                }
            }
        }
        System.out.println(answer);
    }

    static class Stuff {
        final int amount;
        final int y;
        final int x;

        Stuff(int amount, int y, int x) {
            this.amount = amount;
            this.y = y;
            this.x = x;
        }
    }
}

[/hide]