Skip to Content
CTRL K

Table Coloring

Explicación

TL;DR

Si vemos la grilla como un grafo, obtenemos KK componentes conexas. La respuesta es entonces 2K−12^{K - 1} o 00, y usamos DSU o DFS para determinar cuál de las dos es.

Intuición

Sea c(x,y)=1c(x, y) = 1 si la celda (x,y)(x, y) es azul y 00 en caso contrario. Por conveniencia, también agregamos una fila 0 y una columna 0.

Primero, nótese que si ya conocemos el color de 3 celdas en una tabla 2×22 \times 2, también conocemos el último color.

De esto obtenemos la recurrencia

c(x,y)=¬(c(x−1,y−1)⊕c(x−1,y)⊕c(x,y−1)) c(x, y) = \lnot (c(x - 1, y - 1) \oplus c(x - 1, y) \oplus c(x, y - 1))

para todo x,y>1x, y > 1.

Tras analizar esta recurrencia, hallamos que en realidad tenemos

c(x,y)=(c(0,0)⊕c(0,y)⊕c(x,0)⊕((x⋅y)%2)) c(x, y) = (c(0, 0) \oplus c(0, y) \oplus c(x, 0) \oplus ((x \cdot y) \% 2))

Hice una hoja de cálculo útil  para visualizar esto.

Contar las coloraciones

Sin pérdida de generalidad, sea la celda (0,0)(0, 0) roja (porque su color no cambia la respuesta). Esto significa que, sin celdas ya coloreadas, todas las celdas (x,0)(x, 0) y (0,y)(0, y) son independientes.

Sin embargo, una celda ya coloreada (x,y)(x, y) hace que las 2 celdas (x,0)(x, 0) y (0,y)(0, y) dependan una de la otra.

Vemos la grilla como un grafo:

  • Todas las celdas (x,0)(x, 0) y (0,y)(0, y) son nodos.
  • Por cada celda ya coloreada (x,y)(x, y), agregamos una arista entre (x,0)(x, 0) y (0,y)(0, y) con peso c(x,0)⊕c(0,y)c(x, 0) \oplus c(0, y).

Esto crea KK componentes conexas. La respuesta es entonces 2K−12^{K - 1} o 00. Esto es porque cada nodo de una componente conexa depende de los demás nodos de esa componente y todas las componentes conexas son independientes. Si simplemente no es posible colorear la tabla, la respuesta es 00.

Comprobar si la respuesta es 00

Este problema se reduce entonces a comprobar si hay un ciclo de peso impar en el grafo resultante, lo que podemos responder de forma eficiente con DSU o DFS.

Una forma de implementar esto es la siguiente. Como cada celda ya coloreada (x,y)(x, y) determina si los colores de las celdas (x,0)(x, 0) y (0,y)(0, y) son iguales, en su lugar podemos partir cada nodo de nuestro grafo en 2 nodos (uno por cada color) y crear aristas entre nodos con colores consistentes. La respuesta es 00 si dos nodos nuevos correspondientes al mismo nodo original están en la misma componente conexa.

Implementación

Complejidad temporal: O((N+M+K)log⁡(N+M+K))\mathcal{O}((N+M+K)\log (N+M+K))

#include <algorithm>
#include <iostream>
#include <vector>
 
const int MOD = 1e9;
 
// BeginCodeSnip{DSU (from the module)}
class DisjointSets {
  private:
	std::vector<int> parents;
	std::vector<int> sizes;
 
  public:
	DisjointSets(int size) : parents(size), sizes(size, 1) {
		for (int i = 0; i < size; i++) { parents[i] = i; }
	}
 
	/** @return el nodo "representante" de la componente de x */
	int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }
 
	/** @return si la fusión cambió la conectividad */
	bool unite(int x, int y) {
		int x_root = find(x);
		int y_root = find(y);
		if (x_root == y_root) { return false; }
 
		if (sizes[x_root] < sizes[y_root]) { std::swap(x_root, y_root); }
		sizes[x_root] += sizes[y_root];
		parents[y_root] = x_root;
		return true;
	}
};
// EndCodeSnip
 
