Tutorial: Sum over Subset DP

Materiale didattico
1

Breve tutorial riguardo Sum over Subsets DP. Altre ottimizzazioni di programmazione dimanica si trovano nella lezione “DP optimization” del Secondo Stage 2024.

SOS DP

Consideriamo il seguente problema.

Sono dati M \leq 10^6 interi a N = 20 bit. Calcolare per ogni elemento x il numero di elementi y tali che x | y = x.

Osservazione: Vale x | y = x \iff y \subseteq x, con x, y visti come insiemi delle posizioni dei bit 1.

Sia a[x] la frequenza di x nell’array. Per ogni elemento x, la risposta è la “sum over subsets” sos[x] := \sum_{y \subseteq x} a[y].

Approccio naive \mathcal{O}(4^N):

int n = 20;
vector<int> a(1 << n);
vector<int> sos(1 << n);
for (int x = 0; x < (1 << n); ++x)
    for (int y = 0; y < (1 << n); ++y)
        if (x | y == x)
            sos[x] += a[y];

Approccio \mathcal{O}(3^N):

Idea: Per ogni x, posso iterare solo sugli y \subseteq x. In questo modo il numero totale di iterazioni è uguale a S = \#\{(x,y) \mid y \subseteq x \subseteq \{1,\dots,N\}\} = 3^N.

Esercizio: dimostrare l’ultima uguaglianza.

Soluzione con i conti (esiste un modo più intuitivo):

S = \sum_{x \subseteq \{1,\dots,N\}} 2^{|x|} = \sum_{k=0}^{N} {N \choose k}2^k = \sum_{k=0}^{N} {N \choose k}2^k 1^{N - k} = (1+2)^N = 3^N.

for (int x = 1; x < (1 << n); ++x) {
    for (int y = x; y >= 0; y = (y - 1) & x) {
        sos[x] += a[y];
        if (y == 0) {
            break;
        }
    }
}

Purtroppo nel nostro caso \mathcal{O}(3^N) è ancora troppo lento. Per raggiungere la soluzione consideriamo un problema apparentemente scollegato.

Somme prefisse 2D:

È data una griglia le cui celle contengono degli interi. Per ogni cella (i,j), calcolare la somma dei numeri contenuti nelle celle (x,y) con x \leq i \wedge y \leq j.

Si procede calcolando le somme prefisse prima per riga, poi per colonna sulla nuova griglia che contiene le somme prefisse di ogni riga. Alla fine in ogni cella (x,y) si trova la risposta.

Esempio step per una griglia 4 \times 4:

0  2  0  0
0  0  3  0
7  5  0  1
0  0  0  1

0  2  2  2
0  0  3  3
7 12 12 13
0  0  0  1

0  2  2  2
0  2  5  5
7 14 17 18
7 14 17 19

Esercizio (scollegato): Esprimere la somma di un generico rettangolo di vertici (i_1,j_1), (i_2, j_2) nella griglia iniziale come somma/differenza di elementi della griglia finale.

Lo stesso approccio funziona per un numero arbitrario di dimensioni e – tenetevi forte – il problema di partenza si può formulare esattamente in questi termini! :partying_face:

Nel nostro caso l’array è N-dimensionale e ogni coordinata è 0 o 1. Dunque ogni elemento di \{0, \dots, 2^N - 1\} è una N-upla di coordinate binarie. Vale y \subseteq x se e solo se le coordinate di y sono minori o uguali delle coordinate di x (proprio come nelle somme prefisse 2D).

Soluzione \mathcal{O}(N \cdot 2^N)

vector<int> sos(1 << n); // inizialmente sos[i] = a[i]
for (int i = 0; i < n; ++i)
    for (int mask = 0; mask < (1 << n); ++mask)
        if (mask & (1 << i))
            sos[mask] += sos[mask ^ (1 << i)];

Allo step i-esimo, per ogni cella sommiamo le celle precedenti nella i-esima direzione, dunque se l’i-esimo bit è 0 non sommiamo nulla, se è 1 sommiamo l’elemento precedente sulla “riga generalizzata”, vale a dire sos[mask \oplus 2^i].

Esercizio: rispondere anche alle ultime due domande di Bit Problem.

Problema avanzato: JOI18 – Snake Escaping.
Hint: data una stringa w \in \{0, 1, ?\}^L, qual è la massima frequenza del simbolo che appare meno volte?

Fonti:

9 Mi Piace