5. Optimálna šifrovačka vzorové riešenie

6 6
100
50
300
47
20
15
1 3 10
3 2 40
2 1 50
4 2 70
5 3 60
5 6 30

130

Zopakujme si, ako znie zadanie. Na vstupe máme niekoľko tatranských križovatiek, každú v inej nadmorskej výške. Medzi nimi vedie niekoľko rôzne dlhých chodníkov. Našou úlohou je nájsť čo najdlhšiu cestu, ktorá celý čas klesá.

Celú situáciu si môžeme predstaviť ako graf. Križovatky sú vrcholy a chodníky predstavujú hrany medzi nimi. Uvedomme si však, že po každej hrane môžeme chodiť len jedným smerom – v smere od vyššie položeného vrchola k tomu nižšiemu. Takéto hrany nazývame orientované. Takisto v tomto grafe nemôžu existovať orientované cykly, lebo by to znamenalo, že v nejakom momente sme porušili podmienku klesania. Graf, ktorý nám zaručuje zadanie, je preto orientovaný a acyklický a zvykne sa označovať ako DAG¹.

Skúsme sa teraz pozrieť na to, ako vyzerajú najdlhšie cesty v ňom. Je jasné, že musia začínať vo vrchole, do ktorého nevedie žiadna hrana. V opačnom prípade by sme predsa začali o kúsok vyššie a cestu si predĺžili. Takisto, končiť bude v nejakom vrchole, z ktorého už žiadna hrana nevedie. Oveľa viac však zaručiť nevieme. To však nevadí, pokúsme sa vymyslieť aspoň nejaké prvé riešenie.

Hľadanie všetkých ciest

Prvá možnosť, ktorá nás môže napadnúť, je vyskúšať všetky možné cesty, ktoré v našom grafe existujú a vybrať z nich tú, ktorá bude mať najväčšiu dĺžku. Myšlienkovo je to samozrejme správne riešenie, aj ked tušíme, že nebude až také rýchle. Keď sa ale zamyslíme, ako by sa niečo také dalo naprogramovať, zistíme, že to nebude také jednoduché. Ukážme si preto, ako naprogramovať toto prvé riešenie a potom si ukážeme, ako ho môžeme zlepšiť.

Ako vôbec vyzerá nejaká cesta? Začneme v niektorom najvyššom vrchole. Odtiaľ pôjdeme jednou z jeho hrán do susedného vrchola. Odtiaľ si opäť vyberieme niektorú z hrán, ktoré z neho vedú a takto budeme pokračovať, až kým sa nedostaneme na spodok. Uvedomme si však, že v každom vrchole, v ktorom sa ocitneme, sme v úplne rovnakej situácii. Chceme sa z neho presunúť všetkými možnými spôsobmi do jeho susedov a odtiaľ pokračovať v hľadaní.

Táto myšlienka je teda vo svojej podstate rekurzívna a to vieme patrične využiť a tak ju aj implementovať. Spravíme si teda funkciu najdi(v) s jedným parametrom. Táto funkcia bude mať nasledovnú úlohu: Prejdi všetky cesty, ktoré vedú z vrchola \(v\).

Nech má vrchol \(v\) susedov \(w_1, w_2 \dots w_k\). Ak chceme prejsť všetkými cestami, ktoré vedú z vrchola \(v\), tak musíme ísť z vrchola \(v\) do vrchola \(w_1\) a potom prejsť všetky cesty z tohto vrchola, čo je vlastne len rekurzívne volanie najdi(w1). No a potom musíme tiež ísť z \(v\) do vrchola \(w_2\) a odtiaľ prejsť všetko, čo je volanie najdi(w2). A tak ďalej pre všetkých susedov vrchola \(v\).

Nás však nezaujímajú všetky cesty, ale len tá najdlhšia. Teda chceme prejsť všetkými cestami vedúcimi z vrchola \(v\) a zistiť dĺžku najdlhšej z nich. Je viacero spôsobov, ako vypočítať túto hodnotu. Mohli by sme si dĺžku aktuálne objavovanej cesty posúvať ako ďalší parameter našej funkcie. Mohli by sme si značiť prejdené vrcholy do pomocného poľa a vždy na spodku cesty pomocou neho vyrátať jej dĺžku. Nám sa však bude hodiť (a podľa mňa je to najelegantnejší spôsob), keď si ju budeme vracať ako návratovú hodnotu tejto funkcie. Naša funkcia najdi(v) bude teda vracať dĺžku najdlhšej cesty, ktorá začína vo vrchole \(v\).

