Skip to Content
CTRL K

Painting the Barn

Análisis oficial (C++) 

Solución en video

Por Abhiraj Mallangi

Nota: La solución en video podría no ser la misma que las otras soluciones. Código en C++ y Java.

Video de YouTube (Chi8Ok-fdG0)

Solución

Explicación

Registramos para cada rectángulo sus incrementos y decrementos de esquina respectivos en un arreglo bidimensional auxiliar.

Usamos un arreglo de diferencias bidimensional para dejar marcadores de “inicio” y “parada” en las esquinas de cada rectángulo de pintura, en lugar de colorear cada casilla interior. Cuando luego recorremos la grilla con una suma acumulada de izquierda a derecha y de arriba a abajo, esos marcadores de esquina automáticamente expanden sus incrementos a cada celda dentro del rectángulo (y se cancelan fuera de él). Al escanear a lo ancho y hacia abajo, vamos sumando estos marcadores de modo que cada celda dentro de un rectángulo termina con exactamente una capa extra y las celdas de afuera se quedan igual.

Luego ejecutamos una suma de prefijos bidimensional sobre ese arreglo para reconstruir el conteo real de capas de pintura en cada celda. Finalmente, recorremos la grilla reconstruida y contamos cuántas celdas tienen exactamente el número requerido de capas.

Implementación

Complejidad temporal: O(Width2)\mathcal{O}(Width^2)

Del análisis oficial (con modificaciones menores):

#include <bits/stdc++.h>
 
using namespace std;
 
const int WIDTH = 1000;
 
int main() {
	freopen("paintbarn.in", "r", stdin);
	freopen("paintbarn.out", "w", stdout);
	int rect_num, paint_req;
	cin >> rect_num >> paint_req;
 
	int barn[WIDTH + 1][WIDTH + 1];
	for (int i = 0; i < rect_num; i++) {
		int start_x, start_y, end_x, end_y;
		cin >> start_x >> start_y >> end_x >> end_y;
		// Preparamos el arreglo de sumas de prefijos con todas las esquinas del
		// rectángulo dado
		barn[start_x][start_y]++;
		barn[start_x][end_y]--;
		barn[end_x][start_y]--;
		barn[end_x][end_y]++;
	}
 
	int valid_area = 0;
	// Ejecutamos sumas de prefijos 2D sobre el arreglo
	for (int x = 0; x < WIDTH; x++) {
		for (int y = 0; y < WIDTH; y++) {
			if (x > 0) barn[x][y] += barn[x - 1][y];
			if (y > 0) barn[x][y] += barn[x][y - 1];
			if (x > 0 && y > 0) barn[x][y] -= barn[x - 1][y - 1];
			valid_area += barn[x][y] == paint_req;
		}
	}
	cout << valid_area << endl;
}
import java.io.*;
import java.util.*;
 
public class PaintBarn {
	static final int WIDTH = 1000;
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("paintbarn");
		int rectNum = io.nextInt();
		int paintReq = io.nextInt();
		int[][] barn = new int[WIDTH + 1][WIDTH + 1];
 
		for (int i = 0; i < rectNum; i++) {
			int start_x = io.nextInt();
			int start_y = io.nextInt();
			int end_x = io.nextInt();
			int end_y = io.nextInt();
 
			// Preparamos el arreglo de sumas de prefijos con todas las esquinas del
			// rectángulo dado
			barn[start_x][start_y]++;
			barn[end_x][end_y]++;
			barn[start_x][end_y]--;
			barn[end_x][start_y]--;
		}
 
		int valid_area = 0;
		// Ejecutamos sumas de prefijos 2D sobre el arreglo
		for (int x = 0; x <= WIDTH; x++) {
			for (int y = 0; y <= WIDTH; y++) {
				if (x > 0) barn[x][y] += barn[x - 1][y];
				if (y > 0) barn[x][y] += barn[x][y - 1];
				if (x > 0 && y > 0) barn[x][y] -= barn[x - 1][y - 1];
				if (barn[x][y] == paintReq) { valid_area++; }
			}
		}
		io.println(valid_area);
		io.close();
	}
 
	// CodeSnip{Kattio}
}
WIDTH = 1000
 
barn = [[0 for _ in range(WIDTH + 1)] for _ in range(WIDTH + 1)]
with open("paintbarn.in") as read:
	rect_num, paint_req = [int(i) for i in read.readline().split()]
	for _ in range(rect_num):
		start_x, start_y, end_x, end_y = [int(i) for i in read.readline().split()]
		# Preparamos el arreglo de sumas de prefijos con todas las esquinas del rectángulo dado
		barn[start_x][start_y] += 1
		barn[start_x][end_y] -= 1
		barn[end_x][start_y] -= 1
		barn[end_x][end_y] += 1
 
valid_area = 0
# Ejecutamos sumas de prefijos 2D sobre el arreglo
for x in range(WIDTH + 1):
	for y in range(WIDTH + 1):
		if x > 0:
			barn[x][y] += barn[x - 1][y]
		if y > 0:
			barn[x][y] += barn[x][y - 1]
		if x > 0 and y > 0:
			barn[x][y] -= barn[x - 1][y - 1]
		valid_area += barn[x][y] == paint_req
 
print(valid_area, file=open("paintbarn.out", "w"))
Fundamentos