USACO Silver 2020 December - Rectangular Pasture

Author: Kevin Sheng

Official Analysis (C++)

Explanation

Let's analyze the sample case a bit more:

initial

The bound of N2500N \leq 2500 suggests a complexity of O(N2)\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:

countercase

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

corners

This only gives us 66 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 aa be the number of cows above the initial bounding box and bb be the number of cows below the initial bounding box, there are (a+1)(b+1)(a+1)(b+1) distinct bounding boxes from the perspective of the initial box. The +1+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:

new

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 O(N3)\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=86+2=8 rectangles still falls short of the 1313 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+1N+1 to our subtotal, which in our case gives us the 4+1=54+1=5 extra needed sets!

Video Solution

Implementation

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

C++

#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
int main() {

Java

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<>();

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!