8. Algorytmycké problémy vzorové riešenie

3 4
9 8 9
5 3 4 10
2 1 2
2 2 3
2 3 4

5

Najskôr zlé riešenie

Poznámka od autora: veľmi ťažko sa mi vyrábali vstupy, ktoré by toto nesprávne riešenie neprešlo, pretože sa veľmi podobá správnemu. Niekedy nie je zlé začať aj s niečím nesprávnym a skúsiť to opraviť.

Pre každý problém skúsime nakódiť čo najviac jeho algoritmov, ale len toľko, na koľko nám ešte “vyjde potešenie”. Teda postupne skúšame kódiť ešte nenakódené algoritmy potrebné na vyriešenie problému a zakaždým znížime potešenie, ktoré za problém získame. Skončíme v momente, keď by pridaním ďalšieho algoritmu získané potešenie vyriešenia problému kleslo pod nulu.

Toto riešenie samo o sebe prejde na nejakých vstupoch.

Môžeme skúsiť spraviť viac iterácií tohoto postupu, možno sa to zlepší… Ak by sme boli veľmi šikovní a mali nejaké ďalšie nápady a k tomu trochu šťastia, mohli sme už teraz oklamať testovač a získať aj nejaké body. My si však ukážeme ako sa táto úloha mala riešiť.

Len to opravme

Uvedomme si, kde toto riešenie zlyhá. Na to si najprv lepše pomenujme, čo vlastne robí.

Pre každý algoritmus, ktorý nakódime, vyberieme nejaký problém, ktorý za neho “zaplatí”. Takto to budeme volať aj vo zvyšku vzoráku. Náš program naivne rozhoduje, ktorý problém zaplatí za ktorý algoritmus. Keďže ešte nemáme OK, tak to zjavne robí neoptimálne.

Môžeme si všimnúť \(2\) problémy:

1. V optimálnom riešení môže niekedy zaplatiť za jeden algoritmus aj viac ako jeden problém, čo náš program nezistí.
2. Niekedy môžeme určiť, že za algoritmus \(x\) zaplatí problém \(p\) určitú hodnotu potešenia, ale optimálne by bolo, aby zaplatil menej. To sa nám však už nikdy nepodarí, lebo sa nevraciame späť.

Prvý problém je ľahké vyriešiť. Namiesto toho, aby sme vždy určili nejaký problém, ktorý zaplatí za algoritmus, určíme len nejaký problém, ktorý algoritmu zaplatí \(1\) potešenie. Síce musíme náš postup zopakovať veľakrát, ale to sa ukáže ako jednoduchá vec.

Druhý problém už nie je až tak triviálne riešiť, ale predstavme si to takto. Sme v nejakom stave, kde máme záznamy tipu problém \(p\) platí algoritmu \(x\) jedno potešenie. Predstavme si, že chceme nájsť problém, ktorý zaplatí algoritmu \(x\), ale všetky problémy, ktoré potrebujú \(x\) už nemajú potešenie navyše. Potom môžeme spraviť nasledovnú úpravu. Vyberieme nejaký problém \(p\), ktorý potrebuje algoritmus \(x\), ale platí nejakému inému algoritmu \(y\). Ak existuje problém \(q\), ktorý potrebuje algoritmus \(y\) a ešte má potešenie navyše, môže \(q\) zaplatiť jedno potešenie algoritmu \(y\), tým pádom \(p\) nemusí platiť \(y\) a môže zaplatiť \(x\).

Takto sme vlastne presunuli potešenie z \(q\) do \(x\), a nič iné sa nezmenilo. Teda okrem toho, kto komu platí, ale to nás v skutočnosti nezaujíma.

V pôvodnom nesprávnom riešení hľadáme len problémy \(p\). Teraz máme ešte stále nesprávne riešenie, lebo hľadáme len problémy \(q\) vzdialené jednu iteráciu hľadania (len jeden krát sa vrátime naspäť).

