Zadanie

Táto úloha je prebraná z domáceho kola Olympiády v Informatike kategórie B. Riešením tejto úlohy sa teda viete zapojiť aj do Olympiády (odovzdať to však musíte samostatne druhýkrát).

Ak sa Vám úlohy v PRASKu páčia, vyskúšajte si aj riešenie Olympiády, termín jej domáceho kola je do 30. novembra 2019. Riešením domáceho kola máte možnosť postúpiť do kola krajského a skúsiť si riešenie aj v súťažnejších podmienkach a kratšom čase. Na postup na krajské kolo obvylke stačí 10 bodov, takže ak vyriešite túto úlohu a ešte niečo, postup budete mať zaručený.

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahne (liahen.ksp.sk). Keď budeš riešiť sadu conditions_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Andrejovi na ajo@ksp.sk

Jitka sa rozhodla ísť pozrieť Ema do Švajčiarska. Ten sa na jej príchod veľmi tešil a pripravil pre ňu prekvapenie – romantický pobyt v horskej chate. Keď sa však už tretiu hodinu drali hustým lesom na ceste k chate, uvedomil si Emo, že ceny vo Švajčiarsku sú odlišné od tých na Slovensku. A tak za cenu priemerného slovenského ubytovania objednal Emo pomerne podpriemernú chatku uprostred ničoho.

Našťastie, to ich už našiel chatár, ktorý poznal zopár šikovných skratiek a o chvíľu už mali chatku na dohľad. Poslednú prekážku tvorila riečka, z ktorej vytŕčalo veľké množstvo kameňov, po ktorých sa dalo preskákať na druhú stranu. Blíži sa však obdobie dažďov a Emo je nervózny. Ako dlho potrvá, kým sa hladina zdvihne natoľko, že sa už nebude dať dostať na druhú stranu?

Úloha

V rieke sa nachádza cesta tvorená \(n\) kameňmi. Pre každý kameň máme zadané jedno číslo \(k_i\) – poradové číslo posledného dňa kedy je ešte tento kameň nezatopený a dá sa po ňom prejsť.

Pri prechode riekou môžeme samozrejme stúpať iba na nezaplavené kamene. Jedným krokom sa však vieme presunúť nielen na nasledujúci kameň, ale aj na kameň hneď za ním. Vďaka tomu je možné niektoré zaplavené kamene prekročiť.

Vašou úlohou je zistiť, ktorý najneskorší deň sa ešte stále dá dostať z jednej strany rieky na druhý.

Formát vstupu

Na prvom riadku vstupu je číslo \(n\) \((2\leq n\leq 1\,000\,000)\) – počet kameňov v rieke, ktoré tvoria cestu medzi dvoma brehmi.

Na druhom riadku vstupu je \(n\) medzerami oddelených čísel \(k_1, k_2 \dots k_n\). Hodnota \(k_i\) \((1\leq k_i\leq 1\,000\,000\,000)\) označuje posledný deň v ktorý sa bude dať prejsť po \(i\)-tom kameni predtým ako bude zatopený.

Formát výstupu

Na výstup vypíšte jediné číslo \(x\) – posledný deň kedy sa dá prejsť po nezatopených kameňoch z jednej strany rieky na druhú.

Hodnotenie

Sú 3 sady vstupov po 5 bodov. Pre prvú sadu naviac platí, že \(n \leq 1\,000\).

Príklad

Input:

7
7 3 15 7 2 8 6

Output:

7

V 7. deň je zatopený druhý, štvrtý a siedmy kameň, teda tie, ktoré majú ako deň zatopenia číslo menšie ako 7. Pomocou nezatopených kameňov sa dá však stále popreskakovať na druhú stranu rieky. Stačí skočit z brehu na prvý kameň, odtiaľ preskočiť na tretí kameň, posunúť sa na štvrtý, z neho na šiesty a odtiaľ už rovno na druhý breh. Všimnite si, že pri každom skoku, vrátane tých z brehu a na breh, sme preskočili maximálne jeden kameň. V ôsmy deň už nemôžme použiť prvý ani druhý kameň a teda z brehu nevieme skočiť na nezatopený kameň.

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\)\(\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\)\(\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.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.