$\renewcommand{\le}{\leqslant}$ $\renewcommand{\ge}{\geqslant}$

SOS-DP

Bititehted

Enne asja juurde minemist tuletame põgusalt meelde nn "bititehted".

AND, OR ja XOR

Tehete AND, OR ja XOR tegemiseks kirjutame need arvud kahendsüsteemis kohakuti (nagu arve "kirjalikult" liites). Vastuses iga bitt sõltub temaga samas veerus olevatest bittidest järgmiselt:

Arvudest $a$ ja $b$ tehte AND võtmist tähistame $a \& b$, tehte OR võtmist $a \mid b$ ja tehte XOR võtmist $a \oplus b$. Programmeerimiskeeltes on üldiselt sellised tehted implementeeritud: neid ei ole vaja ise implementeerima hakata! Paljudes programmeerimiskeeltes (näiteks C++, Java, Python) kasutatakse tähistusi a & b, a | b, a ^ b.

Teeme need tehted läbi näiteks arvude $21 = 10101_2$ ja $12 = 1100_2$ peal: $$ \begin{array}{ccccccc} &&1&0&1&0&1\\ \& && &1&1&0&0\\ \hline &&0&0&1&0&0 \end{array} \qquad \begin{array}{ccccccc} &&1&0&1&0&1\\ \mid && &1&1&0&0\\ \hline &&1&1&1&0&1 \end{array} \qquad \begin{array}{ccccccc} &&1&0&1&0&1\\ \oplus && &1&1&0&0\\ \hline &&1&1&0&0&1 \end{array} $$ Saame, et $21 \& 12 = 100_2 = 4$, $21 \mid 12 = 11101_2 = 29$, $21 \oplus 12 = 11001_2 = 25$.

Tehted $\ll$ ja $\gg$

Olgu antud arvud $a$ ja $k$. Siis $a \ll k$ on arv $a$, kuhu on kahendsüsteemis $k$ nulli juurde pandud. Näiteks $13 \ll 2 = 1101_2 \ll 2 = 110100$. Programmeerimiskeeltes kasutatakse tähistust a << k. Kehtib $a \ll k = a \cdot 2^k$. Seetõttu kirjutatakse mõnikord programmides $2^k$ arvutamiseks 1 << k.

Olgu antud arvud $a$ ja $k$, siis $a \gg k$ on arv $a$, kust on kahendsüsteemis $k$ parempoolset bitti "ära lõigatud". Näiteks $109 \gg 3 = 1101101_2 \gg 3 = 1101$. Programmeerimiskeeltes kasutatakse tähistust a >> k.

Oletame, et on antud arv $a$ ja vaja kontrollida, kas tema $k$-s bitt (paremalt) on 1. Selleks piisab kontrollida, kas $a \& 1 \ll k = a \& (1 \ll k)$ on nullist erinev.

"Alamhulgad"

Olgu $a$ ja $b$ arvud. Kui $a \& b = b$ ehk $a \mid b = a$, siis ütleme, et $b$ on $a$ alamhulk ja tähistame $b \subseteq a$. Teisisõnu on $b$ arvu $a$ alamhulk, kui $b$ kahendesituses on ühed vaid seal, kus arvul $a$.

Millest selline mõiste? Sageli kasutatakse bitimaske/kahendarve selleks, et tähistada naturaalarvude hulga lõplikke alamhulki. Arvule $a$ vastab hulk $A$, kus $n \in A$ parajasti siis, kui $a$ $n$-s kahendkoht (paremalt) on 1. Näiteks $197 = 11000101_2$ tähistab hulka $\{0, 2, 6, 7\}$. Niisuguses käsitluses vastab tehe AND ühisosa võtmisele, tehe OR ühendi võtmisele ja alamhulga mõiste alamhulga mõistele.

Ülesande püstitus

Olgu meil antud massiiv $A$ pikkusega $n = 2^k$. Vaja on leida ja välja trükkida massiiv $B$, pikkusega samuti $2^k$, kus $$B[i] = \sum_{j \subseteq i} A[j].$$ Nõutav keerukus on $O(kn) = O(k 2^k) = O(n \log n)$. Seda ülesannet (ja selle lahendusvõtet) nimetatakse mõnikord SOS-DP (sum-over-subsets DP, summa-üle-alamhulkade DP).

Lahenduskäik (prefiksisummade vaatenurgast)

1-mõõtmelised prefiksisummad

