USACO Platinum 2017 US Open - Modern Art

Official Editorial (C++)

Explanation

Initial Observation

There's just one small observation we should make before continuing with the actual problem, and it's that given the final canvas, it's optimal to assume that each color takes up only the minimum rectangle needed to cover the cells that are shown.

For example, if only these blue cells are present in the canvas:

It's best to think that this is the rectangle Picowso painted:

Analysis

The main issue with this problem is finding out which rectangles must overlap other rectangles, because as long as we know that color A overlaps color B, then color A can't possibly have been painted first.

However, we can't iterate through all pairs of colors, since that would result in a complexity of at least $\mathcal{O}(N^4)$. Since that rules out considering things from the colors' angle, why not try considering it from each canvas cell's angle?

Given the observation we made, we know the bounding box of each rectangle. Thus, with prefix sums, it's possible for us to figure out how many rectangles have been painted on a single cell.

With this, we can construct our answer with the fact that if a cell has more than 2 rectangles painted over it, than the color shown in the given painting can't possibly have been painted first. Thus, we keep a set of all colors shown and update it accordingly, removing a color that's found to overlap some other color. All colors not shown in the final canvas could have been painted first.

Implementation

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

Copy
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

Copy
import java.io.*;
import java.util.*;

public class Art {
 	Code Snippet: Color Rectangle Bound Class (Click to expand)

	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("art.in"));

		int width = Integer.parseInt(read.readLine());

Copy
class Bound:
	def __init__(self, min_r: int, max_r: int, min_c: int, max_c: int):
		self.min_r = min_r
		self.max_r = max_r
		self.min_c = min_c
		self.max_c = max_c


with open("art.in") as read:
	width = int(read.readline().strip())