int main() {
	int n, m, k;
	std::cin >> n >> m >> k;
	DisjointSets dsu(2 * (n + m));
 
	for (int i = 0; i < k; i++) {
		int x, y, c;
		std::cin >> x >> y >> c;
		x--, y--;
		c ^= (x & 1) && (y & 1);
 
		if (c) {
			dsu.unite(x, y + n);
			dsu.unite(x + m + n, y + 2 * n + m);
		} else {
			dsu.unite(x + m + n, y + n);
			dsu.unite(x, y + 2 * n + m);
		}
	}
 
	int valid_components = -1;
	for (int i = 0; i < n + m; i++) {
		if (dsu.find(i) == dsu.find(i + n + m)) { return std::cout << "0", 0; }
		if (dsu.find(i) == i) { valid_components++; }
	}
 
	int ans = 1;
	for (int i = 0; i < valid_components; i++) { ans = (ans * 2) % MOD; }
	std::cout << ans << '\n';
}
import java.io.*;
import java.util.*;
 
public class TableColoring {
	static final int MOD = 1000000000;
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int n = io.nextInt();
		int m = io.nextInt();
		int k = io.nextInt();
 
		DisjointSets dsu = new DisjointSets(2 * (n + m));
 
		for (int i = 0; i < k; i++) {
			int x = io.nextInt() - 1;
			int y = io.nextInt() - 1;
			int c = io.nextInt();
 
			c ^= ((x & 1) != 0 && (y & 1) != 0) ? 1 : 0;
 
			if (c == 1) {
				dsu.unite(x, y + n);
				dsu.unite(x + m + n, y + 2 * n + m);
			} else {
				dsu.unite(x + m + n, y + n);
				dsu.unite(x, y + 2 * n + m);
			}
		}
 
		int validComponents = -1;
		for (int i = 0; i < n + m; i++) {
			if (dsu.find(i) == dsu.find(i + n + m)) {
				io.println(0);
				io.close();
			}
 
			if (dsu.find(i) == i) { validComponents += 1; }
		}
 
		int ans = 1;
		for (int i = 0; i < validComponents; i++) { ans = ((ans * 2) % MOD) % MOD; }
 
		io.println(ans);
		io.close();
	}
 
	// CodeSnip{Kattio}
}
 
// BeginCodeSnip{DSU (from the module)}
class DisjointSets {
	int[] parents;  // indexación desde cero
	int[] sizes;
 
	public DisjointSets(int size) {
		parents = new int[size];
		sizes = new int[size];
		for (int i = 0; i < size; i++) {
			parents[i] = i;
			sizes[i] = 1;
		}
	}
 
	/** @return el nodo "representante" de la componente de x */
	public int find(int x) {
		return parents[x] == x ? x : (parents[x] = find(parents[x]));
	}
 
	/** @return si la fusión cambió la conectividad */
	public boolean unite(int x, int y) {
		int xRoot = find(x);
		int yRoot = find(y);
		if (xRoot == yRoot) { return false; }
 
		if (sizes[xRoot] < sizes[yRoot]) { return unite(yRoot, xRoot); }
		parents[yRoot] = xRoot;
		sizes[xRoot] += sizes[yRoot];
		return true;
	}
}
// EndCodeSnip
import sys
 
MOD = 10**9
 
# BeginCodeSnip{DSU (from the module)}
class DisjointSets:
	def __init__(self, size: int) -> None:
		self.parents = [i for i in range(size)]
		self.sizes = [1 for _ in range(size)]
 
	def find(self, x: int) -> int:
		""":return: el nodo "representante" de la componente de x"""
		if self.parents[x] == x:
			return x
		self.parents[x] = self.find(self.parents[x])
		return self.parents[x]
 
	def unite(self, x: int, y: int) -> bool:
		""":return: si la fusión cambió la conectividad"""
		x_root = self.find(x)
		y_root = self.find(y)
		if x_root == y_root:
			return False
 
		if self.sizes[x_root] < self.sizes[y_root]:
			x_root, y_root = y_root, x_root
 
		self.parents[y_root] = x_root
		self.sizes[x_root] += self.sizes[y_root]
		return True
 
 
# EndCodeSnip
 
n, m, k = map(int, input().split())
 
dsu = DisjointSets(2 * (n + m))
for i in range(k):
	x, y, c = map(int, input().split())
	x -= 1
	y -= 1
	c ^= (x & 1) and (y & 1)
 
	if c:
		dsu.unite(x, y + n)
		dsu.unite(x + m + n, y + 2 * n + m)
	else:
		dsu.unite(x + m + n, y + n)
		dsu.unite(x, y + 2 * n + m)
 
valid_components = -1
for i in range(n + m):
	if dsu.find(i) == dsu.find(i + n + m):
		print(0)
		sys.exit()
 
	if dsu.find(i) == i:
		valid_components += 1
 
ans = 1
for _ in range(valid_components):
	ans = (ans * 2) % MOD
 
print(ans)
Fundamentos