USACO Silver 2019 February - Painting the Barn

Official Analysis (C++)

Explanation

We record for each rectangle its respective corner increments and decrements in an auxiliary two dimensional array.

We use a two dimensional difference array to drop “start” and “stop” markers at the corners of each paint rectangle, rather than coloring every square inside. When you later sweep through the grid with a cumulative sum from left to right and top to bottom, those corner markers automatically spread their increments into every cell inside the rectangle (and cancel out outside it). As you then scan across and down, you continually add up these markers so that every cell inside a rectangle ends up with exactly one extra coat and cells outside stay the same.

Then we run a two dimensional prefix sum over that array to rebuild the actual count of coats of paint in every cell. Finally, we scan the reconstructed grid and count how many cells have exactly the required number of coats.

Implementation

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

Copy
#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;

Copy
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];

Copy
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()]
		# Set up the prefix sums array with all the corners of the given rectangle
		barn[start_x][start_y] += 1
		barn[start_x][end_y] -= 1