DP ja bitinikerdamine

1. Bititehted

Enne asja juurde minemist tuletame põgusalt meelde nn "bititehted". Tegemist on loogikast tuntud tehetega, mida tehakse iga biti kohta eraldi.

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:

• tehtes AND tekib vastavale kahendkohale 1 parajasti siis, kui mõlemad samas veerus olevad bitid on 1;
• tehtes OR tekib vastavale kahendkohale 1 parajasti siis, kui vähemalt üks samas veerus olev bitt on 1;
• tehtes XOR tekib vastavale kahendkohale 1 parajasti siis, kui täpselt üks samas veerus olev bitt on 1.

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:

Saame, et \(21 \& 12 = 100_2 = 4\), \(21 \mid 12 = 11101_2 = 29\), \(21 \oplus 12 = 11001_2 = 25\).

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.

Tehete järjekord keeles C++ on järgmine:

• ~a
• a * b, a / b ja a % b
• a + b ja a - b
• a << b ja a >> b
• a < b, a <= b, a > b, a >= b
• a == b ja a != b
• a & b
• a ^ b
• a | b
• a && b
• a || b

Eriti tähelepanelik tuleb olla bititehteid ja võrdusi koos kasutades. Näiteks avaldist a & b == c loetakse a & (b == c), mitte (a & b) == c.

Tehteid &, |, ^, ~, << ja >> kombineerides saame tuletada veel mõned kasulikud avaldised:

C++ keeles on olemas veel järgmised funktsioonid, mis võivad olla kasulikud arvu kahendesitusega töötamiseks. Need on üldjuhul kiiremad, kui vastavate operatsioonide "käsitsi" tegemine. Alates C++20-st on need olemas teegis <bit>; varasemates versioonides neid ametlikult ei ole, aga GCC kompilaator on need "mitteametlikult" implementeerinud.