Olgu antud massiiv $A$ pikkusega $n$. Vaja on leida ja välja trükkida massiiv $B$, kus $$B[i] = A[0] + A[1] + \cdots + A[i] = \sum_{i' \le i} A[i'].$$ Nõutav keerukus on $O(n)$.

See on üks klassikalisemaid võistlusprogrammeerimise ülesandeid.

B = A
for (int i = 1; i < n; i++) {
    B[i] += B[i - 1];
}

print(B)

2-mõõtmelised prefiksisummad

Olgu antud kahemõõtmeline $n \times n$ massiiv $A$. Vaja on leida ja välja trükkida $n \times n$ massiiv $B$, kus $$B[i][j] = \sum_{i' \le i, j' \le j} A[i'][j'].$$ Nõutav keerukus on $O(n^2)$.
Lahendus on järgmine.
B = A
for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j++) {
        B[i][j] += B[i][j - 1];
    }
}

for (int i = 1; i < n; i++) {
    for (int j = 0; j < n; j++) {
        B[i][j] += B[i - 1][j];
    }
}

print(B)

Veendume selle korrektsuses. Eesmärk on, et programmi töö lõpuks oleks $B[i][j]$ võrdne nurkadega $(0, 0)$ ja $(i, j)$ ristküliku elementide summaga. On lihtne veenduda, et kui jõuame reale 7, siis mistahes $i$ ja $j$ korral $$B[i][j] = B[i][0] + B[i][1] + \cdots B[i][j].$$ Oletame, et me oleme mingite konkreetsete arvudega $i$ ja $j$ real 10. Tol hetkel:

Pärast liitmist on siis $B[i][j]$ nurkadega $(0, 0)$ ja $(i, j)$ ristküliku summa.

3-mõõtmelised prefiksisummad

Olgu antud kolmemõõtmeline $n \times n \times n$ massiiv $A$. Vaja on leida ja välja trükkida $n \times n \times n$ massiiv $B$, kus $$B[i][j][k] = \sum_{i' \le i, j' \le j, k' \le k} A[i'][j']][k'].$$ Nõutav keerukus on $O(n^3)$.
B = A
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 1; k < n; k++) {
            B[i][j][k] = B[i][j][k - 1];
        }
    }
}

for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j++) {
        for (int k = 0; k < n; k++) {
            B[i][j][k] = B[i][j - 1][k];
        }
    }
}

for (int i = 1; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            B[i][j][k] = B[i - 1][j][k];
        }
    }
}

print(B)

Idee on sama, mis enne. Iga $i$ korral on $B[i]$ üks $n \times n$ massiiv. Kui jõuame reale 17, siis on iga $i$ jaoks lahendatud massiivis $B[i]$ "ülesanne 2". Teisisõnu, iga $(i, j, k)$ korral on $B[i][j][k]$ tippudega $(i, 0, 0)$ ja $(i, j, k)$ risttahuka summa.

Oletame, et oleme mingite konkreetsete arvudega $i, j, k$ real 21. Sellel hetkel:

Pärast liitmist on siis $B[i][j][k]$ tippudega $(0, 0, 0)$ ja $(i, j, k)$ risttahuka summa.

$k$-mõõtmelised prefiksisummad

Olgu antud $k$-mõõtmeline $n \times n \times \cdots \times n$ massiiv $A$. Vaja on leida ja välja trükkida $n \times n \times \cdots \times n$ massiiv $B$, kus $$B[i_{k - 1}]\cdots[i_1][i_0] = \sum_{i'_0 \le i_0, i'_1 \le i_1, \ldots, i'_{k - 1} \le i_{k - 1}} A[i'_{k - 1}]\cdots[i'_1][i'_0].$$ Nõutav keerukus on $O(kn^k)$.

Siin on koordinaadid nummerdatud paremalt vasakule: hiljem tegeleme bitimaskidega, kus just nii on kombeks.

Praeguseks on lugeja loodetavasti (eelmiste näidete varal) võimeline näiteks 4-, 5-, 6-dimensionaalse juhu jaoks programmi kirjutama. Anname siinkohal üldise skeemi.

B = A
for (ik - 1 = 0; ik - 1 < n; ik - 1++) {
    ................................
        for (i1 = 0; i1 < n; i1++) {
            for (i0 = 1; i0 < n; i0++) {
                B[ik - 1]...[i1][i0] += B[ik - 1]...[i1][i0 - 1]
            }
        }
    ................................
}

