5. Kamenná cesta vzorové riešenie

7
7 3 15 7 2 8 6

7

Ak si zoberieme všetky dni, v ktorých vieme prejsť na druhý breh rieky, zadanie od nás chce, aby sme našli posledný (najväčší) deň, v ktorom je to možné. Ako prvé je preto dobré si rozmyslieť, ako veľké takéto číslo môže byť, čo nám ohraničí výsledok.

Existuje pre každý vstup aspoň nejaké riešenie? Kedže pre deň, v ktorom je \(i\)-ty kameň ešte použiteľný, \(k_i\) platí, že \(k_i\geq 1\), tak ľahko vidieť, že v prvý deň vieme určite použiť všetky kamene a dostať sa na druhú stranu. Existuje aj horné ohraničenie? Inými slovami, existuje deň, kedy už nevieme cez rieku v žiadnom prípade prejsť?

Takéto ohraničenie by neexistovalo iba keby nepotrebujeme žiadny kameň na prejdenie rieky, kedže po určitom čase bude každý zaplavený. Kedže vieme preskočiť iba jeden kameň a pre počet kameňov \(n\) platí nerovnosť \(n\geq 2\) tak máme zaručené, že musíme použiť aspoň jeden kameň na prejdenie rieky. Vieme teda, že rieku určite neprejdeme v deň, kedy už bude zatopený aj posledný kameň. Môžeme si uvedomiť, že tento deň je o jedna väčší ako maximum z hodnôt \(k_1, k_2, \dots k_n\).

Zistili sme, že správna odpoveď sa nachádza niekde medzi hodnotami 1 a \(\max(k_1, k_2 \dots k_n) + 1\). To je super, pretože môžeme postupne vyskúšať všetky tieto hodnoty a nájsť najväčšiu vyhovujúcu.

Povedzme, že máme nejaký konkrétny deň \(r\). Chceme zistiť, či vieme prekročiť rieku iba pomocou doteraz nezatopených kameňov. Teda platí, že kameň \(j\) môžeme použiť iba ak \(k_j\geq r\). Môžeme si vytvoriť pomocné pole o veľkosti \(n\) a doňho si zaznačiť, na ktoré políčka sa vieme dostať z ľavého brehu. Pri vypĺňaní \(i\)-teho políčka sa nám stačí pozrieť, či je možné sa dostať buď na políčko \(i-1\) alebo \(i-2\). Ak áno a platí, že \(k_i\geq r\), tak sa vieme dostať v \(r\)-tý deň aj na \(r\)-té políčko a do pomocného poľa zaznačíme , inak . Na konci vieme z hodnôt na indexoch \(n-1\) a \(n\) v našom pomocnom poli zistiť, či v daný deň vieme rieku prekročiť. Rieku prekročíme iba ak sa na jedno z týchto políčok vieme dostať.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool over(vector<int>& kam, int den)
{
    int n = kam.size();
    // na zaciatku oznacime vsetko ako nedosiahnutelne
    vector<bool> pom(n, false);
    
    if(kam[0] <= den) pom[0] = true;
    if(kam[1] <= den) pom[1] = true;
    
    for(int i=2; i<n; ++i) {
        if(kam[i] >= den && (pom[i-1] || pom[i-2])) {
            pom[i] = true;
        }
    }
    if (pom[n-1] == true || pom[n-2] == true) {
        return true;
    }
    else {
        return false;
    }
}

