DP de suma sobre subconjuntos

Suma sobre subconjuntos (Sum Over Subsets, SOS) es una técnica usada para calcular de forma eficiente la suma de valores de todos los subconjuntos de un conjunto o máscara de bits dado.

Problema de suma sobre subconjuntos

Considerar un arreglo $A$ con $2^n$ elementos. Nuestro objetivo es calcular $F(x)$ para todo $x = 0, 1, 2, \dots, 2^n - 1$. Aquí, $F(x)$ representa la suma de los valores del arreglo $A$ para todos los subconjuntos (submáscaras) $i$ de $x$. Es decir:

Por ejemplo, $F(5)=A[0]+A[1]+A[4]+A[5]$.

Solución

Fuerza bruta

La solución naive sería iterar sobre todos los pares de máscaras, sumando $A[i]$ solo cuando una de ellas es un subconjunto de la otra (es decir, $i\ \&\ x = i$).

vector<int> sos(1 << n);
 
for (int x = 0; x < (1 << n); x++) {
	// iterate over all other sets and checks whether they're a subset of x
	for (int i = 0; i < (1 << n); i++) {
		if ((i & x) == i) { sos[x] += a[i]; }
	}
}

sos = [0] * (1 << n)
for x in range(1 << n):
	# iterate over all other sets and checks whether they're a subset of x
	for i in range(1 << n):
		if (x & i) == i:
			sos[x] += a[i]

Esta solución tiene complejidad temporal $\mathcal{O}(2^n \cdot 2^n) = O(4^n)$, que es demasiado lenta para valores grandes de $n$.

Solución optimizada: iterar sobre submáscaras

En lugar de iterar sobre las $2^n$ máscaras de bits para $i$, podemos optimizar iterando solo sobre las máscaras subconjunto de $x$ usando la fórmula $i = (i - 1)\ \&\ x$, que genera de forma eficiente todos los subconjuntos válidos de $x$ en orden inverso. Este enfoque omite combinaciones innecesarias, reduce de forma significativa la cantidad de iteraciones y mejora la complejidad temporal.

vector<int> sos(1 << n);
 
 
for (int x = 0; x < (1 << n); x++) {
	sos[x] = a[0];
	// iterate over all subsets of x directly
	for (int i = x; i > 0; i = (i - 1) & x) { sos[x] += a[i]; }
}

sos = [0] * (1 << n)
for x in range(1 << n):
	sos[x] = a[0]
	i = x
	# iterate over all subsets of x directly
	while i > 0:
		sos[x] += a[i]
		i = (i - 1) & x

Complejidad temporal: $\mathcal{O}(3^n)$

Solución más rápida usando programación dinámica

Aunque el método anterior es mejor, todavía tiene algo de redundancia. Por ejemplo, si una máscara de bits $i$ tiene $k$ bits apagados, entonces $A[i]$ se suma $2^k$ veces. Agrupando las máscaras que aparecen juntas con frecuencia, podemos precomputar y reutilizar sus sumas para eliminar adiciones repetidas.

Partición de máscaras subconjunto con $S(x, i)$

Definimos el conjunto $S(x, i)$ de subconjuntos de $x$ de la siguiente forma:

En términos más simples, $S(x, i)$ contiene todas las máscaras subconjunto de $x$ cuyos bits coinciden con los de $x$ excepto por los $i$ bits más a la derecha.

Por ejemplo:

Podemos descomponer $S(x, i+1)$ de la siguiente forma:

1. Si el $i$-ésimo bit de $x$ es $0$, entonces $S(x, i+1) = S(x, i)$.
2. Si el $i$-ésimo bit de $x$ es $1$:
   • Subconjuntos con el $i$-ésimo bit $1: S(x, i)$.
   • Subconjuntos con el $i$-ésimo bit $0 : S(x \oplus 2^i, i)$. Así:

Usando la partición de arriba, definimos una tabla de DP $dp[x][i]$ donde:

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

