This is just a little humble blog post writing about solving this problem. Here’s the link if you want to give it a try.

Problem Statement

Art critics worldwide have only recently begun to recognize the creative genius behind the great bovine painter, Picowso.

Picowso paints in a very particular way. She starts with an \(N \times N\) blank canvas, represented by an \(N \times N\) grid of zeros, where a zero indicates an empty cell of the canvas. She then draws 9 rectangles on the canvas, one in each of 9 colors (conveniently numbered \(1 \dots 9\)). For example, she might start by painting a rectangle in color 2, giving this intermediate canvas:

She might then paint a rectangle in color 7:

And then she might paint a small rectangle in color 3:

Each rectangle has sides parallel to the edges of the canvas, and a rectangle could be as large as the entire canvas or as small as a single cell. Each color from \(0 \dots 9\) is used exactly once, although later colors might completely cover up some of the earlier colors.

Given the final state of the canvas, please count how many of the colors still visible on the canvas could have possibly been the first to be painted.

INPUT FORMAT (file art.in):

The first line of input contains \(N\), the size of the canvas (\(1 \leq N \leq 10\)). The next \(N\) lines describe the final picture of the canvas, each containing \(N\) numbers that are in the range \(0 \dots 9\). The input is guaranteed to have been drawn as described above, by painting successive rectangles in different colors.

OUTPUT FORMAT (file art.out):

Please output a count of the number of colors that could have been drawn first, from among all colors visible in the final canvas.

SAMPLE INPUT:

SAMPLE OUTPUT:

In this example, only color 2 could have been the first to be painted. Color 3 clearly had to have been painted after color 7, and color 7 clearly had to have been painted after color 2.

Problem credits: Brian Dean

Getting Started

All right, let’s break this bad boy down. So, we’re essentially given a canvas with a bunch of rectangles stacked on top of each other, and the goal is to determine which ones are could have been first. As seen in the example, only 2 could have been first. But why? If we’re only given the final product, how can we find possible candidates for the first rectangle?

One good strategy to use here is to find which rectangles are definitely not the first one. For example, below, we see that 3 is definitely not the first rectangle because it slices through the 7 rectangle, turning it into a U shape.

This insight is powerful yet so simple it sounds stupidly obvious: if a rectangle is on top of another rectangle, it’s not the first one. Taking it one step further, this property actually reveals all of the rectangles that are not the first one: “If a rectangle is on top of another rectangle, the rectangle cannot be the first one.“

Nice, but how do we determine whether a rectangle is on top of another one? Well, we saw before that the 3 rectangle cuts into the 7 rectangle, meaning that it was placed on top of it, meaning that it came after it! From this we can conclude that, in general,

Rectangle A comes after rectangle B if and only if rectangle A cuts into rectangle B.

All that’s left to do is formalize what we mean by one rectangle “cutting” into another rectangle. And this is pretty easy to define. Indeed, let’s start by finding the smallest possible shape that 7 could have taken on:

Let’s call this the bounding box for 7. Then, a rectangle can only come after 7 if part of it lands on top of this bounding box… such as 3!

This leads to another key observation: Rectangle A comes after Rectangle B if and only if part of rectangle A is in Rectangle B’s bounding box. And we’re in the final stretch of the problem before we get to writing some code!

Now that we’ve determined how to find the order between two rectangles, here’s how we can approach the problem: We can start off by assuming that all of the rectangles are candidates for the first one. In the example above, let’s put them all in a set {2, 3, 7}. Then, for each rectangle, such as 7 for example, we search for all of the possible “intruders” in 7's bounding box, in this case, 3. Because we now know that 3 came after 7, we can remove it from the set, so now we’re left with {2, 7}. We repeat the process and find that 7 came after 2, so now we only have {2}, meaning that 2 was the first rectangle!

Now let’s get to writing some code. The steps are as follows:

1. Collect all of the rectangle numbers present on the canvas.
2. Put all of the rectangle numbers on a set.
3. Loop through the set
    I. Find the bounding box of rectangle i.
    II. Look for intruders in the bounding box.
    III. Remove all intruders from the set.
4. Print the size of the set.

I’m not going to munch through the details, but here is my implementation in C++:

#include <bits/stdc++.h>

using namespace std;

int nxt() {
  int n; cin >> n; return n;
}

set<int> search_intruders(vector<vector<int>> &grid, int x1, int y1, int x2, int y2, int normal) {
  set<int> result;
  for (int y = y1; y <= y2; ++y) {
    for (int x = x1; x <= x2; ++x) {
      if (grid[y][x] != normal) result.insert(grid[y][x]);
    }
  }
  return result;
}

int main() {
  freopen("art.in", "r", stdin);
  freopen("art.out", "w", stdout);

  int n = nxt();
  vector<vector<int>> grid(n, vector<int>(n));
  set<int> remaining;

  // Initialize bounding box trackers
  vector<int> minX(10, n), maxX(10, -1), minY(10, n), maxY(10, -1);

  for (int y = 0; y < n; ++y) {
    string line; cin >> line;
    for (int x = 0; x < n; ++x) {
      int val = line[x] - '0';
      grid[y][x] = val;
      if (val == 0) continue;
      remaining.insert(val);
      minX[val] = min(minX[val], x);
      maxX[val] = max(maxX[val], x);
      minY[val] = min(minY[val], y);
      maxY[val] = max(maxY[val], y);
    }
  }

  for (int color = 1; color <= 9; ++color) {
    if (minX[color] > maxX[color]) continue; // Color not found
    set<int> intruders = search_intruders(grid, minX[color], minY[color], maxX[color], maxY[color], color);
    for (int intruder : intruders) {
      remaining.erase(intruder);
    }
  }

  cout << remaining.size() << endl;
  return 0;
}

And that finishes things; even though the problem has \( 1 \leq N \leq 10\) we solved it in \(O(N)\) time! Make sure to follow the blog - there’s a lot more coming in!

Solving the Modern Art Problem from USACO 2017 US Open Bronze Contest