int main()
{
    int n; cin >> n;

    vector<int> kamene(n);
    for(int i=0; i<n; ++i) {
        cin >> kamene[i];
    }
    
    int maxim = kamene[0];
    for(int i=1; i<n; ++i) {
        maxim = max(maxim, kamene[i]);
    }
    
    for(int i=maxim; i>=1; --i) {
        if(over(kamene, i)) {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

V pythone si ukážeme mierne inú implementáciu a to bez pomocného poľa. Je založená na pozorovaní, že z nášho pomocného poľa nám vždy stačí poznať iba posledné dve vypočítané hodnoty (pozície \(i-2\) a \(i-1\)).

def over(kam, den):
    pred, pred2 = True, True
    
    for i in range(len(kam)):
        if (pred == False and pred2 == False):
            break

        pred2 = pred
        pred = False

        if (kam[i] >= den):
            pred = True
    
    return (pred or pred2)

            
n = int(input())
kamene = [int(_) for _ in input().split()]

maxim = max(kamene)

for i in range(maxim, 0, -1):
    if over(kamene, i):
        print(i)
        break

Toto riešenie je správne, ale má časovú zložitosť závislú od maximálneho \(k_i\), ktoré môže byť oveľa väčšie ako \(n\). Je teda pomalé, ale stačí na riešenie prvej a tretej sady.

Riešenie hrubou silou ide v skutočnosti vylepšiť ďalším pozorovaním. Samotné overovanie nejakého konkrétneho riešenia \(r\) nezrýchlime. To čo sme robili doteraz je, že sme overili všetky hodnoty medzi \(1\) až \(\max(k_0, k_1, \dots k_n)\) a vybrali najväčšie riešenie. Myšlienkou zrýchlenia je, že pokiaľ ide prejsť rieku v \(i\)-ty deň tak je to možné aj v každý skorší deň. Prečo? Pokiaľ sme v \(i\)-ty deň použili nejaké kamene, pomocou ktorých sme vedeli prejsť na druhú stranu rieky. Vieme presne tie isté kamene použiť aj v hociktorý skorší deň. To platí aj opačne, ak nevieme v \(i\)-ty deň prejsť rieku, nepôjde to ani neskôr. To preto, že neskôr bude zatopených už len viac kameňov. Toto nám umožnuje použiť techniku známu ako binárne vyhľadanie na nájdenie nášho riešenia.

Pointa binárneho vyhľadávania je, že namiesto overenia hodnôť \(1\) až \(\max(k_0, k_1, \dots k_n)\) nám postačuje overiť riešenie pre číslo, ktoré je v strede, medzi \(1\) a \(\max(k_0, k_1, \dots k_n)\). Označme si ho \(s\). Pokiaľ platí, že v \(s\)-tý deň sa dá prejsť cez rieku tak vieme, že naše riešenie bude väčšie alebo rovné ako \(s\). Pokiaľ v \(s\)-tý deň nevieme rieku prejsť, riešenie bude menšie ako \(s\). V oboch prípadoch sa nám počet čísel, ktoré môžu byť riešením zmenšil približne o polovicu. Tento postup vieme ďalej opakovať na novo nájdené ohraničenia našeho riešenia až kým nám neostane jedno číslo, ktoré je výsledkom.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// na overenie mozeme pouzit funkciu z predchadzajuceho riesenia
bool over(vector<int>& kam, int den);

int main()
{
    int n; cin >> n;
    
    vector<int> kamene(n);
    for(int i=0; i<n; ++i) {
        cin >> kamene[i];
    }
    
    int maxim = kamene[0];
    for(int i=1; i<n; ++i) {
        maxim = max(maxim, kamene[i]);
    }
    
    int l = 0, h = maxim+1;
    while (l+1 < h) {
        int stred = (l + h) / 2;

        if (over(kamene, stred)) {
            l = stred;
        }
        else {
            h = stred;
        }
    }
    
    cout << l << endl;
    
    return 0;
}

V predchádzajúcich riešeniach nám vadilo, že naše riešenia boli závislé od maximálneho \(k_i\). Poďme skúsiť nájsť riešenie, ktoré je závislé len od \(n\). Urobíme to tak, že sa pozrieme bližšie na samotnú hodnotu najlepšieho riešenia.

Vieme, že najlepšie riešenie leží medzi 1 a \(\max(k_1, k_2, \dots k_n)\). Tvrdíme však, že toto riešenie musí byť rovná niektorému z \(k_i\). Viete prečo? Povedzme si, že by nebolo. Potom ale určite existujú kamene, po ktorých vieme preskákať v tento deň a jeden z nich, označme si ho \(j\), má najnižšiu hodnotu \(k_j\). Naše riešenie nemôže byť najlepšie pretože od tohto riešenia existuje lepšie riešenie rovné \(k_j\). To používa kamene z nášho predchádzajúceho riešenia a pritom je určite väčšie. Po tejto úvahe už vieme, že riešenie bude určite rovné niektorému z hodnôt \(k_1, k_2, \dots k_n\). To znamená, že nám stačí overiť \(n\) hodnôt, každú v čase \(O(n)\), čo nám prinesie riešenie s časovou zložitosťou \(O(n^2)\).

Síce na vyriešenie úlohy na plný počet bodov stačilo aj riešenie z časti , my si teraz ukážeme jedno ešte rýchlejšie a elegantnejšie riešenie. Jeho myšlienka je nasledujúca.

Kedy určite rieku nevieme prejsť? Predsa keď budú zatopené dva za sebou ležiace kamene! Takto veľkú medzeru totiž nevieme preskočiť a ostaneme zaseknutý. Dvojica kameňov \(i\) a \(i+1\) bude zatopená keď sa zatopí ten neskorší, teda v čase \(\max(k_i, k_{i+1}) + 1\). Zo všetkých dvojíc však chceme zobrať tú najskoršie zatopenú, prvá dvojica kameňov bude teda zatopená v čase \(\min(\max(k_1, k_2) + 1, \max(k_2, k_3) + 1, \dots \max(k_{n-1}, k_{n}) + 1)\).

My si však musíme odpovedať aj na dôležitejšiu otázku a to, či sa dá prejsť na druhú stranu rieky vždy, keď ešte dvojica za sebou idúcich zatopených kameňov. Ak totiž platí takéto tvrdenie, znamená to, že vyššie určená hodnota je správnou odpoveďou.

Predstavme si, že žiadne dva za sebou idúce kamene nie sú zatopené. Je jasné, že z ľavého brehu máme kam skočiť. V tom momente sa nachádzame na nezatopenom kameni. Ak je nasledujúci kameň nezatopený, jednoducho naň prejdeme a riešime problém ďalej. Ak však zatopený je, ten ďalší zatopený byť nemôže (lebo to by boli už dva za sebou idúce zatopené kamene). Preskočíme teda jeden zatopený kameň a pokračujeme rovnakou úvahou ďalej.

Práve sme dokázali, že v deň \(\min(\max(k_1, k_2), \max(k_2, k_3), \dots \max(k_{n-1}, k_{n})) + 1\) sa cez rieku určite nedostaneme, ale v ľubovoľný skorší deň to ešte pôjde, toto číslo mínus jeden je teda odpoveďou.