6. Okultistický fundraising vzorové riešenie

3
12
3 5
4 2
4 7

122

3
15
3 5
4 2
4 7

A je to v ...

Táto úloha bola na pomery O-čka pomerne ľahká. Hlavná časť jej riešenia používa metódu dynamického programovania a ak sa vám túto úlohu nepodarilo vyriešiť, určite by ste si mali prečítať toto vzorové riešenie, pretože táto metóda je často používaná.

Prezeranie všetkých riešení

Skôr ako sa pustíme do vzorového riešenia, povedzme si čo-to o menej optimálnych prístupoch. Úloha po nás chce, aby sme sa o každej z \(n\) kariet rozhodli, ktorou stranou ju otočíme (ktoré číslo sa objaví na vrchu) a chceme, aby súčet týchto čísel dal dokopy hodnotu \(s\).

Ako prvé riešenie teda môžeme vyskúšať všetky možné otočenia kariet. Pre každé otočenie vyskúšame, aký súčet dostaneme a ak sa nejaký súčet rovná \(s\), prehlásime toto otočenie za výsledok. Ak ani jedno otočenie nebude vyhovovať, riešenie zjavne neexistuje. Otázka je, koľko je možných otočení \(n\) kariet. A asi je jasné, že týchto možností je \(2^n\). Ak naviac každú možnosť spracujeme v čase \(O(n)\) dostávame riešenie so zložitosťou \(O(n2^n)\). Nič úžasné, ale dosť na to, aby sme získali sľubované \(3\) body.

Otázkou teraz zostáva, ako takéto riešenie naprogramovať a ako ho naprogramovať čo najbezbolestnejšie. Celý trik leží v tom, ako si reprezentujeme dané otočenie. Ak sa pozrieme na výstup, vidíme, že máme vypísať postupnosť čísel \(1\) a \(2\), kde \(i\)-te číslo reprezentuje otočenie \(i\)-tej karty. Čísla \(1\) a \(2\) nie sú pre počítač až také pekné – čo ak by sme ich zmenili na čísla \(1\) a \(0\)? Potom by predsa každé otočenie bol bitový reťazec, čo je vlastne číslo v binárnom zápise.

Reprezentovať si otočenie pomocou čísla môže byť pomerne pohodlné, hlavne ak vezmeme do úvahy, že každé číslo od \(0\) po \(2^n-1\) je nejaké platné otočenie, a navyše každé dve rôzne čísla reprezentujú dve rôzne otočenia. Otázkou však zostáva, či sa vieme nejakým jednoduchým spôsobom dostať k \(i\)-temu bitu čísla \(x\), teda zistiť, či je tento bit \(0\) alebo \(1\). Odpoveď je, že to vieme dokonca v konštantnom čase, použitím dvoch binárnych operácií – shift left (zapisovaný ako \(<<\)) a and (zapisovaný ako \(\&\)). Operácia \(x\&(1<<i)\) potom vráti na výstup \(i\)-ty bit čísla \(x\).¹

for(int i=0; i<(1<<n); i++) {
    int sucet = 0;
    for(int j=0; j<n; j++)
        if(i&(1<<j)) sucet += druha_strana[j];
        else sucet += prva_strana[j];
    if(sucet == s) riesenie = i;
}

Meet in the middle

Keď už máme tri body, mohli by sme poškuľovať po tých piatich. Obmedzenie, ktoré máme zadané, nám vraví, že \(n\) je menšie ako \(50\), čo je zhruba dvojnásobok predchádzajúceho obmedzenia. Mohli by sme teda stále zostať v exponencionálnej časovej zložitosti, akurát ju trošku zlepšiť. V tomto prípade, ak by sa nám podarilo vytvoriť algoritmus so zložitosťou približne \(O(2^{n/2})\), ešte stále by to mohlo fungovať. Vyzerá to teda, ako by sme mohli naraz pracovať len s polovicou vstupu. A presne na tom sa zakladá riešenie metódou meet in the middle.

Zoberme si prvú polovicu vstupu a pustime naň predchádzajúci algoritmus. Vyskúšame teda všetky možné otočenia prvej polovice kariet. Ak je súčet nejakého otočenia väčší ako \(s\), toto otočenie môžeme rovno zahodiť, lebo je nepoužiteľné. V opačnom prípade si ho ale zapamätáme aj s príslušným súčtom.