bit_width(0) on 0. countl_zero(a) sõltub loomulikult a tüübist (näiteks countl_zero(0) on tavaliselt 32, countl_zero(0LL) aga 64. GCC funktsioonid on erinevate tüüpide jaoks erinevad — long long-idega opereerimiseks tuleb kasutada __builtin_popcountll jne.

GCC funktsioonid __builtin_clz ja __builtin_ctz on määramata väärtusega, kui argument on 0.

2. Alamhulkadega DP

See on nn rändkaupmehe ülesanne (traveling salesman problem), mis on tuntud näide NP-täielikust ülesandest. Seega polünoomilises ajas lahendust tõenäoliselt ei leidu. Niisama kõikide variantide läbi vaatamine on aga liiga aeglane: \(n\) tippu saab panna \(n!\) erinevasse järjestusse; \(20! \approx 2.4 \cdot 10^{18}\). Kuigi väga efektiivset lahendust olla ei saa, vajame siiski midagi paremat kui kõikide variantide läbivaatus.

Ringkäik peab igas tipus ühe korra käima, seega võime lihtsalt otsustada, et see "algab" ja "lõpeb" tipus 0. Arvutame iga tipuhulga \(S\) ja tipu \(u\) jaoks \(dp[S][u]\) — lühima teekonna, mis algab tipust \(1\), lõpeb tipus \(u\) ja läbib teekonnal täpselt tipud hulgas \(S\).

Selles DP-s on osa olekust hulk, mitte lihtsalt arv. Hulga indeksina kasutamine oleks üsna ebamugav ja tõenäoliselt ka üsna aeglane. Seega kasutame programmi koodis selle hulga esitamiseks bitimaske: hulka esitab täisarv, mille \(k\)-s kahendkoht näitab, kas arv \(k\) kuulub hulka.

Selleks, et need väärtused välja arvutada, seame easialgu \(dp[\{0\}][0] = 0\) ja \(dp[S][k] = \infty\) kõikidel muudel juhtudel. Olekust \((S, u)\) saab edasi liikuda olekutesse \((S \cup \{ v \}, v)\), kus \(v\) on mingi tipp, millesse on serv tipust \(u\) ja mis ei esine hulgas \(S\). DP väärtusi arvutav kood võiks seega olla midagi niisugust:

// siin eeldame, et iga kahe tipu vahel on serv ja W[u][v] on serva uv pikkus
// samuti eeldame, et tipud on nullist indekseeritud

// see, mis järjekorras hulgad täpselt läbi käia, ei ole oluline
// oluline on see, et kui A on B alamhulk, siis A käiakse enne läbi
// väga mugav järjekord on aga see:
for (int mask = 0; mask < 1 << n; mask++) {
  for (int u = 0; u < n; u++) {
    // oleme läbi käinud bitivälja mask tipud ja hetkel tipus u

    // kui u ei esine väljas mask, siis on see olek võimatu
    // see continue ei ole iseenesest vajalik, kuna sel juhul on dp[mask][u] niikuinii lõpmatu
    if (!(mask & 1 << u))
      continue;

    // käime läbi kõik u naabrid, kuhu teekond ei ole veel jõudnud
    for (int v = 0; v < n; v++) {
      // teekond on juba v külastanud, seda me ei uuenda
      if (mask & 1 << v)
        continue;

      dp[mask | 1 << v][v] = min(dp[mask | 1 << v][v], dp[mask][u] + W[u][v]);
    }
  }
}

Nüüd on meil teada iga \(u\) jaoks teada lühima teekonna pikkus, mis algab tipust \(0\), lõpeb tipus \(u\) ja käib igas tipus täpselt ühe korra: \(dp[\{0, 1, \ldots, n - 1\}][u]\). Kui sellele teekonnale lisada serv \(u\) ja \(0\) vahel, moodustab see ringkäigu. Käime läbi kõik tipud \(u\) ja vaatame, millisega see ringkäik kõige lühem tuleb. See ongi vastus.

Keerukus on \(O(n^2 2^n)\) — välimine tsükkel käib läbi \(2^n\) maski, iga maski kohta tehakse veel kaks üksteise sees olevat tsüklit.

3. "Broken profile" DP

Siin on lahendus olemuselt sarnane eelmisega, aga DP olekute valikuga tuleb olla ettevaatlik. Kui proovida ruudustikku ülevalt alla täita ja jätta meelde ainult praegusel real olevaid kaetud ruute, ei ole meil kuhugi salvestada, millised järgmise rea ruudud me oma tegevusega katame. Kui aga proovida meelde jätta praegusel ja järgmisel real olevad kaetud ruudud, on meil vaja \(O(2^{2n})\) olekut: kaugelt liiga palju.

Üks võimalik toimiv lahendus on järgmine: haldame massiivi \(DP[i][j][mask]\), mis loendab, kui mitu võimalust on ruudustikku osaliselt katta nii, et:

• esimesed \(i\) rida on täielikult kaetud;
• \(i\)-nda rea esimesed \(j\) ruutu on täielikult kaetud;
• bitimaski \(mask\) esimesed \(j\) elementi näitavad, millised \(i+1\)-nda rea esimesest \(j\) ruudust on kaetud;
• bitimaski \(mask\) ülejäänud \(m-j\) elementi näitavad, millised \(i\)-nda rea ülejäänud ruutudest on kaetud.

Ka blokeeritud ruudud lähevad maskis kaetud ruutude alla.

DP arvutamiseks proovime katta ruutu \((i, j)\) alla või paremale suunatud doominoga, välja arvatud juhul, kui see juba on blokeeritud või kaetud. Selleks on kolm võimalust ehk kolm DP transitsiooni.

Esiteks, kui ruudud \((i, j)\) ja \((i + 1, j)\) on vabad, siis võime need doominoga katta.

if (i != n - 1 && !(mask & 1 << j) && !blocked[i + 1][j]) {
	int nmask = mask | 1 << j;
	dp[i][j + 1][nmask] += dp[i][j][mask];
}

Teiseks, kui ruudud \((i, j)\) ja \((i, j + 1)\) on vabad, siis võime need doominoga katta. Ruute \((i + 1, j)\) ja \((i + 1, j + 1)\) see ei kata, aga need võivad juba olla blokeeritud. Seega sõltub ka järgmine olek sellest, kas need ruudud on blokeeritud.

if (j != m - 1 && !(mask & 1 << j) && !(mask & 1 << (j + 1))) {
	int nmask = mask | blocked[i + 1][j] << j | blocked[i + 1][j + 1] << (j + 1);
	dp[i][j + 2][nmask] += dp[i][j][mask];
}

Viimaks, kui ruut \((i, j)\) on täidetud, võime lihtsalt järgmise ruudu võtta. Jälle sõltub järgmine olek sellest, kas ruut \((i + 1, j)\) on täidetud.

if (mask & 1 << j) {
	int nmask = (mask & ~(1 << j)) | blocked[i + 1][j] << j;
	dp[i][j + 1][nmask] += dp[i][j][mask];
}

Lisaks nendele reeglitele on veel mõned baasreeglid:

• \(dp[0][0][mask] = 1\), kus \(mask\) vastab esimesel real olevatele blokeeritud ruutudele;
• \(dp[i + 1][0][mask] = dp[i][m][mask]\) mistahes maski \(mask\) korral.

Kõik kokku pannes on keerukus \(O(2^m nm)\): iga DP oleku jaoks tehakse konstantne aeg tööd.

4. Summa üle alamhulkade

Inspireerituna eelmistest teemadest, kus arvu kahendesitus võis tähistada hulka — ja seega AND ühisosa ja OR ühendit — võime rääkida ka teistest hulgateoreetilistest kontseptsioonidest nagu alakmhulkadest. 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\).

