Home » 国际竞赛 » Details

USACO 2020 December Contest, Silver Problem 2. Rectangular Pasture

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日下午3:32

USACO 2020 December Contest, Silver Problem 2. Rectangular Pasture

Farmer John's largest pasture can be regarded as a large 2D grid of square "cells" (picture a huge chess board). Currently, there are $N$ cows occupying some of these cells ( $1 \leq N \leq 2500$ ).

Farmer John wants to build a fence that will enclose a rectangular region of cells; the rectangle must be oriented so its sides are parallel with the $x$ and $y$ axes, and it could be as small as a single cell. Please help him count the number of distinct subsets of cows that he can enclose in such a region. Note that the empty subset should be counted as one of these.

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

The first line contains a single integer $N$ . Each of the next $N$ lines Each of the next $N$ lines contains two space-separated integers, indicating the $(x, y)$ coordinates of a cow's cell. All $x$ coordinates are distinct from each-other, and all $y$ coordinates are distinct from each-other. All $x$ and $y$ values lie in the range $0 \dots 10^{9}$ .

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

The number of subsets of cows that FJ can fence off. It can be shown that this quantity fits within a signed 64-bit integer (e.g., a "long long" in C/C++).

SAMPLE INPUT:

SAMPLE OUTPUT:

There are $2^{4}$ subsets in total. FJ cannot create a fence enclosing only cows 1, 2, and 4, or only cows 2 and 4, or only cows 1 and 4, so the answer is $2^{4} - 3 = 16 - 3 = 13$ .

SCORING:

Test cases 2-3 satisfy $N \leq 20$ .
Test cases 4-6 satisfy $N \leq 100$ .
Test cases 7-12 satisfy $N \leq 500$ .
Test cases 13-20 satisfy no additional constraints.

Problem credits: Benjamin Qi

USACO 2020 December Contest, Silver Problem 2. Rectangular Pasture 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

First, compress all of the $x$ and $y$ coordinates so that everything is in the range $[0, N - 1]$ .

For each nonempty subset of cows that can be fenced off, consider the rectangle of the minimum size that encloses the subset. This rectangle must contain a cow on each of its four sides. Conversely, each rectangle with a cow on each of its sides corresponds to a unique subset of cows that can be fenced off. Due to the condition that all coordinates are distinct, each side will contain exactly one cow.

A naive approach would be to test whether each of the $O (N^{4})$ possible rectangles satisfies this condition, giving an $O (N^{5})$ time solution. For additional an $O (N^{4})$ time solution, check each rectangle in $O (1)$ time.

For full credit, we need an $O (N^{2})$ solution. Suppose that we fix the cows $a = (x_{a}, y_{a})$ and $b = (x_{b}, y_{b})$ on the bottom and top sides of the rectangle (so $y_{a} \leq y_{b}$ ). Then the cow $c$ on the left side of the rectangle must satisfy $x_{c} \leq min (x_{a}, x_{b})$ and $y_{a} \leq y_{c} \leq y_{b}$ . Similarly, the cow $d$ on the right side of the rectangle must satisfy $max (x_{a}, x_{b}) \leq x_{d}$ and $y_{a} \leq y_{d} \leq y_{b}$ . In other words, the number of possibilities for $c$ is the number of points in the rectangle $[0, min (x_{a}, x_{b})] \times [y_{a}, y_{b}]$ while the number of possibilities for $d$ is the number of cows in the rectangle $[max (x_{a}, x_{b}), N - 1] \times [y_{a}, y_{b}]$ . We can compute these quantities using 2D prefix sums.

Brian Dean's code:

#include <iostream>
#include <algorithm>
using namespace std;
 
typedef pair<int,int> Point;
bool ycomp(Point p, Point q) { return p.second < q.second; }
 
const int MAX_N = 2500;
int N, Psum[MAX_N+1][MAX_N+1];
Point P[MAX_N];
 
int rsum(int x1, int y1, int x2, int y2)
{
  return Psum[x2+1][y2+1] - Psum[x2+1][y1] - Psum[x1][y2+1] + Psum[x1][y1];
}
 
int main(void)
{
  cin >> N;
  for (int i=0; i<N; i++) {
    int x, y;
    cin >> x >> y;
    P[i] = make_pair(x,y);
  }
  sort(P, P+N); 
  for (int i=0; i<N; i++) P[i].first = i+1;
  sort(P, P+N, ycomp); 
  for (int i=0; i<N; i++) P[i].second = i+1;
  for (int i=0; i<N; i++) Psum[P[i].first][P[i].second] = 1;
  for (int i=1; i<=N; i++)
    for (int j=1; j<=N; j++)
      Psum[i][j] += Psum[i-1][j] + Psum[i][j-1] - Psum[i-1][j-1];
  long long answer = 0;
  for (int i=0; i<N; i++) 
    for (int j=i; j<N; j++) {
      int x1 = min(P[i].first, P[j].first) - 1;
      int x2 = max(P[i].first, P[j].first) - 1;
      answer += rsum(0,i,x1,j) * rsum(x2,i,N-1,j);
    }
  cout << answer + 1 << "\n";
  
}

Danny Mittal's code:

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
 
public class RectangularPasture {
    static int[][] sums;
 
    static int getSum(int fromX, int toX, int fromY, int toY) {
        return sums[toX][toY] - sums[fromX - 1][toY] - sums[toX][fromY - 1] + sums[fromX - 1][fromY - 1];
    }
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] xs = new int[n];
        int[] ys = new int[n];
        Integer[] cows = new Integer[n];
        for (int j = 0; j < n; j++) {
            xs[j] = in.nextInt();
            ys[j] = in.nextInt();
            cows[j] = j;
        }
        Arrays.sort(cows, Comparator.comparingInt(j -> xs[j]));
        for (int x = 1; x <= n; x++) {
            xs[cows[x - 1]] = x;
        }
        Arrays.sort(cows, Comparator.comparingInt(j -> ys[j]));
        for (int y = 1; y <= n; y++) {
            ys[cows[y - 1]] = y;
        }
        sums = new int[n + 1][n + 1];
        for (int j = 0; j < n; j++) {
            sums[xs[j]][ys[j]]++;
        }
        for (int x = 0; x <= n; x++) {
            for (int y = 0; y <= n; y++) {
                if (x > 0) {
                    sums[x][y] += sums[x - 1][y];
                }
                if (y > 0) {
                    sums[x][y] += sums[x][y - 1];
                }
                if (x > 0 && y > 0) {
                    sums[x][y] -= sums[x - 1][y - 1];
                }
            }
        }
        long answer = n + 1;
        for (int j = 0; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                answer += getSum(Math.min(xs[j], xs[k]), Math.max(xs[j], xs[k]), 1, Math.min(ys[j], ys[k]))
                        * getSum(Math.min(xs[j], xs[k]), Math.max(xs[j], xs[k]), Math.max(ys[j], ys[k]), n);
            }
        }
        System.out.println(answer);
    }
}

[/hide]