Keď sme spracovali prvú polovicu, pustime sa do druhej. Zoberieme si nejaké otočenie druhej polky kariet a zistíme, že jeho súčet je \(x\). To ale znamená, že ak sa nám podarí otočiť prvú polovicu kariet tak, aby dávala súčet \(s-x\), máme vhodné otočenie. Dokopy totiž obe časti dajú súčet \(s\). Stačí sa teda pozrieť do riešení prvej polovice – a aby to bolo dosť efektívne, tieto riešenia chceme mať uložené v mape alebo utriedené podľa súčtov a v nich binárne vyhľadávať.

Spracovanie prvej polovice nám trvá \(O(n2^{n/2})\) (najväčší prínos má triedenie, ktorého zložitosť je \(2^{n/2} \log(2^{n/2})\), to je však po odstránení logaritmu \(n2^{n/2}\)) a tento čas nám trvá aj spracovanie druhej polovice. Keďže sme ich však od seba oddelili a spracovávame ich samostatne, výsledný časová zložitosť bude tiež \(O(n2^{n/2})\), a to by nám malo stačiť na \(5\) bodov. Riešenie vyzerá podobne ako predchádzajúce, minimálne sa v ňom využívajú rovnaké časti programu².

map<int,int> prva_polovica;
int pol = n/2;
for(int i=0; i<(1<<pol); i++) {
    int sucet = 0;
    for(int j=0; j<pol; j++)
        if(i&(1<<j)) sucet += druha_strana[j];
        else sucet += prva_strana[j];
    prva_polovica[sucet] = i;
}
pol = n - pol;
for(int i=0; i<(1<<pol); i++) {
    int sucet = 0;
    for(int j=0; j<pol; j++)
        if(i&(1<<j)) sucet += druha_strana[n/2 + j];
        else sucet += prva_strana[n/2 + j];
    if(prva_polovica.find(s - sucet) != prva_polovica.end()) {
        riesenie_prva = prva_polovica[s - sucet];
        riesenie_druha = i;
    }
}

Vzorové riešenie

Podľa obmedzení, ktoré máme zadané, je jasné, že žiadne exponenciálne riešenie nebude vyhovovať, preto to potrebujeme nejakým spôsobom zlepšiť. Začnime teda malým trikom.

Hlavný problém je, že sa musíme rozhodovať, ktorú stranu zoberieme, a ktoré číslo prirátame k výsledku. Zoberme si teraz kartu, na ktorej sú čísla \(8\) a \(3\). Je jasné, že nech otočíme kartu ľubovoľnou stranou, k výsledku pripočítame aspoň hodnotu \(3\). Čo ak by sme teda nahradili túto kartu kartou, ktorá má na sebe čísla \(5\) a \(0\), a odčítali číslo \(3\) od \(s\)? Dostali by sme novú sadu kariet a ich otočením by sme chceli dosiahnuť hodnotu \(s-3\). Vidíme, že naša úloha sa vlastne vôbec nezmenila, a ak nájdeme otočenie, ktoré rieši túto úlohu, toto otočenie bude dobré aj pre nezmenené karty.

Takýmto spôsobom môžeme upraviť všetky karty. Zistíme minimum z ich strán a toto minimum odčítame jednak od oboch strán karty, jednak od hodnoty \(s\). Na prvý pohľad sa zdá, že sa nič nezmenilo, stále hľadáme otočenie \(n\) kariet, akurát hľadáme inú hodnotu \(s^\prime\). Na jednej zo strán karty je však zakaždým hodnota \(0\). To znamená, že náš problém sa dá preformulovať: Ktoré karty máme vybrať, aby ich súčet bol \(s^\prime\)?

Znamená to, že máme množinu \(n\) čísel a chceme zistiť, či niektorá z množín týchto čísel má súčet \(s^\prime\). Možno, že to tak nevyzerá, úloha sa nám však trochu zjednodušila a skúsenejší z vás v nej možno spoznali klasický problém o napĺňaní batoha (aspoň jednu z mnohých verzií tohoto problému).

