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

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 NN (1N21051≤N≤2⋅105), the number of times apples hit the number line or FJ's cows appear.The next NN lines each contain four integers qiqititixixi, and nini (qi{1,2},0ti109,0xi109,1ni103qi∈{1,2},0≤ti≤109,0≤xi≤109,1≤ni≤103).

 

  • If qi=1qi=1, this means that nini of FJ's cows arrive on the number line at time titi at location xixi.
  • If qi=2qi=2, this means that nini apples will hit the number line at time titi at location xixi.

It is guaranteed that all of the ordered pairs (ti,xi)(ti,xi) are distinct.

 

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

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

 

SAMPLE INPUT:

5
2 5 10 100
2 6 0 3
2 8 10 7
1 2 4 5
1 4 7 6

SAMPLE OUTPUT:

10

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

 

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

 

SAMPLE INPUT:

5
2 5 10 100
2 6 0 3
2 8 11 7
1 2 4 5
1 4 7 6

SAMPLE OUTPUT:

9

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

 

  • All six of FJ's cows that arrive at time t=4t=4 catch one of the apples that land at time t=8t=8.
  • Three of the remaining cows that arrive at time t=2t=2 catch one of the apples that land at time t=6t=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 xx-axis and time is the yy-axis. For a given cow that arrives at time tt to position xx, the possible apples that that cow could catch are the ones landing at time tt′ at position xx′ that satisfy ttt′≥t and |xx||tt||x′−x|≤|t′−t|. This region in the plane is a sort of infinite V shape with 4545 degree angles extending upwards from the point (x,t)(x,t).

If we rotate the entire plane 4545 degrees clockwise (transform each point (x,t)(x,t) to (u,v)=(t+x2,tx2)(u,v)=(t+x2,t−x2)), then those infinite V shapes become infinite squares, which means that the condition for a cow (u,v)(u,v) to be able to catch an apple (u,v)(u′,v′) is simply uuu≤u′ and vvv≤v′.

Let's use that transformation. We can simply ignore the 2–√2 factor as it doesn't change the condition. For now, we will assume that nn is 11, so each line of the input represents a single cow or apple.

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

Based on this greedy principle, we can devise an algorithm to solve this problem. First, sort all the cows and all the apples by vv. Now, for each apple in increasing order of vv, 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 vv at most the vv of the current apple, with the BST being sorted by uu. For each apple aa, we will first add in all the cows with vv at most the vv of aa that haven't been added yet. Then, we will query our BSTs to find the cow in the BST with the largest uu such that the uu is still small enough to catch aa. If there is such a cow, then we use it to catch aa, meaning that we remove it from the BST and increment our answer.

This algorithm runs in O(NlgN)O(Nlg⁡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 NN, and so this algorithm still runs in O(NlgN)O(Nlg⁡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]

翰林国际教育资讯二维码