APIO 2011 - Table Coloring

Explanation

TL;DR

If we view the grid as a graph, we get $K$ connected components. The answer is then either $2^{K - 1}$ or $0$ and we use DSU or DFS to determine which one it is.

Intuition

Let $c(x, y) = 1$ if the cell $(x, y)$ is blue and $0$ otherwise. For convenience, also add a row 0 and column 0.

Firstly, notice that if we already know the color of 3 cells in a $2 \times 2$ table, then we also know the last color.

From this, we get the recurrence

for all $x, y > 1$.

After analysing this recurrence, we find that we actually have

I made a helpful spreadsheet for you to visualise this.

Counting the colorings

Without loss of generality, let the cell $(0, 0)$ be red (since its color doesn't change the answer). This means that without any already-colored cells, all cells $(x, 0)$ and $(0, y)$ are independent.

However, an already-colored cell $(x, y)$ makes the 2 cells $(x, 0)$ and $(0, y)$ depend on each other.

View the grid as a graph:

• All cells $(x, 0)$ and $(0, y)$ are nodes.
• For each already-colored cell $(x, y)$, add an edge between $(x, 0)$ and $(0, y)$ with weight $c(x, 0) \oplus c(0, y)$.

This creates $K$ connected components. The answer is thus either $2^{K - 1}$ or $0$. This is because each node in a connected component is dependent on the other nodes in that component and all connected components are independent. If it simply isn't possible to color the table, the answer is $0$.

Checking Whether the Answer is $0$

This problem then becomes checking whether there is an cycle with odd weight in the resulting graph, which we can answer efficiently using DSU or DFS.

One way to implement this is as follows. Since each already-colored cell $(x, y)$ determines whether the colors of the cells $(x, 0)$ and $(0, y)$ are the same, we can instead split each node in our graph into 2 nodes (one for each color) and create edges between nodes with consistent colors. The answer is $0$ if two new nodes corresponding to the same original node are in the same connected component.

Implementation

Time Complexity: $\mathcal{O}((N+M+K)\log (N+M+K))$

Copy
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

const int MOD = 1e9;

int x[100001], y[100001], cmp[400001];

int find(int A) {
	while (A != cmp[A]) cmp[A] = cmp[cmp[A]], A = cmp[A];