Official Analysis (C++)

Video Solution 1

By Kyle Xu

Note: The video solution might not be the same as other solutions. Code in C++ and Java.

Video Solution 2

Solution 1

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!

Implementation

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

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

Solution 2

Explanation

The central idea behind this solution is identical to the previous solution, but differs in how we count the cows above and below a bounding box.

Instead of keeping two prefix sums for the number of cows above and below a y-coordinate, we directly use 2D prefix sums on coordinate compressed locations. To count the number of cows above and below a bounding box, we use rectangular sums to directly sum the frequency of cows in the column above a box.

Implementation

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

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

bool sort_by_x(const pair<int, int> &a, const pair<int, int> &b) {
	return a.first < b.first;
}
bool sort_by_y(const pair<int, int> &a, const pair<int, int> &b) {
	return a.second < b.second;
}