Rectangular Pasture

Análisis oficial (C++)

Solución en video 1

Por Kyle Xu

Nota: la solución en video puede no ser la misma que las demás soluciones. Código en C++ y Java.

Video de YouTube (1rZqkPkXVYk)

Solución en video 2

Video de YouTube (AH1wyxq8nPM)

Solución 1

Explicación

Analicemos un poco más el caso de ejemplo:

La cota $N \leq 2500$ sugiere una complejidad de $\mathcal{O}(N^2)$ , así que intentemos pensar este problema desde la perspectiva de cada par de vacas.

Nótese que para cualquier par de vacas siempre podemos crear una caja única, con una vaca en una esquina y la otra en la esquina opuesta.

Podemos hacer esto porque el problema estipula que todas las posiciones x e y son distintas. Si no lo fueran, podríamos formar la misma caja con dos pares distintos de puntos de esta forma:

Dibujando las cajas creadas por esta observación, ahora tenemos las siguientes cajas:

Esto solo nos da $6$ rectángulos, que es menos que la respuesta real. La razón es que no hemos tenido en cuenta las cajas en las que hay solo uno o ningún punto en las esquinas. Afortunadamente, podemos construir tales rectángulos a partir de los que ya tenemos expandiendo el borde superior y/o inferior para incluir cualquier vaca que no estuviera inicialmente incluida en la cerca.

Más concretamente, si $a$ es la cantidad de vacas por encima de la caja acotante inicial y $b$ es la cantidad de vacas por debajo, hay $(a+1)(b+1)$ cajas acotantes distintas desde la perspectiva de la caja inicial. El $+1$ es porque una opción es simplemente no incluir ninguna vaca por encima y/o por debajo de la caja.

Usando el método de construcción descrito arriba, ahora podemos tener las siguientes cajas adicionales:

Sin embargo, si recorremos todas las vacas para hallar cuántas hay por encima y por debajo de una caja acotante, obtendríamos una complejidad de $\mathcal{O}(N^3)$ , ya que ya estamos recorriendo todos los pares de vacas. Por tanto, necesitamos un método en tiempo constante para hallar cuántas vacas están por encima o por debajo de una cierta coordenada y y también entre dos ciertas coordenadas x.

Esto es posible con sumas de prefijos. Para cada coordenada y en la que hay una vaca, recorremos todas las vacas en orden de coordenada x y construimos dos arreglos de sumas de prefijos para la coordenada y dada: uno para cuántas vacas hay por encima de la coordenada y otro para cuántas hay por debajo. ¡Ahora tenemos nuestro método en tiempo constante!

Nótese, sin embargo, que nuestros $6+2=8$ rectángulos siguen quedando cortos de los $13$ estipulados. Esto se debe a que no hemos tenido en cuenta los casos en los que FJ encierra una sola vaca o ninguna. Por tanto, hay que sumar $N+1$ a nuestro subtotal, lo que en nuestro caso nos da los $4+1=5$ conjuntos extra necesarios.

Implementación

Complejidad temporal: $\mathcal{O}(N^2)$

C++Java


#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <set>
#include <vector>
 
using namespace std;
 