Túto hodnotu nie je problém vyrátať. Je to maximum z nasledovných hodnôt: dĺžka hrany z \(v\) do \(w_i\) plus dĺžka najdlhšej cesty z vrchola \(w_i\), čo je najdi(wi), postupne pre všetky možné \(i\). Vďaka tomu dostávame prvé riešenie, ktorého program nájdete nižšie. Odporúčam podrobnejšie si ho preštudovať.

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

int n, m;
vector<vector<pair<int, long long> > > Graf;
vector<int> Vysky;
vector<int> pocet_vchadzajucich_hran;

long long najdi(int v) {
    long long najdlhsia=0;
    // pre vsetkych susedov
    for(int i=0; i<Graf[v].size(); i++) {
        int w = Graf[v][i].first;
        int c = Graf[v][i].second;
        najdlhsia = max(najdlhsia, c+najdi(w));
    }
    return najdlhsia;
}

int main() {
    scanf("%d %d", &n, &m);
    Vysky.resize(n);
    Graf.resize(n); 
    pocet_vchadzajucich_hran.resize(n);
    for(int i=0; i<n; i++)
        scanf(" %d", &Vysky[i]);
    for(int i=0; i<m; i++) {
        int x, y, c;
        scanf(" %d %d %d", &x, &y, &c);
        x--; y--;
        if(Vysky[x] < Vysky[y]) swap(x, y);
        Graf[x].push_back(make_pair(y, c));
        pocet_vchadzajucich_hran[y]++;
    }
    long long vysledok=0;
    // pre vsetky vrcholy, do ktorych nic nevchadza
    for(int i=0; i<n; i++)
        if(pocet_vchadzajucich_hran[i] == 0)
            vysledok = max(vysledok, najdi(i));
    printf("%lld\n", vysledok);
}

Memoizácia

Po odovzdaní tohto riešenia zistíme, že je síce korektné, lebo na prvom vstupe prejde, ale strašne pomalé a na zvyšných prekročí časový limit. To ale neznamená, že postupujeme zle. Možno stačí malá úprava, aby sa naše riešenie zmenilo na vzorové. A ako uvidíte, od vzorového riešenia sa toto skúšanie všetkých možností líši v štyroch riadkoch.

Takmer vždy, keď máme správne, ale pomalé riešenie, (a už tobôž keď ho riešime pomocou rekurzívnej funkcie) oplatí sa položiť si nasledovné otázky: Nepočítame niečo zbytočne? Nepočítame niečo viackrát?

Predstavme si, že máme graf, v ktorom z vrchola \(1\) vedie strašne dlhá cesta – bez odbočiek, jednoducho stále iba jedna možnosť ako sa pohnúť ďalej. Naviac nech existuje veľa vrcholov, do ktorých nevedie žiadna hrana a vychádza z nich jediná hrana do vrchola \(1\).

Výpočet nášho programu na tomto grafe vyzerá nasledovne: začnem v jednom z vrchných vrcholov, posuniem sa do vrchola \(1\), pričom sa zavolá funkcia najdi(1). Tá zistí, že najdlhšia cesta vedúca z vrchola \(1\) má dĺžku \(x\), lebo celú túto cestu prejde. Potom si zoberieme druhý vrchol, do ktorého nič nevedie a opäť sa presunieme do vrchola \(1\). Potom sa opäť zavolá funkcia najdi(1), ktorá vo svojich volaniach prejde celú tú dlhočiznú cestu nadol, aby nám povedala to, čo už dávno vieme. Teda, že najdlhšia cesta z vrchola \(1\) má dĺžku \(x\). A toto sa zopakuje ešte niekoľkokrát.