................................
// j-s iteratsioon
for (ik - 1 = 0; ik - 1 < n; ik - 1++) {
    ................................
        for (ij + 1 = 0; ij + 1 < n; ij + 1++) {
            for (ij = 1; ij < n; ij++) {
                for (ij - 1 = 0; ij - 1 < n; ij - 1++) {
                    ................................
                        for (i0 = 0; i0 < n; i0++) {
                            B[ik - 1]...[ij + 1][ij][ij - 1]...[i0] += B[ik - 1]...[ij + 1][ij - 1][ij - 1]...[i0];
                        }
                    ................................
                }
            }
        }
    }
}

................................

for (ik - 1 = 1; ik - 1 < n; ik - 1++) {
    ................................
        for (i1 = 0; i1 < n; i1++) {
            for (i0 = 1; i0 < n; i0++) {
                B[ik - 1]...[i1][i0] += B[ik - 1 - 1]...[i1][i0]
            }
        }
    ................................
}
print(B)

Korrektsust on võimalik tõestada (induktsiooniga) analoogiliselt 2D ja 3D juhtudega. Selline kood iseenesest töötab, aga kirjapanek on tohutult tülikas. Pealegi, kõikide nende punktiiride kirjutamine päris koodis ei oleks võimalik. Tahaksime, et dimensioonide arvu $k$ oleks samamoodi võimalik anda parameetrina koodile ette. Sama idee kirja panekuks on vaja välja mõelda parem moodus.

Kujutame ette, et $A$ ja $B$ ei ole mitte massiivid, vaid hoopis mapid, mis võtavad sisendiks $k$-elemendilisi täisarvude vektoreid ja tagastavad täisarve. Sellisel juhul on eelmise koodi idee võimalik kirja panna järgnevalt.

B = A
for (int j = 0; j < k; j++) {
    E = vektor, mis koosneb nullidest, aga paremalt j-ndal kohal on 1
    for (üle kõigi vektorite i leksikograafilises järjestuses) {
        if (i[j] != 0) {
            B[i] += B[i - E];
        }
    }
}
print(B)

Kolmandal real itereerime täpsemalt öeldes üle kõigi $k$-elemendiliste täisarvude vektorite, mille kõik elemendid on $0, 1, \ldots, n - 1$ seas. Vektorite $i$ ja $E$ lahutamine käib koordinaaditi.

SOS-DP kui prefiksisummad

Olgu antud massiiv $A$ pikkusega $2^k$. Vaja on leida ja välja trükkida pikkusega $2^k$ massiiv $B$, kus $$B[i] = \sum_{i' \subseteq i} A[i'].$$ Nõutav keerukus on $O(k2^k)$.

Veendume, et tegu on sisuliselt eelmise ülesande erijuhuga, kus võetakse $n = 2$. Kirjutame arvu $i$ lahti kahendsüsteemis: $$i = i_{k - 1} 2^{k - 1} + \cdots + i_1 2^1 + i_0 2^0 = \overline{i_{k - 1} \cdots i_1 i_0}.$$ Paneme tähele, et $$\overline{i'_{k - 1} \cdots i'_1 i'_0} \subseteq \overline{i_{k - 1} \cdots i_1 i_0} \iff i'_{k - 1} \le i_{k - 1}, \ldots, i'_1 \le i_1, i'_0 \le i_0.$$ Nüüd on massiivi $B$ definitsioon muutunud järgmiseks: $$B\left[\overline{i_{k - 1} \cdots i_1 i_0}\right] = \sum_{i'_{k - 1} \le i_{k - 1}, \ldots, i'_1 \le i_1, i'_0 \le i_0} B\left[\overline{i'_{k - 1} \cdots i'_1 i'_0}\right].$$ Nüüd on näha, et see ülesanne on sisuliselt sama, mis eelmine.

Kirjutame eelmise ülesande lahenduskoodi bitimaskide kujule.

B = A
for (int j = 0; j < k; j++) {
    E = 1 << j;
    for (int i = 0; i < 1 << k; i++) {
        if (i & 1 << j) {
            B[i] += B[i - E];
        }
    }
}
print(B)

Praktilised ülesanded

Olgu kohe alguses öeldud, et lahenduskäik ei kasuta mingeid erilisi liitmise omadusi. Kasutasime nendest ainult kahte (kuigi üsna varjatud kujul): liitmise assotsiatiivsus (see, et $a + (b + c) = (a + b) + c$) ja kommutatiivsus (see, et $a + b = b + a$). See tähendab, et sama ülesannet saab täpselt samal moel lahendada ka igasuguste muude tehete jaoks. Näiteks (ja ülesannetes võib seda vaja minna) võime arvutada samal moel massiivi $B$, kus $$B[i] = \max_{i' \subseteq i} A[i']; \qquad B[i] = \bigoplus_{i' \subseteq i} A[i']$$ või ka mõni muu tehe.