Ako však riešiť túto úlohu? Ešte stále sa nám ponúka vyššie ukazované exponenciálne riešenie, pomocou ktorého vieme prechádzať všetky podmnožiny. Samozrejme toto riešenie je príliš pomalé. Treba sa preto pozrieť na to, prečo je tak pomalé. Spýtajme sa teda veľmi dôležitú otázku, ktorú by ste sa mali pýtať zakaždým: Nerobíme niečo viac krát? Ak totiž rátame nejakú informáciu viacej krát, dá sa toto opakovanie odstrániť a tým zrýchliť naše riešenie.

Zoberme si množinu čísel \(\{1,3,2,5\}\). Ak spracujeme prvé tri prvky, zistíme, že pomocou prvého a tretieho prvku vieme dosiahnuť hodnotu \(3\), ale túto hodnotu vieme dosiahnuť aj pomocou druhého prvku. Máme teda dva rôzne spôsoby ako dosiahnuť tú istú hodnotu a k obom týmto možnostiam následne skúsime pridať hodnotu \(5\). Nám však stačí, ak zistíme, že hodnotu \(3\) vieme vyskladať pomocou prvých troch prvkov a potom k tejto hodnote pridať \(5\) len raz. Samozrejme, dá sa argumentovať, že toto nám nemusí pomôcť, lebo každá podmnožina čísel môže dávať rôzny súčet. Možných súčtov by teda bolo \(2^n\), pre nás zaujímavé sú však len tie súčty, ktoré sú menšie ako \(s^\prime\). V okamihu ako nájdeme väčší súčet, môžeme ho rovno zahodiť, lebo nám nemôže pomôcť, keďže pracujeme len s kladnými číslami. A hodnota \(s^\prime\) je podľa zadania najviac \(50\,000\), čo je často menej než \(2^n\).

Zostáva už len správne využiť spomenuté pozorovanie. Spravíme si pole \(V\) dĺžky \(s^\prime\) a na políčko \(x\) si budeme značiť, či vieme dosiahnuť súčet \(x\) pomocou nejakej podmnožiny prvých \(i\) čísel. Na začiatku, keď nepoužívame žiadne čísla, jediný súčet, ktorý vieme dosiahnuť, je \(0\). Preto si nastavíme hodnotu \(V[0]=1\) a zvyšné hodnoty na \(0\).

Nech už máme pridaných prvých \(i-1\) čísel a chceme pridať \(i\)-te číslo, ktoré má hodnotu \(a_i\). Prezerajme postupne pole \(V\), prvok po prvku. Ak je na \(x\)-tej pozícii hodnota \(0\), nepotrebujeme urobiť nič – hodnotu \(x\) nevieme vyskladať z prvých \(i-1\) kariet a teda nemôžeme pridať túto kartu. Ak je však \(V[x]\) rovné \(1\), tak to znamená, že existuje podmnožina prvých \(i-1\) kariet, ktorá dáva súčet \(x\). Ak k tejto (ľubovoľnej z nich) podmnožine pridáme kartu \(a_i\), dostaneme množinu so súčtom \(x+a_i\) a zaznačíme si do \(V\), že \(V[x+a_i]=1\). Ak náhodou \(x+a_i>s^\prime\) tak túto hodnotu zahodíme.

Ak po spracovaní všetkých kariet sa \(V[s^\prime]\) rovná \(1\), tak naša úloha má riešenie, v opačnom prípade nevieme nájsť podmnožinu s požadovaným súčtom. Zostávajú nám posledné dve veci, ktoré musíme vyriešiť. Prvou z nich je, ako spätne zistiť, ktoré čísla použijeme vo výslednej množine, ktorá dáva súčet \(s^\prime\), aby sme vedeli späť zistiť, ktoré karty otočiť na ktorú stranu. Druhá vec je trochu nejasnejšia, ale pomôže nám v tom, aby nám celý algoritmus fungoval korektne.

Začnime tou druhou. Problém našeho algoritmu môže vzniknúť pri prechádzaní poľa \(V\) a pridávaní ďalšej karty. Ak budeme prechádzať pole od hodnoty \(0\) po \(s^\prime\), tak sa stane nasledovná vec. Nájdeme jednotku vo \(V[0]\) a nastavíme na jedna \(V[a_1]\). Potom ale nájdeme aj túto novo pridanú jednotku a nastavíme \(V[2a_1]\) na jednotku. To však nie je platná množina, lebo pomocou jednej karty s hodnotou \(a_1\) ju nevieme dosiahnuť. Preto si treba dať pozor, aby sme pole prechádzali od väčších hodnôt k menším. Tým zaručíme, že upravujeme už spracované indexy a náš algoritmus bude fungovať správne.