vector<int> sos(1 << n);
vector<vector<int>> dp(1 << n, vector<int>(n + 1));
 
 
for (int x = 0; x < (1 << n); x++) {
	dp[x][0] = a[x];
	for (int i = 0; i < n; i++) {
		dp[x][i + 1] = dp[x][i];
		if (x & (1 << i)) { dp[x][i + 1] += dp[x ^ (1 << i)][i]; }
	}
	sos[x] = dp[x][n];
}

sos = [0] * (1 << n)
dp = [[0] * (n + 1) for _ in range(1 << n)]
 
for x in range(1 << n):
	dp[x][0] = a[x]
	for i in range(n):
		dp[x][i + 1] = dp[x][i]
		if x & (1 << i):
			dp[x][i + 1] += dp[x ^ (1 << i)][i]
 
	sos[x] = dp[x][n]

Uso de memoria optimizado

Como $dp[x][i+1]$ solo depende de $dp[x][i]$, podemos reutilizar el arreglo de DP.

sos = a;
 
for (int i = 0; i < n; i++) {
	for (int x = 0; x < (1 << n); x++) {
		if (x & (1 << i)) { sos[x] += sos[x ^ (1 << i)]; }
	}
}

sos = a[:]
 
for i in range(n):
	for x in range(1 << n):
		if x & (1 << i):
			sos[x] += sos[x ^ (1 << i)]

SOS DP como suma de prefijos N-dimensional

Antes de seguir, revisitemos las sumas de prefijos 2D. Dado un arreglo $n \times m$ $A$, el arreglo de sumas de prefijos $S$ se define como:

El enfoque estándar usa inclusión-exclusión:

Aunque este enfoque funciona para grillas 2D, tiene una limitación importante: a medida que aumenta el número de dimensiones, la cantidad de términos que hay que sumar o restar también crece de forma exponencial, lo que lo vuelve ineficiente para grillas de más dimensiones.

Un enfoque simple y más escalable sería barrer a lo largo de cada eje de a uno y calcular la suma de prefijos paso a paso:

// Initialize
for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) { S[i][j] = A[i][j]; }
}
 
// Sweep along x-axis
for (int i = 1; i < n; i++) {
	for (int j = 0; j < m; j++) { S[i][j] += S[i - 1][j]; }
}
 
// Sweep along y-axis
for (int i = 0; i < n; i++) {
	for (int j = 1; j < m; j++) { S[i][j] += S[i][j - 1]; }
}

# Initialize
for i in range(n):
	for j in range(m):
		S[i][j] = A[i][j]
 
# Sweep along the x-axis
for i in range(1, n):
	for j in range(m):
		S[i][j] += S[i - 1][j]
 
# Sweep along the y-axis
for i in range(n):
	for j in range(1, m):
		S[i][j] += S[i][j - 1]

Este enfoque se generaliza a más dimensiones.

Digamos que queremos calcular el arreglo de sumas de prefijos para una grilla 4D. Podemos calcularlo barriendo a lo largo de cada eje de una grilla 4D, de a uno:

• Después de barrer a lo largo del eje x, $S[i][j][k][l]$ contiene la suma de $A[a][b][c][d]$ donde:
  • $a \leq i$
  • $b = j, c = k,$ y $d = l$.
• Después de barrer a lo largo del eje y, $S[i][j][k][l]$ contiene la suma de $A[a][b][c][d]$ donde:
  • $a \leq i, b \leq j$
  • $c = k,$ y $d = l$.
• Después de barrer a lo largo del eje z, $S[i][j][k][l]$ contiene la suma de $A[a][b][c][d]$ donde:
  • $a \leq i, b \leq j, c \leq k$
  • $d = l$.
• Por último, después de barrer a lo largo del eje w, $S[i][j][k][l]$ contiene la suma de $A[a][b][c][d]$ donde:
  • $a \leq i, b \leq j, c \leq k,$ y $d \leq l$.

Si extendemos esta idea a $n$ dimensiones, esto es lo que ocurre después de barrer a lo largo del $i$-ésimo eje. Para cada vector $n$-dimensional $x$, $S[x]$ contiene la suma de los valores de $A$ donde las primeras $i+1$ coordenadas son menores o iguales que $x$, y las coordenadas restantes coinciden con $x$. ¿Suena familiar?

