Official Analysis (C++)

Explanation

Any rectangle with sides parallel to the grid is uniquely defined by its top-left and bottom-right corners. There are $\mathcal{O}(N^2)$ choices for the top-left corner and $\mathcal{O}(N^2)$ choices for the bottom-right corner, resulting in $\mathcal{O}(N^4)$ total rectangles. Since $N$ is at most $20$, an $\mathcal{O}(N^6)$ algorithm is efficient enough to solve the problem within the constraints. To achieve this, we require $\mathcal{O}(N^2)$ work to determine whether each rectangle is a PCL.

Since there are $\mathcal{O}(N^4)$ total rectangles, there are $\mathcal{O}(N^8)$ total possible rectangle pairs. However, this realistically is not the number of PCL pairs and therefore our solution will still pass.

To check whether a rectangle is a PCL, we use a flood-fill algorithm. For each rectangle, we count the number of connected components for each color within its bounds. A rectangle qualifies as a PCL if it contains exactly two colors, with one color forming a single connected component and the other forming two or more connected components. By setting bounds for the flood-fill and skipping already-visited cells, we ensure that each cell in the rectangle is processed only once, leading to $\mathcal{O}(N^2)$ work per rectangle.

Once all candidate PCLs are identified, we need to ensure no PCL is nested within another. Rather than using clever ordering, we handle this with a straightforward approach: for each identified PCL, we check whether it is completely contained within any other PCL. Since the number of valid PCLs is significantly smaller than the total number of rectangles as invalid rectangles are discarded early, this approach remains efficient.

Implementation

Time Complexity: $\mathcal{O}(N^6+P^2)$, where $P$ is the number of PCLs in the input.

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 20;
vector<vector<char>> image(MAX_N, vector<char>(MAX_N));
vector<vector<bool>> visited(MAX_N, vector<bool>(MAX_N));

/** PCL delimited by the top left corner (i1, j1) & bottom right corner (i2, j2) */
struct PCL {
	int i1, j1;

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

public class Where {
	static final int MAX_N = 20;

	static char[][] image = new char[MAX_N][MAX_N];
	static boolean[][] visited = new boolean[MAX_N][MAX_N];

	static int iMin, iMax, jMin, jMax;

Copy
from typing import List

MAX_N = 20


class PCL:
	def __init__(self, i1: int, j1: int, i2: int, j2: int):
		self.i1 = i1
		self.j1 = j1
		self.i2 = i2