Posledný problém, ako spätne zistiť, ktoré čísla tvoria výslednú množinu, vieme vyriešiť pomocou jedného poľa navyše. V tomto poli \(S\) si na pozícii \(x\) zaznačíme, ktoré číslo sme pridali ako posledné do množiny so súčtom \(x\). Ak teda nastavíme hodnotu \(V[x+a_i]\) na jednotku, do políčka \(S[x+a_i]\) nastavíme hodnotu \(i\). Pomocou tohoto poľa a hodnôt \(a_i\) vieme spätne zrekonštuovať riešenie.

Rekapitulácia

Zopakujme si teda celé naše riešenie. Začneme tým, že upravíme všetky naše karty tak, aby na jednej strane bola \(0\) a na druhej kladná hodnota, a príslušne upravíme hodnotu \(s\). S novovytvorenými číslami potom spustíme algoritmus, ktorý bude zisťovať, ktoré všetky súčty vieme vytvoriť z prvých \(i\) čísel. Na konci zistíme, či vieme vytvoriť súčet \(s^\prime\) a pomocou pomocného poľa \(S\), do ktorého si ukladám posledné použité číslo, zistíme, ktoré čísla patria do riešenia. Následne otočíme každú kartu, ktorej patrí číslo z tejto množiny, na stranu, kde má maximum a zvyšné karty na stranu, kde majú minimum.

Aká bude časová a pamäťová zložitosť tohoto riešenia? Na zisťovanie dosiahnuteľnosti súčtov a pamätanie si kroku späť potrebujeme pole dĺžky \(s\) a na zapamätanie kariet pole veľkosti \(n\). Máme teda pamäťovú zložitosť \(O(n+s)\). Čo sa týka času, tak na pridanie jednej karty k našim vytvoreným množinám potrebujeme prejsť celým poľom dĺžky \(s\) a toto opakujeme \(n\) krát. Dosiahneme teda zložitosť \(O(ns)\), ktorá nám bude stačiť na získanie plného počtu bodov.

Na záver poznamenám, že riešenie využíva to, že hodnota \(s\) je dostatočne malá a teda treba vždy zvážiť, kedy takéto riešenie použiť. Naviac je dobré si uvedomiť, že riešenie nemá polynomiálnu časovú zložitosť, lebo je závislé od hodnoty \(s\), ktorá nezodpovedá veľkosti vstupu. Vstup je veľký \(O(n)\) a \(s\) môže byť ľubovoľne veľké bez toho aby sa zväčšila veľkosť vstupu. Takéto riešenie nazývame pseudopolynomiálne.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define For(i,n) for(int i=0; i<(n); i++)

typedef pair<int,int> pii;

int main() {
    int n,s;
    scanf("%d %d",&n,&s);
    vector<pii> K; K.resize(n);
    For(i,n) scanf(" %d %d",&K[i].first,&K[i].second);
    vector<int> Vys; Vys.resize(n);
    vector<int> M; M.resize(n);
    For(i,n)
        if(K[i].first < K[i].second) {M[i]=K[i].second-K[i].first; s-=K[i].first; Vys[i]=0;}
        else {M[i]=K[i].first-K[i].second; s-=K[i].second; Vys[i]=1;}
    if(s<0) {printf("A je to v ...\n"); return 0;}
    vector<int> V; V.resize(s+47,0); V[0]=1;
    vector<int> S; S.resize(s+47,-1);
    For(i,n) {
        for(int j=s; j>=0; j--) {
            if(V[j] == 0) continue;
            if(j+M[i]>s) continue;
            if(V[j+M[i]]==1) continue;
            V[j+M[i]]=1; S[j+M[i]]=i;
        }
    }
    if(V[s] == 0) {printf("A je to v ...\n"); return 0;}
    int kde=s;
    while(kde!=0) {
        Vys[S[kde]]=1-Vys[S[kde]];
        kde-=M[S[kde]];
    }
    For(i,n) printf("%d",Vys[i]+1);
    printf("\n");
}