APIO 2011 - Table Coloring

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)$.

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$

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 we know must be the same color.

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

Complexity

Time: $\mathcal{O}(N)$.

Memory: $\mathcal{O}(N)$.

Code

1#include <bits/stdc++.h>
2#define FOR(i, x, y) for (int i = x; i < y; i++)
3typedef long long ll;
4using namespace std;
5
6const int MOD = 1e9;
7
8int x[100001], y[100001], cmp[400001];
9
10int find(int A) {