Lahenduse leidmiseks üldistame prefiksisummade meetodit.

1-mõõtmelised prefiksisummad

See on üks klassikalisemaid võistlusprogrammeerimise ülesandeid.

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

2-mõõtmelised prefiksisummad

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];
    }
}

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

Oletame, et me oleme mingite konkreetsete arvudega \(i\) ja \(j\) real 10. Tol hetkel:

• \(B[i - 1][j]\) on nurkadega \((0, 0)\) ja \((i - 1, j)\) ristküliku summa;
• \(B[i][j]\) enne liitmist on nurkadega \((i, 0)\) ja \((i, j)\) ristküliku summa.

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

3-mõõtmelised prefiksisummad

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];
        }
    }
}

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.

\(k\)-mõõtmelised prefiksisummad

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

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

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

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

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];
        }
    }
}

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

Veendume, et tegu on sisuliselt eelmise ülesande erijuhuga, kus võetakse \(n = 2\). Kirjutame arvu \(i\) lahti kahendsüsteemis:

Paneme tähele, et

Nüüd on massiivi \(B\) definitsioon muutunud järgmiseks:

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];
        }
    }
}

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

5. Keskel kohtumine

See on variatsioon maksimaalse sõltumatu hulga (maximum independent set) ülesandest, mis on NP-täielik. Seekord võib \(n\) olla 40 ehk \(O(2^n)\) ja sarnaste keerukustega algoritmid on liiga aeglased. Vajame midagi kiiremat.

Jaotame graafi tipud pooleks: esimesse poolde kuuluvad tipud \(1, 2, \ldots, \lfloor n / 2 \rfloor\), teisse \(\lfloor n / 2 \rfloor + 1, \ldots, n\). Nimetame esimest gruppi vasakpoolseteks ja teist parempoolseteks.

Vaatleme mingit sõltumatut parempoolsete tippude alamhulka \(S\). Tahame lisada sellele mõned vasakpoolsed tipud nii, et hulk jääks sõltumatuks ja väärtuste summa oleks võimalikult suur. Tippe, mis on naabriks mõnele tipule hulgast \(S\), ei saa me loomulikult hulka lisada: kõik lisatavad tipud peavad olema hulgast \(T = \{ 1, 2, \ldots, \lfloor n / 2 \rfloor \} \setminus N(S)\), kus \(N(S)\) tähistab \(S\) tippude kõikide naabrite hulka.

Üks võimalik idee oleks siis järgmine:

• Iga parempoolsete tippude sõltumatu alamhulga \(S\) kohta:
  • arvutame hulga \(T = \{ 1, 2, \ldots, \lfloor n / 2 \rfloor \} \setminus N(S)\);
  • leiame hulgas \(T\) maksimaalse kaaluga sõltumatu hulga \(U\);
  • üks kandidaat lahendiks on \(S \cup U\).

Parmpoolsete tippude hulgal on ülimalt \(O(2^{n / 2})\) alamhulka; hulga \(T\) arvutamine on võimalik \(O(n)\) ajas. Ebaselge on ainult see, kuidas arvutada vasakpoolse hulga \(T\) maksimaalse kaaluga sõltumatu alamhulk.

Teeme seda kõikide vasakpoolsete hulkade jaoks korraga, enne parempoolsete tippude uurimist. Tähistagu \(dp[T]\) hulga \(T\) maksimaalset sõltumatut alamhulka. Paneme tähele, et kas:

• \(T\) on ise sõltumatu alamhulk; või
• leidub mingi \(u \in T\) nii, et \(T\) maksimaalne sõltumatu alamhulk no ka \(T \setminus \{ u \}\) maksimaalne sõltumatu alamhulk.

Niisiis võime \(dp[T]\) väärtused välja arvutada nii:

for (int mask = 0; mask < 1 << n / 2; mask++) {
	dp[mask] = 0;
	if (is_independent_set(mask))
		dp[mask] = get_total_weight(mask);
	for (int i = 0; i < n / 2; i++)
		if (mask & 1 << i)
			dp[mask] = max(dp[mask], dp[mask & ~(1 << i)]);
}

See võtab kokku \(O(n 2^{n / 2})\) aega, seega on ka kogu algoritmi keerukus \(O(n 2^{n / 2})\).

6. SOS-DP ja konvolutsioon*

Üllataval kombel lahendab selle ülesande järgmine meetod. Arvutame SOS-DP meetodil massiividest \(A\) ja \(B\) massiivid \(A'\) ja \(B'\):

Korrutame need komponenditi kokku: \(C'[i] = A'[i] \cdot B'[i].\) Tuleb välja, et siis

kus \(C\) on otsitav massiiv. Tõepoolest, mistahes \(k\) korral

Tehes SOS-DP arvutuskäik läbi "tagurpidi", saame nii leida massiivi \(C\).

Avaldist kujul \(C[k] = \sum_{i \star j = k} A[i] B[j]\) nimetatakse konvolutsiooniks. Massiivi \(C\) efektiivseks arvutamiseks kasutatakse üldiselt sarnast võtet:

• mõeldakse tehte \(\star\) jaoks välja mingi teisendus;
• teisendatakse sellega massiivid \(A\) ja \(B\) massiivideks \(A'\) ja \(B'\);
• korrutatakse \(A'\) ja \(B'\) komponenthaaval kokku massiiviks \(C'\);
• teisendus tehakse massiivi \(C'\) peal "tagurpidi" ja leitakse otsitav massiiv \(C\).

Tehtele \(\star\) vastava teisenduse leidmine on loomulikult kõige keerulisem osa. Tehte \(|\) jaoks osutus alamhulkade üle summa võtmine sobivaks teisenduseks. Kuidas on aga teiste bititehetega, näiteks \(\&\) ja \(\oplus\)? Ka nende jaoks on vastavad teisendused olemas. Näiteks XOR jaoks toimib järgmine kood:

void fwht (vector<int> &arr, bool inv) {
	// a pikkus peas olema kahe aste
	int n = arr.size();
	for (int step = 1; step < n; step *= 2) {
		for (int i = 0; i < n; i += 2 * step) {
			for (int j = i; j < i + step; j++) {
				int u = arr[j];
				int v = arr[j + step];
				arr[j] = u + v;
				arr[j + step] = u - v;
			}
		}
	}

	if (inv) {
		for (int i = 0; i < n; i++) {
			arr[i] /= arr.size();
		}
	}
}

Sellist teisendust nimetatakse kiireks Walsh-Hadamardi teisenduseks (fast Walsh-Hadamard transform). Selle teema ja tema üldistuste kohta on palju kirjutatud:

• XOR convolution without math
• Generalized FWHT
• Subset convolution interpretation