int main() {
	int cow_num;
	cin >> cow_num;
 
	set<int> seen_x, seen_y;
	vector<pair<int, int>> cows(cow_num);
	for (pair<int, int> &c : cows) {
		cin >> c.first >> c.second;
		assert(!(seen_x.count(c.first) || seen_y.count(c.second)));
		seen_x.insert(c.first);
		seen_y.insert(c.second);
	}
 
	// hacemos un poco de compresión de coordenadas
	sort(cows.begin(), cows.end());  // ordenar por x
	map<int, int> reduced_x;
	for (int c = 0; c < cow_num; c++) { reduced_x[cows[c].first] = c; }
 
	auto cmp = [&](const pair<int, int> &c1, const pair<int, int> &c2) {
		return c1.second < c2.second;
	};
	sort(cows.begin(), cows.end(), cmp);  // ordenar por y
	map<int, int> reduced_y;
	for (int c = 0; c < cow_num; c++) { reduced_y[cows[c].second] = c; }
 
	for (auto &[x, y] : cows) {
		x = reduced_x[x];
		y = reduced_y[y];
	}
 
	// ordenar de nuevo por x
	sort(cows.begin(), cows.end());
	// construir nuestras sumas de prefijos para las líneas y
	vector<vector<int>> lt_y(cow_num, vector<int>(cow_num + 1));
	vector<vector<int>> gt_y(cow_num, vector<int>(cow_num + 1));
	for (int c = 0; c < cow_num; c++) {
		int curr_y = cows[c].second;
		for (int x = 1; x <= cow_num; x++) {
			lt_y[curr_y][x] = (lt_y[curr_y][x - 1] + (cows[x - 1].second < curr_y));
			gt_y[curr_y][x] = (gt_y[curr_y][x - 1] + (cows[x - 1].second > curr_y));
		}
	}
 
	long long total = 0;
	for (int c1 = 0; c1 < cow_num; c1++) {
		for (int c2 = c1 + 1; c2 < cow_num; c2++) {
			int bottom = min(cows[c1].second, cows[c2].second);
			int top = max(cows[c1].second, cows[c2].second);
 
			int bottom_total = 1 + lt_y[bottom][c2 + 1] - lt_y[bottom][c1];
			int top_total = 1 + gt_y[top][c2 + 1] - gt_y[top][c1];
			total += (long long)bottom_total * top_total;
		}
	}
 
	/*
	 * no contamos las cajas en las que fj encierra
	 * o bien una sola vaca o bien ninguna
	 */
	total += cow_num + 1;
 
	cout << total << endl;
}


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<>();
		Set<Integer> seenY = new HashSet<>();
		int[][] cows = new int[cowNum][2];
		for (int c = 0; c < cowNum; c++) {
			StringTokenizer cow = new StringTokenizer(read.readLine());
			cows[c][0] = Integer.parseInt(cow.nextToken());
			cows[c][1] = Integer.parseInt(cow.nextToken());
			assert !(seenX.contains(cows[c][0]) || seenY.contains(cows[c][1]));
			seenX.add(cows[c][0]);
			seenY.add(cows[c][1]);
		}
 
		// hacemos un poco de compresión de coordenadas
		Arrays.sort(cows, Comparator.comparingInt(c -> c[0]));  // ordenar por x
		Map<Integer, Integer> reducedX = new HashMap<>();
		for (int c = 0; c < cowNum; c++) { reducedX.put(cows[c][0], c); }
 
		Arrays.sort(cows, Comparator.comparingInt(c -> c[1]));  // ordenar por y
		Map<Integer, Integer> reducedY = new HashMap<>();
		for (int c = 0; c < cowNum; c++) { reducedY.put(cows[c][1], c); }
 
		for (int c = 0; c < cowNum; c++) {
			cows[c][0] = reducedX.get(cows[c][0]);
			cows[c][1] = reducedY.get(cows[c][1]);
		}
 
		// ordenar de nuevo por x
		Arrays.sort(cows, Comparator.comparingInt(c -> c[0]));
		// construir nuestras sumas de prefijos para las líneas y
		int[][] ltY = new int[cowNum][cowNum + 1];
		int[][] gtY = new int[cowNum][cowNum + 1];
		for (int c = 0; c < cowNum; c++) {
			int currY = cows[c][1];
			for (int x = 1; x <= cowNum; x++) {
				ltY[currY][x] = (ltY[currY][x - 1] + (cows[x - 1][1] < currY ? 1 : 0));
				gtY[currY][x] = (gtY[currY][x - 1] + (cows[x - 1][1] > currY ? 1 : 0));
			}
		}
 
		long total = 0;
		for (int c1 = 0; c1 < cowNum; c1++) {
			for (int c2 = c1 + 1; c2 < cowNum; c2++) {
				int bottom = Math.min(cows[c1][1], cows[c2][1]);
				int top = Math.max(cows[c1][1], cows[c2][1]);
 
				int bottomTotal = 1 + ltY[bottom][c2 + 1] - ltY[bottom][c1];
				int topTotal = 1 + gtY[top][c2 + 1] - gtY[top][c1];
				total += (long)bottomTotal * topTotal;
			}
		}
 
		/*
		 * no contamos las cajas en las que fj encierra
		 * o bien una sola vaca o bien ninguna
		 */
		total += cowNum + 1;
 
		System.out.println(total);
	}
}

Solución 2

Explicación

La idea central de esta solución es idéntica a la anterior, pero difiere en cómo contamos las vacas por encima y por debajo de una caja acotante.

En lugar de mantener dos sumas de prefijos para la cantidad de vacas por encima y por debajo de una coordenada y, usamos directamente sumas de prefijos 2D sobre las posiciones con coordenadas comprimidas. Para contar las vacas por encima y por debajo de una caja acotante, usamos sumas rectangulares para sumar directamente la frecuencia de vacas en la columna por encima de una caja.

Implementación

Complejidad temporal: $\mathcal{O}(N^2)$

C++


#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;
}
 
int rect_sum(const vector<vector<int>> &grid, int r1, int r2, int c1, int c2) {
	return (grid[r2][c2] - grid[r2][c1 - 1] - grid[r1 - 1][c2] + grid[r1 - 1][c1 - 1]);
}
 
int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> nums(n);
	for (auto &[x, y] : nums) { cin >> x >> y; }
 
	// comprimir coordenadas X
	sort(nums.begin(), nums.end(), sort_by_x);
	for (int i = 0; i < nums.size(); i++) { nums[i].first = i + 1; }
 
	// comprimir coordenadas Y
	sort(nums.begin(), nums.end(), sort_by_y);
	for (int i = 0; i < nums.size(); i++) { nums[i].second = i + 1; }
 
	// la grilla es n+1 por n+1 porque las posiciones están indexadas desde 1
	vector<vector<int>> grid(n + 1, vector<int>(n + 1));
 
	// añadir puntos a la grilla y calcular sumas de prefijos 2D
	for (auto [x, y] : nums) { grid[x][y] = 1; }
 
	for (int i = 1; i < grid.size(); i++) {
		for (int j = 1; j < grid[i].size(); j++) {
			grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1];
		}
	}
 
	// elegir dos puntos, contar rectángulos
	sort(nums.begin(), nums.end(), sort_by_x);
	long long res = 0;
 
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int r1 = nums[i].first;
			int r2 = nums[j].first;
			int c1 = min(nums[i].second, nums[j].second);
			int c2 = max(nums[i].second, nums[j].second);
 
			int above = rect_sum(grid, 1, r1 - 1, c1, c2);
			int below = rect_sum(grid, r2 + 1, n, c1, c2);
 
			res += 1ll * (above + 1) * (below + 1);
		}
	}
 
	// sumar resultados de una sola vaca o ninguna
	res += n + 1;
 
	cout << res << '\n';
}