Ülesanne: or-pluss-max

Olgu antud massiiv $A$ pikkusega $2^n$. Vaja on leida ja välja trükkida pikkusega $2^n$ massiiv $B$, kus $$B[k] = \max_{i \mid j \le k, i \ne j} (A[i] + A[j]).$$ On teada, et $1 \le n \le 18$. [Allikas: ARC 100 E].

Esiteks otsime hoopis massiivi $C$, kus $$C[k] = \max_{i \mid j \subseteq k, i \ne j} (A[i] + A[j]) = \max_{i \subseteq k, j \subseteq k, i \ne j} (A[i] + A[j]).$$ Selleks piisab teada (iga $k$ jaoks), mis on kaks kõige suuremat $A[i]$ nii, et $i \subseteq k$.

Defineerime tehte $\odot$, kus $(a, b) \odot (c, d) = (u, v)$, kus $u, v$ on arvude $a, b, c, d$ seast kaks suurimat. Veel defineerime massiivi $$D[i] = (A[i], -\infty)$$ ja arvutame massiivi $$F[k] = \bigodot_{i \subseteq k} D[i].$$ Nüüd on $F[k]$ iga $k$ korral paar $(A[i], A[j])$, kus $A[i]$ ja $A[j]$ on kaks kõige suuremat sellist arvu, et $i$ ja $j$ on $k$ alamhulgad. Võtame $$C[k] = A[i] + A[j], \qquad \text{ kus } F[k] = (A[i], A[j]).$$ Viimaks arvutame $B$ kui $C$ prefiksimaksimumi: $$B[k] = \max(C[0], C[1], \ldots, C[k]).$$ Koodis näeb see välja nii:

pair<int, int> merge (pair<int, int> p, pair<int, int> q) {
    // tagastab paari, kus on kaks paaride p ja q kõige suuremat elementi
}

for (int i = 0; i < 1 << n; i++) {
    D[i] = make_pair(A[i], -INF);
}

F = D
for (int j = 0; j < n; j++) {
    E = 1 << j;
    for (int i = 0; i < 1 << n; i++) {
         if (i & 1 << j) {
             F[i] = merge(F[i], F[i - E]);
         }
    }
}
                                                                                            
for (int i = 0; i < 1 << n; i++) {
    C[i] = F[i].first + F[i].second;
}

B[0] = C[0];
for (int i = 1; i < 1 << n; i++) {
    B[i] = max(B[i - 1], C[i]);
}
print(B)

Ülesanne: alamhulgad, mille AND on 0

On antud massiiv $A$ $n$ elemendiga. Mitu võimalust on valida mõned indeksid $i_1, i_2, \ldots, i_k$ nii, et $$0 = A[i_1] \& A[i_2] \& \cdots \& A[i_k]?$$ $1 \le n, A[i] \le 10^6$. [Allikas: CF 449 D]
Esiteks kasutame SOS-DP (tegelikult siin tuleb võtta "summa üle ülemhulkade", mitte "summa üle alamhulkade", aga lahenduskäik on analoogiline) et arvutada massiiv $B$, kus $$B[j] = \text{selliste indeksite $i$ arv, et } j \subseteq A[i].$$ Defineerime massiivi $C[j] = 2^{B[j]}$ ja paneme tähele, et siis $$C[j] = 2^{B[j]} = (\text{selliste indeksite $i_1, \ldots, i_k$ valikute arv, et } j \subseteq A[i_1] \& \cdots \& A[i_k]).$$ Nüüd saame kasutada elimineerimisprintsiipi (inclusion-exclusion principle), et arvutada ülesande vastus.

Ülesanne: täishäälikud

On antud sõnastik, mis koosneb $n$ sõnast. Sõnad koosnevad kolmest tähest, iga täht on ladina täht a...x. Küsitakse $q$ päringut kujul: $1 \le q \le 2^{24}, 1 \le n \le 10^4$. [Allikas: CF 383 E].

Ülesanne: graafi värvimine

On antud graaf $n$ tipuga. Leia, mitu võimalust on värvida graafi tipud mustaks ja valgeks nii, et leidub vähemalt üks must-must serv, üks must-valge serv ja üks valge-valge serv. $1 \le n \le 40$. [Allikas: CF 1221 G]