Official Analysis (C++)

Solution

Explanation

First, notice that if two colors are overlapping, we know at least one of them cannot be the original rectangle.

For each color $c_1$, we can determine the limits of that color and consider its bounding rectangle. Any other color $c_2$ that appears inside this rectangle in the final grid must have been painted after $c_1$, and we can rule out $c_2$ as the first color painted.

We must notice that we always choose the smallest bounding rectangle as possible for each color $c_1$. This is because a larger rectangle creates more intersection between colors, which could elminate valid starting colors.

Implementation

Time Complexity: $\mathcal O(N^3)$

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

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

const int MAX_COLOR = 9;

Copy
import java.io.*;

public class Art {
	static final int MAX_COLOR = 9;

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

		/*

Copy
MAX_COLOR = 9

"""
Bounding boxes of each of the colors.
The first element won't be used (colors go from 1-9)
"""
left = [0] * (MAX_COLOR + 1)
right = [0] * (MAX_COLOR + 1)
down = [0] * (MAX_COLOR + 1)
up = [0] * (MAX_COLOR + 1)