Túto myšlienku však môžeme aj zovšeobecniť. Nebudeme hľadať len problémy \(q\), ktoré ešte majú potešenie, ale budeme hľadať aj hlbšie a vždy vzdialenejšie problémy, ktoré ešte majú potešenie.

Toto je vlastne celá myšlienka vzoráku, vo zvyšku už len dokážeme správnosť a pozrieme sa na implementáciu. Naozaj to nebolo až tak ťažké, že? A ukáže sa to ešte omnoho jednoduchšie.

Vyzerá to povedome

Môžme si celú úlohu predstaviť ako bipartitný graf. Problémy sú napravo a algoritmy naľavo. Hrany vedú medzi algoritmom a problémom vtedy, ak problém algoritmus potrebuje.

Vždy, keď určíme, že nejaký problém platí nejakému algoritmu, vlastne sme povedali, že hrana medzi nimi má smerom k algoritmu o \(1\) väčšiu hodnotu (je jedno, ktorým smerom to povieme, ale je dobré si nejaký vybrať).

Keď hľadáme problém, ktorý zaplatí za algoritmus \(x\), robíme vlastne jednoduché prehľadávanie. Vždy sa najskôr skúsime vrátiť nejakou hranou (toto je ekvivalentné tomu, že nejaký problém potrebuje algoritmus \(x\)), čím najdeme naše \(p\). Potom z \(p\) ideme hranou, po ktorej ide niečo v smere (teda \(p\) platí niekomu inému) ďalej znovu nejakou hranou… Toto opakujeme, až kým nenájdeme problém \(q\), ktorý má ešte voľné potešenie. Teraz pošleme všetkými hranami, ktorými sme prešli jedno potešenie opačným smerom.

Môžme si ukázať, ako by taký beh našeho programu mohol vyzerať. Máme \(3\) algoritmy s cenami \(11\), \(4\) a \(3\) potešenia a \(2\) problémy, ktoré dajú \(2\) a \(13\) potešenia. Takto nejako by mohol náš algoritmus pridelovať, kto komu platí:

Prvé \(3\) kroky by zvládol aj nesprávny algoritmus zo začiatku. Preto je pre nás zaujímavý zelený krok. V tomto kroku má algoritmus \(13\) ešte jedno voľné potešenie. Toto voľné potešenie pridelí algoritmu \(11\), tomu zoberie jedno potešenie od problému \(2\) a to pridelí \(4\).

DOKEDY???

Ako môžeme vidieť na obrázku, niektoré kroky nášho algoritmu je dobré robiť, lebo nám zlepšujú odpoveď. Ak by sme si však pred zeleným krokom povedali, že už máme dosť, a chceli by sme – nedajbože – teraz skúmať odpoveď spôsobom: \(13\) má ešte jedno voľné potešenie a jej algoritmy sú zaplatené teda odpoveď je \(1\). Dopracujeme sa k nesprávnemu riešeniu.

Ukážeme si ale, že ak vykonáme maximálny počet krokov, dokážeme zistiť, aké je optimálne riešenie.

Zjavne ak má nejaký problém na konci algoritmu ešte nejaké potešenie, určite ho v optimálnom riešení vyriešime. POZOR okrem toho môžeme vyriešiť aj nejaké iné problémy, ktoré majú už teraz potešenie \(0\). Keďže stačí výsledok len povedať a nie aj skonštruovať, ukáže sa, že na získanie výsledku stačí len sčítať pozitívne hodnoty. Naozaj to je ľahké.

Nech po vykonaní maximálneho počtu krokov existuje nejaký problém \(p\), ktorý má ešte voľné potešenie. Z maximálnosti počtu krokov vieme, že všetky algoritmy, s ktorými je spojený, už sú zaplatené. Zlé jazyky by však mohli povedať nasledovné: Čo ak je medzi algoritmami susednými s \(p\) nejaký algoritmus \(x\), za ktorý platí problém \(q\), ktorý ale nevyriešime?

