USACO Silver 2020 December - Rectangular Pasture

Official Analysis (C++)

Explanation

Let's analyze the sample case a bit more:

The bound of $N \leq 2500$ suggests a complexity of $\mathcal{O}(N^2)$, so let's try to think about this problem from the perspective of each pair of cows.

Notice that for any two pair of cows, we can always create a unique box, with one cow at a corner and the other cow at the opposing corner.

Note that we can do this because the problem stipulates that all x-positions and y-positions are distinct. If they weren't, we could form the same box with two different pairs of points like so:

Drawing out the boxes created by this observation, we now have the following boxes:

This only gives us $6$ rectangles, though, which is less than the actual answer. The reason for this is because we've failed to account for the boxes where there's only one or no points at the corners. Fortunately, we can construct such rectangles from the ones we initially have by expanding the top and/or bottom border to include any cows that weren't initially included in the fence.

More specifically, if we let $a$ be the number of cows above the initial bounding box and $b$ be the number of cows below the initial bounding box, there are $(a+1)(b+1)$ distinct bounding boxes from the perspective of the initial box. The $+1$ is because a choice is to simply not include any cows above and/or below the box.

Using the method of construction described above, we can now have the following additional boxes:

However, if we iterate through all cows to find the number of cows above and below a bounding box, this would give us a complexity of $\mathcal{O}(N^3)$, since we're already iterating through all pairs of cows. Thus, we need a constant-time method to find the number of cows that are above or below a certain y-coordinate and also between two certain x-coordinates.

This is possible with prefix sums. For each y-coordinate that a cow is at, we iterate through all the cows in order of x-coordinate, and construct two prefix sum arrays for the given y-coordinate: one for how many cows are above the coordinate and another for how many cows are below the coordinate. Now, we have our constant-time method!

Notice, though, that our $6+2=8$ rectangles still falls short of the $13$ stipulated. This is because we've failed to account for the cases where FJ encases a single cow or none at all. Thus, we have to add $N+1$ to our subtotal, which in our case gives us the $4+1=5$ extra needed sets!

Video Solution

Implementation

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

Copy
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main() {

Copy
import java.io.*;
import java.util.*;

public class RPasture {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

		int cowNum = Integer.parseInt(read.readLine());

		Set<Integer> seenX = new HashSet<>();