Comparemos esto con el problema SOS. Si pensamos cada bit de una máscara de bits como su propio eje, entonces una máscara de bits $x$ con $n$ bits se puede ver como un vector $n$-dimensional, donde cada coordenada es $0$ o $1$. Una submáscara de $x$ corresponde a un vector $n$-dimensional donde cada coordenada es menor o igual que $x$.

Por lo tanto, cuando interpretamos la máscara de bits como un vector $n$-dimensional, $F(x)$ coincide con la definición de una suma de prefijos $n$-dimensional.

Aplicando el algoritmo de barrido a lo largo de cada eje, obtenemos la solución de SOS DP con memoria optimizada mencionada antes, lo que demuestra que la SOS DP es de hecho una suma de prefijos n-dimensional.

F = A;
 
for (int i = 0; i < n; i++) {  // Sweep along the i-th axis
	for (int x = 0; x < (1 << n); x++) {
		if (x & (1 << i))  // If the i-th bit is set, accumulate
			F[x] += F[x ^ (1 << i)];
	}
}

F = A[:]
 
for i in range(n):  # Sweep along the i-th axis
	for x in range(1 << n):
		if x & (1 << i):  # If the i-th bit is set, accumulate
			F[x] += F[x ^ (1 << i)]

Explicación

Primero, pensar cada palabra como una combinación de letras representada por una máscara de bits. Por ejemplo, bcd = 0b1110, y ada = 0b1001, donde cada bit representa una letra. También llevaremos la cuenta de con qué frecuencia aparece cada máscara de bits en el diccionario.

Luego, usamos SOS DP para calcular la cantidad de palabras disjuntas de la máscara (es decir, palabras que contienen ninguna de las vocales de la máscara). Esto significa que la máscara de bits de la palabra debe ser un subconjunto del complemento de la máscara (~mask).

Una vez calculado esto, la cantidad de palabras válidas para un subconjunto es simplemente $n - sos[\sim mask]$ porque una palabra es válida si contiene al menos una vocal del subconjunto, es decir, no es disjunta de la máscara. Por último, elevamos al cuadrado el conteo de palabras válidas para cada subconjunto, hacemos XOR de todos esos valores al cuadrado, y eso nos da la respuesta.

Implementación

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

#include <iostream>
#include <string>
 
const int M = 24;
int sos[1 << M];
 
int main() {
	int n;
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		std::string st;
		std::cin >> st;
		int mask = (1 << (st[0] - 'a')) | (1 << (st[1] - 'a')) | (1 << (st[2] - 'a'));
		sos[mask] += 1;
	}
 
	for (int i = 0; i < M; i++) {
		for (int mask = 0; mask < (1 << M); mask++) {
			if (mask & (1 << i)) { sos[mask] += sos[mask ^ (1 << i)]; }
		}
	}
 
	int res = 0;
	for (int mask = 0; mask < (1 << M); mask++) {
		// sos[mask] now contains the number of words whose bitmasks are subsets of mask
		int valid_words = n - sos[(1 << M) - 1 - mask];
		res ^= valid_words * valid_words;
	}
	std::cout << res << '\n';
}

M = 24
sos = [0] * (1 << M)
 
n = int(input())
for i in range(n):
	st = input()
	mask = (
		(1 << (ord(st[0]) - 97)) | (1 << (ord(st[1]) - 97)) | (1 << (ord(st[2]) - 97))
	)
	sos[mask] += 1
 
 
for i in range(M):
	for mask in range(1 << M):
		if mask & (1 << i):
			sos[mask] += sos[mask ^ (1 << i)]
 
res = 0
for mask in range(1 << M):
	# sos[mask] now contains the number of words whose bitmasks are subsets of mask
	valid_words = n - sos[(1 << M) - 1 - mask]
	res ^= valid_words * valid_words
 
print(res)

Problemas generales