Môžeme si teda všimnúť, že vždy, keď v našom programe zavoláme funkciu najdi(v), dostaneme tú istú hodnotu. Tá sa totiž nemá prečo meniť. Najdlhšia cesta z tohto vrcholu zostane najdlhšou bez ohľadu na to, z ktorého vrchola sme sem prišli. A to platí pre ľubovoľný vrchol \(v\). Namiesto toho, aby sme spúšťali funkciu najdi(v) viackrát, zapamätáme si, akú hodnotu nám vrátila pri prvom zavolaní. Keď ju budeme chcieť neskôr zavolať znova, jednoducho zistíme, že sme tú hodnotu už vyrátali predtým a vrátime rovno toto vyrátané číslo, čím sa vyhneme celému zbytočnému výpočtu.

Toto celé sa dá implementovať veľmi jednoducho. Vytvoríme si pole memoizacia[], ktoré si bude na \(i\)-tej pozícii pamätať, aká je najdlhšia cesta vedúca z vrchola \(i\). Na začiatku naplníme toto pole hodnotami \(-1\) (alebo niečím iným zbytočným). Následne sa funkcia najdi(v) vždy po zavolaní najskôr pozrie, čo je v poli memoizacia[v]. Ak je tam číslo \(-1\), znamená to, že sme túto funkciu pred tým nerátali. Preto pokračujeme rovnako, ako v prvom riešení, akurát si na konci výsledok zapamätáme na pozícii memoizacia[v]. Ak je ale v memoizacia[v] nejaké nezáporné číslo, vieme, že sme túto funkciu už volali s parametrom \(v\) a toto je jej výsledok, ktorý môžeme rovno vrátiť.

Táto technika, ktorá sa volá memoizácia, je naviac veľmi všestranná, lebo sa dá použiť na každú rekurzívnu funkciu. Občas nie až s tak dobrým výsledkom, ale často krát nám to riešenie výrazne zrýchli.

Zložitosť

Zostáva nám odhadnúť zložitosť tohto riešenia. Uvedomme si, že funkciu najdi(v) budeme rátať najviac raz pre každé \(v\), lebo pri jej ďalších volaniach už stačí vyberať výsledok z poľa memoizacia[]. Počas všetkých týchto rátaní dokopy prejdeme cez každú hranu práve raz, a teda výsledná časová zložitosť bude \(O(n+m)\).

Pamäťová zložitosť je rovnaká, lebo si musíme zapamätať celý vstupný graf. No a ako som sľúbil, tu je vzorový program, v ktorom sa oproti pomalému riešeniu zmenili naozaj iba štyri riadky. Odporúčam vám overiť si to ;)

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

int n, m;
vector<vector<pair<int, long long> > > Graf;
vector<int> Vysky;
vector<int> pocet_vchadzajucich_hran;
vector<long long> memoizacia;

long long najdi(int v) {
    if(memoizacia[v] != -1) return memoizacia[v];
    long long najdlhsia=0;
    // pre vsetkych susedov
    for(int i=0; i<Graf[v].size(); i++) {
        int w = Graf[v][i].first;
        int c = Graf[v][i].second;
        najdlhsia = max(najdlhsia, c+najdi(w));
    }
    memoizacia[v] = najdlhsia;
    return najdlhsia;
}

int main() {
    scanf("%d %d", &n, &m);
    Vysky.resize(n);
    Graf.resize(n);
    pocet_vchadzajucich_hran.resize(n);
    memoizacia.resize(n, -1);
    for(int i=0; i<n; i++)
        scanf(" %d", &Vysky[i]);
    for(int i=0; i<m; i++) {
        int x, y, c;
        scanf(" %d %d %d", &x, &y, &c);
        x--; y--;
        if(Vysky[x] < Vysky[y]) swap(x, y);
        Graf[x].push_back(make_pair(y, c));
        pocet_vchadzajucich_hran[y]++;
    }
    long long vysledok=0;
    // pre vsetky vrcholy, do ktorych nic nevchadza
    for(int i=0; i<n; i++)
        if(pocet_vchadzajucich_hran[i] == 0) 
            vysledok=max(vysledok, najdi(i));
    printf("%lld\n", vysledok);
}