Quarantraining - 06

Materiale didattico
1

SOS DP

Prerequisiti

  • Bitmasks
  • Programmazione dinamica

Attenzione: Questo post è una quasi totale traduzione di un blog di Codeforces (ma neanche a dirlo) di usaxena95, visitatelo per trovare i problemi relativi all’argomento (e magari anche lasciare un upvote :wink:). In ogni modo l’idea mi interessava e mi sembrava anche un buon seguito all’argomento precedente.

Introduzione

L’ottimizzazione presentata, Sum Over Subsets, permette di risolvere il seguente problema con complessità O(n\cdot 2^n):
Sia S un insieme di n elementi ed s il numero binario che lo rappresenta, per ogni suo sottoinsieme I sia i il numero binario che lo rappresenta, andiamo ad assegnare un valore A[i]. Vogliamo calcolare per ogni B sottoinsieme di S il valore F[b] = \sum\limits_{I\subseteq B} A[i].
Ovviamente assumeremo tutti gli A[i] già calcolati.

Soluzione subottimale

Si potrebbe semplicemente applicare la formula appena scritta sopra in modo banale, iterando su tutti i sottoinsiemi B di S, per poi calcolarsi F[b] iterando su tutti i sottoinsiemi I di B, grazie a quanto visto in Quarantraining 05 possiamo scrivere:

for(int b = 0; b <= s; b++){//s = 2^n - 1, tutti gli elementi sono scelti
    for(int i = b; i >= 0; i = (i - 1) & b){
        F[b] += A[i];
    }
}

La complessità di questo algoritmo è O(3^n), infatti per ogni sottoinsieme B di cardinalità k (numero degli elementi) il programma fa 2^k operazioni, i sottoinsiemi di S di cardinalità k sono n\choose k, dunque il numero di operazioni totali sarà \sum\limits_{k=0}^{n} {n\choose k} \cdot 2^k=(1+2)^n (per il binomio di Newton).
Tuttavia come annunciato possiamo fare di meglio.

Approccio DP

Per evitare di scorrere tutti i sottoinsiemi di B nel calcolare F[b] dobbiamo cercare un modo intelligente per salvarci le somme di A[i].
Definiamo dp[b][j] la somma degli A[i] con b&i == i (I\subseteq B) ed i può differire da b solo nei primi j bit.
Pertanto dp[b][0] è proprio A[b], infatti l’unico i che può essere diverso da b nei primi 0 bit è b stesso, mentre dp[b][n] è la nostra F[b], infatti è la somma degli A[i] con b&i == i (dato che tutti i bit di i possono variare).
Ora cerchiamo di calcolare dp[b][j] in funzione delle altre dp[x][y]. Il bit che si trova in posizione j-1 è l’ultimo che posso variare:

  • se esso vale 0 non posso farlo (dato che vale b&i == i), in questo caso posso variare fino al bit j-2, dunque dp[b][j] = dp[b][j-1].
  • se esso vale 1 invece posso decidere se lasciarlo a 1 o metterlo a 0: se lo lascio ad 1 è come se decidessi di non cambiarlo, quindi vale il caso di prima dp[b][j] = dp[b][j-1], se invece lo metto a 0 vado a modificare b stesso (dato che cambio lo stato del bit j-1 b diventa b^(1<<(j-1))) , quindi dp[b][j] = dp[b^(1<<(j-1))][j] = dp[b^(1<<(j-1))][j-1] (il bit j-1 è 0 quindi l’uguaglianza vale). Ora i 2 casi sono banalmente disgiunti, dato che ho assegnato a un bit 2 valori diversi (e quel bit non può più cambiare da j-1 in poi), quindi se il bit j-1 è uguale a 1 abbiamo dp[b][j] = dp[b][j-1] + dp[b^(1<<(j-1))][j-1].

Abbiamo quindi ben definito dp[b][j] in funzione di casi minori (lo XOR in b^(1<<(j-1)) manda il bit a 0, quindi è minore), possiamo quindi scrivere un algoritmo bottom up che risolva il problema:

for(int b = 0; b <= s; b++){
    dp[b][0] = A[b];
    for(int j = 1; j <= n; j++){
        if(b & (1<<(j-1)))
            dp[b][j] = dp[b][j-1] + dp[b^(1<<(j-1))][j-1];
        else
            dp[b][j] = dp[b][j-1];
    }
    F[b] = dp[b][n];
}

La complessità dell’algoritmo è chiaramente O(n\cdot 2^n).
Possiamo comunque ottimizzare l’algoritmo in modo da usare O(2^n) memoria anziché O(n\cdot 2^n): basta pensare che l’utilizzo di dp è inutile, in quanto dp[b][j] è definita solo in funzione delle dp con j-1 e non di quelle precedenti, basta quindi invertire i for e salvarci i risultati direttamente in F:

for(int b = 0; b <= s; b++)
    F[b] = A[b];
for(int j = 0; j < n; j++){
    for(int b = 0; b <= s; b++){
        if(b & (1<<j))
            F[b] += F[b^(1<<j)];
    }
}

Il codice diventa anche più semplice.

Conclusioni

Nel post ho cercato di cambiare leggermente l’approccio alla spiegazione del problema (rispetto al blog di Codeforces), in modo da provare a dare un punto di vista in più, tuttavia nel poco tempo a disposizione potrei aver lasciato qualcosa indietro, scrivete pure se un punto risulta incomprensibile :slightly_smiling_face:

Problemi

I problemi potete trovarli alla fine del post originale.

9 Mi Piace