Antes de leer este manual, conviene haber visto:
La técnica de SOS DP (sum over subsets dynamic programming) es una aplicación notable de la programación dinámica. En su forma más básica, proporciona una solución al siguiente problema.
Sea $n$ un entero positivo y sea $a$ un vector de $2^n$ elementos, indizado por subconjuntos del conjunto $[n] = \{1, \ldots, n\}$. Queremos calcular, para todo subconjunto $S \subseteq [n]$, la suma de $a(T)$ para todo $T \subseteq S$. Simbólicamente, queremos calcular los valores de $F(S) : \mathcal{P}([n]) \rightarrow \mathbb{Z}$, donde
$$F(S) = \sum_{T \subseteq S} a[T]$$
Nos será más conveniente no pensar en términos de conjuntos y subconjuntos sino pensar en términos de máscaras de bits. Es decir, si representamos los conjuntos como enteros en binario donde el $i$-ésimo bit a $1$ indica que $i$ pertenece al conjunto ahora $F(x)$ es la suma de $a[y]$ para todo entero $y$ que sea una submáscara de $x$.
La forma más directa de resolver este problema es, para cada $x$, iterar por todas las submáscaras de $x$. Si se itera por todos los números $y$ desde $0$ a $2^n-1$ y se comprueba si cada uno es una submáscara, la complejidad total es $O(4^n)$; sin embargo, este elegante código a continuación permite iterar por las submáscaras directamente y obtener una complejidad total de $O(3^n)$.
for (int x = 0; x < (1<<n); x++){
F[x] = a[0];
for(int y = x; y > 0; y = (y-1) & x){
F[x] += a[y];
}
}
Ejercicio: ¿Por qué el código anterior itera por todas las submáscaras? ¿Por qué la complejidad es $O(3^n)$?
Sin embargo, se puede hacer mejor. La técnica de SOS DP permite obtener una complejidad de $O(n \cdot 2^n)$. La idea es definir la siguiente cantidad:
$$f(x, i) = \sum_{\substack{y \subseteq x \\ x \oplus y < 2^i}} a[y]$$
Donde $y \subseteq x$ denota que $y$ es submáscara de $x$ y $\oplus$ denota el XOR bit a bit. Es decir, $f(x, i)$ es la suma de $a[y]$ para los $y$ tales que los primeros $i$ bits de $y$ son uns submáscara de los primeros $i$ bits de $x$ y el resto de bits de $y$ son iguales a $x$. Está claro que $F(x) = f(x,n)$ y $f(x,0) = a[x]$. Además, tenemos, esta expresión recursiva para $f(x, i)$: $f(x, i) = f(x, i-1)$ si el $i$-ésimo bit de $x$ es $0$, en caso contrario $f(x, i) = f(x, i-1) + f(x \oplus 2^{i-1}, i-1)$. Esto nos permite desarrollar la dinámica $O(n \cdot 2^n)$ deseada:
for(int x = 0; x < (1<<n); +x){
f[x][0] = a[x];
for(int i = 0; i < n; ++i){
if(x & (1<<i))
f[x][i+1] = f[x][i] + f[x^(1<<i)][i];
else
f[x][i+1] = f[x][i];
}
F[x] = f[x][n];
}
Podemos eliminar la dimensión del parámetro $i$ para obtener el siguiente código, muy corto y limpio.
for(int i = 0; i < (1<<n); ++i)
F[i] = a[i];
for(int i = 0; i < n; ++i)
for(int x = 0; x < (1<<n); ++x)
if(x & (1<<i))
F[x] += F[x^(1<<i)];
Esta técnica no sirve sólo para resolver este problema en concreto, sino que se puede aplicar para otras operaciones que tengamos que aplicar sobre submáscaras que no sean la suma tal cual. Veamos un ejemplo (intentad pensarlo antes de leer la solución):
Problema (Codefest '19)
Dado un array $a_1, \ldots, a_n$, calcular:
$$\max_{i<j<k} a_i|(a_j \& a_k)$$
Donde $|$ representa el OR bit a bit, $\&$ representa el AND bit a bit.
Restricciones: $3 \leq n \leq 10^6$, $0 \leq b_i \leq 2 \cdot 10^6$.
Solución:
Para cada $x$, sea $i(x)$ el índice más alto tal que $x \subseteq b_{i(x)}$ (si no existe tal índice, $i(x) = -1$). Notemos que este $i(x)$ lo podemos calcular con la técnica SOS: partimos del array $A(x) = \max \{i : b_i = x\}$ (igual que antes, si $x$ no aparece en el array entonces $A(x) = -1$) y en lugar de calcular la suma calculamos el máximo. Una diferencia adicional con el caso anterior es que ahora tenemos que calcular el máximo sobre las súpermáscaras ($y$ tal que $x \subseteq y$), no sobre las submáscaras. Una posible forma de solucionar esto es trabajar con los complementos bit a bit de los números, entonces ahora sí que consideramos las submáscaras.
La solución del problema es ir iterando por cada $i$ y calcular el valor máximo de $a_i | (a_j \& a_k)$ para $k > j > i$. Para ello, se itera por cada bit que no esté en $a_i$ desde el bit más alto hasta el más bajo y se comprueba si existen $k > j > i$ tales que tanto $a_j$ como $a_k$ contienen ese bit (y todos los bits más altos que se han determinado posibles). Para hacer esto, no sólo hay que calcular el $i(x)$ anterior sino también $j(x)$, el segundo índice más alto, pero se puede hacer con una idea parecida. Ver el código para más detalles:
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
const int D = 21;
const int N = (1<<D);
int comp(int x) {
return (~x)&(N-1);
}
void add_idx(ii& x, int i) {
if (i > x.first) {
x.second = x.first;
x.first = i;
}
else if (i > x.second) {
x.second = i;
}
}
int main() {
int n;
cin >> n;
vi a(n);
vii A(N, ii(-1, -2));
for (int i=0; i < n; ++i) {
cin >> a[i];
add_idx(A[comp(a[i])], i);
}
// F[i] = pareja de indices mas a la derecha que tienen como submascara el complementario de i
vii F(N);
for (int j=0; j < N; ++j) {
F[j] = A[j];
}
for (int i=0; i < D; ++i) {
for (int j = 0; j < N; ++j) {
if (j & (1<<i)) {
add_idx(F[j], F[j^(1<<i)].first);
add_idx(F[j], F[j^(1<<i)].second);
}
}
}
int ans = 0;
for (int i=0; i+2 < n; ++i) {
int w = 0;
for (int b=D-1; b >= 0; --b) {
if(!(a[i]&(1<<b)) && F[comp(w|(1<<b))].second > i) {
w |= (1<<b);
}
}
ans = max(ans, w|a[i]);
}
cout << ans << endl;
}
Añadir nuevo comentario