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]

以上就是關(guān)于【USACO 2020 December Contest, Silver Problem 2. Rectangular Pasture】的解答，如需了解學(xué)校/賽事/課程動態(tài)，可至翰林教育官網(wǎng)獲取更多信息。

往期文章閱讀推薦：

NOAI人工智能奧賽 2026-2027 活動章程出爐：新規(guī)則必看！

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動：留學(xué)申請的“核武器”來了！