DP con máscaras de bits

DP con máscaras de bits

Tutorial

Solución

Sea $dp[S][i]$ la cantidad de rutas que visitan todas las ciudades del subconjunto $S$ y terminan en la ciudad $i$. Las transiciones serán entonces:

donde $S \setminus \{i\}$ es el subconjunto $S$ sin la ciudad $i$.

Complejidad temporal: $\mathcal{O}(2^N \cdot N^2)$

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const int MAX_N = 20;
const ll MOD = (ll)1e9 + 7;
 
ll dp[1 << MAX_N][MAX_N];
// come_from[i] contiene las ciudades que pueden volar a i
vector<int> come_from[MAX_N];
 
int main() {
	int city_num;
	int flight_num;
	cin >> city_num >> flight_num;
	for (int f = 0; f < flight_num; f++) {
		int start, end;
		cin >> start >> end;
		come_from[--end].push_back(--start);
	}
 
	dp[1][0] = 1;
	for (int s = 2; s < 1 << city_num; s++) {
		// solo considerar subconjuntos que tienen la primera ciudad
		if ((s & (1 << 0)) == 0) continue;
		// además, solo considerar subconjuntos con la última ciudad si es el subconjunto completo
		if ((s & (1 << (city_num - 1))) && s != ((1 << city_num) - 1)) continue;
 
		for (int end = 0; end < city_num; end++) {
			if ((s & (1 << end)) == 0) continue;
 
			// el subconjunto que no incluye el end actual
			int prev = s - (1 << end);
			for (int j : come_from[end]) {
				if ((s & (1 << j))) {
					dp[s][end] += dp[prev][j];
					dp[s][end] %= MOD;
				}
			}
		}
	}
	cout << dp[(1 << city_num) - 1][city_num - 1] << '\n';
}

import sys
 
MOD = 10**9 + 7
 
input = sys.stdin.readline
 
n, m = map(int, input().strip().split())
dp = [[0 for _ in range(n)] for _ in range(1 << n)]
dp[1][0] = 1
 
adj = [[] for _ in range(n)]
for i in range(m):
	a, b = map(int, input().strip().split())
	adj[b - 1].append(a - 1)
 
for cities in range(1, 1 << n):
	# solo considerar ciudades que incluyen la primera ciudad
	if not cities & 1:
		continue
 
	# solo considerar subconjuntos con la última ciudad si es el subconjunto completo
	if cities & (1 << n - 1) and cities != (1 << n) - 1:
		continue
 
	# recorrer posibles ciudades de llegada
	for end in range(1, n):
		if not cities & (1 << end):
			continue
 
		prev_cities = cities ^ (1 << end)
		for prev_end in adj[end]:
			if not prev_cities & (1 << prev_end):
				continue
			dp[cities][end] += dp[prev_cities][prev_end]
			dp[cities][end] %= MOD
 
print(dp[(1 << n) - 1][n - 1])

Fusionar subconjuntos

En algunos problemas, para un conjunto $S$, no alcanza con transicionar desde $S \setminus \{i\}$. En cambio, hace falta transicionar desde todos los subconjuntos estrictos de $S$.

Aunque pueda parecer que hay que hacer $\mathcal{O}(2^N \cdot 2^N) = \mathcal{O}(4^N)$ transiciones, ¡en realidad solo hay $\mathcal{O}(3^N)$ transiciones!

Para ver por qué, contemos la cantidad de pares ordenados $(T, S)$ donde $T \subset S$. En lugar de contar de forma directa, nótese que cada elemento $x$ está en una de estas situaciones:

1. En $T$ y en $S$
2. En ninguno
3. En $S$ pero no en $T$. Si $x$ está en $T$ pero no en $S$, $T$ no es un subconjunto válido.

Dado que cada elemento puede estar en tres estados posibles, la complejidad total es en realidad $\mathcal{O}(3^N)$.

Para implementar esto, podemos usar algunos trucos bit a bit:

for (int mask = 0; mask < (1 << n); mask++) {
	for (int submask = mask; submask != 0; submask = (submask - 1) & mask) {
		int subset = mask ^ submask;
		// hacer lo que se necesite aquí
	}
}

Cuando restamos $1$ de $\texttt{submask}$, el bit más a la derecha se invierte a $0$ y todos los bits a su derecha se vuelven $1$. Aplicar el AND bit a bit con $\texttt{mask}$ saca todos los bits extra que no están en $\texttt{mask}$. Con este proceso podemos obtener todos los subconjuntos estrictos en orden creciente calculando $\texttt{mask} \oplus \texttt{submask}$, que hace resta de conjuntos.

Explicación

El objetivo de este problema es particionar los nodos en conjuntos tales que los nodos de cada conjunto formen un grafo completo. Sea $\texttt{dp}[S]$ la cantidad mínima de particiones tales que en cada partición el grafo formado es un grafo completo.

Primero podemos hallar qué conjuntos $T$ forman un grafo completo, fijando $\texttt{dp}[T]$ en $1$ e $\infty$ en caso contrario. Esto se puede hacer de forma naive en $\mathcal{O}(2^N \cdot N^2)$ o $\mathcal{O}(2^N \cdot N)$ representando la lista de adyacencia como una máscara de bits y usando manipulación de bits para ver si un conjunto de nodos es un grafo completo.

Luego podemos transicionar así:

Implementación

Complejidad temporal: $\mathcal{O}(3^N + 2^N \cdot N)$

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n, m;
	cin >> n >> m;
	vector<int> adj(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		// lista de adyacencia representada como máscara de bits
		adj[u] |= (1 << v);
		adj[v] |= (1 << u);
	}
 
	vector<int> dp(1 << n, INT32_MAX);
	for (int mask = 0; mask < (1 << n); mask++) {
		bool connected = true;
		for (int u = 0; u < n; u++) {
			if (((mask >> u) & 1) != 0) {
				// comprobar si u está conectado a todos los demás nodos de mask
				if (((adj[u] | (1 << u)) & mask) != mask) {
					connected = false;
					break;
				}
			}
		}
 
		if (connected) { dp[mask] = 1; }
	}
 
	for (int mask = 0; mask < (1 << n); mask++) {
		for (int submask = mask; submask; submask = (submask - 1) & mask) {
			int subset = mask ^ submask;
			// submask tiene todo lo de mask que no está en subset
			if (dp[subset] != INT32_MAX && dp[submask] != INT32_MAX) {
				dp[mask] = min(dp[mask], dp[subset] + dp[submask]);
			}
		}
	}
 
	cout << dp[(1 << n) - 1] << endl;
}

Problemas

Aplicación: máscaras de bits sobre primos

Idea general

En algunos problemas de teoría de números, ayuda representar cada número con una máscara de bits de sus divisores primos. Por ejemplo, el conjunto $\{6, 10, 15 \}$ se puede representar por $\{0b011, 0b101, 0b110 \}$ (en binario)^{El prefijo $0b$ simplemente indica que el número es binario}, donde los bits corresponden a divisibilidad por $[2, 3, 5]$.

Entonces, estas son algunas operaciones equivalentes entre máscaras y estos enteros:

• AND bit a bit es GCD
• OR bit a bit es LCM
• Iterar sobre bits es iterar sobre divisores primos
• Iterar sobre submáscaras es iterar sobre divisores Elegir un conjunto con GCD $1$ es equivalente a elegir un conjunto de máscaras de bits cuyo AND da $0$. Por ejemplo, vemos que $\{6, 10 \}$ no tiene GCD $1$ porque $0b011 \& 0b101 = 0b001 \neq 0$. En cambio, $\{6, 10, 15 \}$ tiene GCD $1$ porque $0b011 \& 0b101 \& 0b110 = 0b000 = 0$.

Problemas