Toto je seriózny problém. Potom by sme nemohli povedať, že vyriešime \(p\), lebo by sme vyriešenými problémami nezaplatili za algoritmi potrebné na jeho vyriešenie – \(q\) nie je vyriešený, ale platí za algoritmy pre \(p\). Avšak zlé jazyky si neuvedomujú silu toho, že niečo robíme maximálny počet krát! Keďže \(q\) sme nevyriešili, existuje algoritmus \(y\) susedný s \(q\), ktorý nie je zaplatený. Teda existuje cesta \(p \to x \to q \to y\), po ktorej môžeme poslať nejaké potešenie, keďže \(p\) ešte potešenie má. Teda sme mohli ešte raz zopakovať náš algoritmus, čo je spor.

Ak teda náš postup opakujeme, kým sú v grafe cesty, po ktorých vieme poslať potešenie, mali by sme ľahko vedieť povedať, aký bude maximálny profit – iba sčítame tie, ktoré ešte majú potešenie nazvyš.

Už máme všetko dokázané, preto sa môžme veselo pustiť do implementácie. Ukážeme si však trik, ktorý nám pomôže použiť radšej staré známe algoritmy, ako sa mordovať s implementáciou, aj keď verím, že by to nebolo zas tak náročné.

Implementácia

Namiesto toho, aby sme mali pre každý vrchol to, koľko potešenia nám pridá, môžeme do grafu pridať jeden vrchol, ktorý je nekonečným zdrojom potešenia a je spojený so všetkými problémami hranou. Po tejto hrane môže prejsť maximálne toľko potešenia, koľko potešenia nám dá vyriešenie daného problému. Zjavne v takomto upravenom grafe hľadáme cestu z tohto zdroja do nejakého algoritmu, za ktorý ešte nie je zaplatené, pričom nechceme prekročiť kapacitu na žiadnej hrane.

Ďalej si vieme podobne pridať ešte jeden vrchol spojený so všetkými algoritmami. Tento vrchol bude nekonečným pohlcovačom potešenia, kde hrany do neho budú mať rovnaké kapacity ako ceny daných algoritmov.

Hrany od problémov k algoritmom majú nekonečné kapacity.

Teraz keď nájdeme cestu medzi pridanými vrcholmi¹, pošleme po nej nejaké potešenie a zapamätáme si aj, koľko potešenia môžeme vrátiť naspäť. (zelená cesta z obrázka vráti po hornej hrane jedno potešenie, lebo ňou išli \(2\) v opačnom smere) To vieme napríklad implementovať tak, že opačným hranám sa zvýši kapacita.

V tomto grafe môžeme postupne hľadať nejakú cestu zo zdroja do stoku pomocou prehladávania (napríklad DFS) a poslať po nej jedno potešenie.

Dokonca môžeme po ceste rovno poslať maximum potešenia, ktoré sa ešte zmestí do kapacity hrán na ceste.

Takéto riešenie mohlo dostať \(6\) z \(8\) bodov. Na \(8\) bodov stačilo DFS vymeniť za BFS. Teda vždy nájsť najkratšiu cestu zo zdroja do stoku².

Toto je koniec vzoráku, ale ako by to bolo, kebyže sa to nedá napísať celé oveľa kratšie pohromade.

A čo to vlastne robíme?

Už som naznačil aj terminológiou, že hľadáme maximálny tok v sieti. Nám sa však oplatí pozrieť na celú úlohu ako na minimálny rez, keďže tieto hodnoty sú rovnaké.

Čo je rez v sieti? Vyberieme nejaké hrany, tie “prerežeme” a musí platiť, že v novej sieti sa nedá dostať zo zdroja do stoku.

Jedna možnosť je napríklad prerezať všetky hrany medzi algoritmami a problémami. My však chceme nájsť takú možnosť, kde súčet hodnôt potešenia na hranách rezu je najmenší možný.

Takže celý vzorák by vlastne mohol byť takýto:

Zoberieme náš graf aj s pridaným zdrojom a stokom a nájdeme v ňom minimálny rez. Tento rez zjavne nebude obsahovať žiadne hrany, ktoré vedú z algoritmov do problémov, lebo tie majú kapacitu nekonečno.

Rez si interpretujeme takto:

1. Ak prerežeme nejakú hranu zo zdroja do problému, znamená to, že tento problém nevyriešime.
2. Ak prerežeme nejakú hranu z algoritmu do stoku znamená to, že tento algoritmus nakódime.

Všimnime si, že ak sa rozhodneme nejaký problém vyriešiť, znamená to, že nakódime všetky jeho susedné algoritmy, lebo inak by sme nedostali rez.

Obe možnosti pre nás znamenajú stratu potešenia, ak teda na začiatku sčítame potešenie pre všetky problémy a odčítame hodnotu minimálneho rezu, dostaneme požadovaný výsledok.

Počítať minimálny rez môžme Edmonds-Karpovým algoritmom, ktorý sme si vlastne trošku obrazne ukázali vyššie – to je ten s BFS.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define inf 1e18

struct EdmondsKarp {
    vector<unordered_map<ll, ll>> g;
    vector<ll> vis;
    vector<ll> pred;
    EdmondsKarp(ll n) : g(n), vis(n), pred(n, -1) {}
    void addEdge(ll a, ll b, ll c, ll rc = 0) {
        g[a][b] = c;
        g[b][a] = rc;
    }
    ll bfs(ll s, ll t) {
        fill(begin(pred), end(pred), -1);
        queue<ll> q;
        q.push(s);
        pred[s] = -2;
        while (!q.empty() && pred[t] == -1) {
            ll v = q.front();
            q.pop();
            for (auto e : g[v]) {
                if (pred[e.first] == -1 && e.second) {
                    pred[e.first] = v;
                    q.push(e.first);
                }
            }
        }
        if (pred[t] != -1) {
            ll f = inf;
            for (ll i = t; i != s; i = pred[i]) {
                f = min(f, g[pred[i]][i]);
            }
            for (ll i = t; i != s; i = pred[i]) {
                if ((g[pred[i]][i] -= f) <= 0) g[pred[i]].erase(i);
                g[i][pred[i]] += f;
            }
            return f;
        }
        return 0;
    }
    ll calc(ll s, ll t) {
        ll ans = 0;
        while (ll p = bfs(s, t)) {
            ans += p;
        }
        return ans;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n), b(m);
    for (auto &i : a) cin >> i;
    for (auto &i : b) cin >> i;
    ll nn = n + m, s = nn, t = nn + 1;
    EdmondsKarp f = EdmondsKarp(nn + 2);
    for (ll i = 0; i < n; i++) {
        ll ni;
        cin >> ni;
        for (ll j = 0; j < ni; j++) {
            ll tool;
            cin >> tool;
            tool--;
            f.addEdge(tool + n, i, inf);
        }
    }
    for (ll i = 0; i < m; i++) {
        f.addEdge(s, i + n, b[i]);
    }
    ll sum = 0;
    for (ll i = 0; i < n; i++) {
        sum += a[i];
        f.addEdge(i, t, a[i]);
    }
    cout << sum - f.calc(s, t) << endl;
}

Zložitosť tohoto algoritmu, je trochu paradoxne \(O(VE^2)\), kde \(V\) je počet vrcholov a \(E\) je počet hrán. V našom prípade \(V=n+m\) a \(E \in O(nm)\), čo pre obmedzenia zo zadania dáva dosť zlú časovú zložitosť.

Doležité sú \(2\) veci:

1. Táto zložitosť je najhorišia možná a veľakrát bude algoritmus bežať omnoho rýchlejšie, ako aj v našom prípade, čo závisí od toho ako sieť vyzerá.
2. Dá sa to aj rýchlejšie nejakými inými tokovými algoritmami, avšak pre rámec tejto úlohy a vzoráku to nie je podstatné.