5. Obiehanie vzorové riešenie

4 2
1 3 4

1 1 2 2

Jednoduché riešenie simuláciou

Najjednoduchší spôsob na riešenie tejto úlohy je simulovať celý turnaj postupne pre všetky počiatočné pozície Romankovho submitu.

Turnaj môžeme simulovať po úrovniach, pričom pre každú úroveň budeme mať jedno pole so submitmi, ktoré sa na túto úroveň dostali. Na začiatku si vytvoríme jedno pole so všetkými submitmi a Romankov submit vložíme na jednu pozíciu medzi tie ostatné a začneme simulovať. Pre dvojice submitov vedľa seba sa pozrieme na ich úžasnosti a do ďalšieho kola posunieme ten, ktorý je úžasnejší – úžasnosť víťaza uložíme do poľa ďalšej úrovne. Keď príde na rad Romankov submit, stačí zistiť, či je submit, s ktorým súperí, úžasnejší a teda či musí Romanko obetovať horalku. Pozíciu Romankovho submitu na každej úrovni si vieme udržiavať napríklad v jednej premennej. Tento postup opakujeme, až kým nám nezostane v aktuálnej úrovni len jeden submit – ten Romankov.

Takto odsimulujeme celý turnaj pre všetky počiatočné pozície Romankovho submitu a pre každú simuláciu vypíšeme výsledok.

Ako rýchly je tento algoritmus? Potrebujeme \(O(n)\)-krát simulovať turnaj. Turnaj pozostáva z jednotlivých zápasov, presnejšie z porovnaní submitov. Vieme, že po každom porovnaní prestane byť jeden submit v turnaji, teda na vyradenie \(n-1\) submitov potrebujeme spraviť \(n-1\) porovnaní. Každý turnaj má teda \(O(n)\) zápasov a toto riešenie má preto časovú zložistosť \(O(n^2)\). Pri pozornej implementácií vieme dosiahnuť pamäťovú zložistosť \(O(n)\). Naprogramovaním tohto postupu by ste dostali približne 3 body v praktickej časti.

Lepšie riešenie

Stará programátorská múdrosť hovorí, že ak chceme mať efektívny algoritmus, tak nesmieme nič počítať zbytočne a tiež nesmieme nič počítať dvakrát. Robíme niečo zbytočne? Simulujeme napríklad veľmi veľa zápasov, ktoré sa Romanka takmer vôbec netýkajú. Takisto veľmi veľa krát simulujeme presne rovnaké zápasy.

Najprv ale zaveďme trošku formálnejšie pojmy, aby sme sa mohli jednoduchšie vyjadrovať. Prečíslujme si submity ostatných ľudí ako \(a_0\) až \(a_{n-2}\) (za číslovanie od \(1\) v zadaní sa ospravedlňujeme). Označme si pozície na začiatku ako \(p_0, p_1\) až \(p_{n-1}\).

Prvým pozorovaním zistíme, čo sa vlastne deje pri jednotlivých zápasoch. V každom zápase proti sebe súperia najúžasnejšie submity z konkrétnych intervalov.

• V prvom kole spolu súperia ,,reprezentanti’’ intervalov dĺžky \(1\) (\(p_0\) proti \(p_1\), \(p_2\) proti \(p_3\), atď.).

• V druhom kole sú to už reprezentanti intervalov dĺžky \(2\) (víťaz z \(p_0\) až \(p_1\) proti víťazovi z \(p_2\) až \(p_3\)).

• V treťom kole sú to intervaly dĺžky \(4\) ( víťaz z \(p_0\) až \(p_3\) proti víťazovi z \(p_4\) až \(p_7\)).

Podobne to ide aj pre ďalšie kolá. Kto ale môže byť reprezentantom pre jeden konkrétny interval? Vždy je to buď najúžasnejší submit z daného intervalu, alebo je to Romanko.

Druhým pozorovaním je, že to, aký submit začína na pozícií \(p_i\) závisí len od umiestnenia Romankovho submitu.

• Ak je Romankov submit naľavo od \(p_i\), tak na \(p_i\) je submit \(a_{i-1}\).

• Ak je Romankov submit napravo, tak na \(p_i\) je submit \(a_i\).

Toto vieme povedať aj pre celé intervaly. Uvažujme interval \(p_x\) až \(p_y\), na ktorom sa nenachádza Romankov submit. Potom sa na tomto intervale nachádzajú buď submity \(a_x\) až \(a_y\) (ak je Romankov submit napravo od tohoto intervalu), alebo \(a_{x-1}\) až \(a_{y-1}\) (ak je Romankov submit naľavo od tohoto intervalu).

Ako vieme tieto pozorovania využiť? Keď chceme zistiť, s kým musí Romankov submit v nejakom kole bojovať, nemusíme simulovať celý daný podstrom turnaja. Stačí nám len zistiť maximum z \(a_{x-1}\) až \(a_{y-1}\) alebo \(a_x\) až \(a_y\). Na to vieme ľahko použiť maximový intervalový strom.

Každý vrchol stromu reprezentuje jeden interval (čísla v krúžkoch sú začiatok a koniec intervalu) a v každom vrchole si budeme pamätať jedno číslo. Vo vrcholoch na najspodnejšej úrovni budú úžasnosti jednotlivých submitov. Hodnoty zvyšných vrcholov budú vždy maximum z ich dvoch synov. V každom vrchole si budeme teda pamätať úžasnosť víťazného submitu na danom intervale.

Výhodou takéhoto stromu je to, že si ho nemusíme pamätať ako graf – vrcholy a hrany – ale dá sa dobre reprezentovať ako obyčajné pole \(P\) dĺžky \(2n\). Na pozícií \(1\) bude koreň. Na pozíciach \(n\) až \(2n-1\) budú listy. (Na obrázku sú indexy jednotlivých vrcholov v poli \(P\) napísané mimo krúžkov a \(n=8\).) To, čo je najkrajšie na tejto reprezentácií je, že vrchol \(x\) má synov na pozíciách \(2x\) a \(2x+1\) a otca na pozícii \(\lfloor x/2 \rfloor\). Teda napr. vrchol \(7\) má synov \(14\) a \(15\) a otca \(3\). Vieme sa tak po strome rýchlo pohybovať a zistiť víťaza intervalu vo vrchole \(x\) ako \(\max(P[2x], P[2x+1])\).

Intervalový strom vie vo všeobecnosti zistiť maximum na ľubovoľnom intervale v čase \(O(\log n)\). Intervaly, ktorých maximá nás zaujímajú, majú ale vždy dĺžku mocninu dvojky a tak sú ich maximá práve čísla uložené vo vrcholoch intervalového stromu. Vďaka tomu vieme víťazov jednotlivých intervalov zistiť v konštantnom čase – pozretím sa na správny index poľa.

Potrebujeme ale dva intervalové stromy, jeden pre normálne intervaly – ako keby bol Romankov submit na konci (napravo) – a jeden pre posunuté – ako keby bol romankov submit na začiatku (naľavo).

Ako bude teda vyzerať celé riešenie? Najprv si predpočítame víťazov jednotlivých intervalov pomocou dvoch stromov. Ich výpočet nám potrvá \(O(n)\). Najprv uložíme na koniec poľa \(P\) úžasnosti jednotlivých submitov a potom jedným prechodom od konca spočítame víťazov všetkých intervalov.

Ďalej budeme simulovať turnaje, ale tentokrát len zápasy Romankovho submitu. V každom kole vieme pomocou stromov zistiť úžasnosť submitu, s ktorým musí Romankov submit zápasiť (s víťazom niektorého intervalu). Kôl v turnaji je \(O(\log n)\) a zisťovanie maxima nám trvá \(O(1)\). Celý turnaj potrebujeme navyše odsimulovať pre \(O(n)\) pozícií. Máme teda riešenie s časovou zložitosťou \(O(n \log n)\) a s pamäťovou zložitosťou \(O(n)\). Toto riešenie dokázalo dostať v praktickej časti plný počet bodov.

#include <iostream>
#include <algorithm>

using namespace std;

vector<int> max1;
vector<int> max2;
int n, k;

int main(){
    // Nacitame a nainicializujeme
    cin >> n >> k;
    max1.resize(2*n, 0);
    max2.resize(2*n, 0);
    vector<int> submits(n-1);
    for(int i = 0; i < n - 1; i++){
        cin >> submits[i];
    }

    // Pripravime maximovy strom
    for(int i = 0; i < n-1; i++){
        max1[n+i+1] = submits[i];
        max2[n+i] = submits[i];
    }
    
    max1[n+0] = k;
    max2[n+n-1] = k;
    for(int i = n-1; i >= 0; i--){
        max1[i] = max(max1[2*i], max1[2*i+1]);
        max2[i] = max(max2[2*i], max2[2*i+1]);
    }
    
    // Prejdeme vsetky pozicie
    for(int i = 0; i < n; i++){
        int position = n+i;
        int answer = 0;
            
        while (position > 1){ 
            int new_position = position/2;
            if (new_position*2 == position){ // Romankov submit bol nalavo
                if (max1[position+1] > k)
                    answer += 1;
            }
            else{                            // Romankov submit bol napravo
                if (max2[position-1] > k)
                    answer += 1;
            }
            position = new_position;
        }

        cout << answer << ((i==n-1) ? '\n' : ' ');
    }
    return 0;
}

Optimálne riešenie

Riešenie však vieme ešte zefektívniť. Stále totiž robíme niektoré veci viackrát. Pozrime sa na posledný zápas. Koľkokrát sa spýtame na maximum z intervalu \(p_{0}, p_{\frac{n}{2}}\)? Vždy, keď Romankov submit začína v intervale \(p_{\frac{n}{2}}, p_{n-1}\), čo je presne \(\frac{n}{2}\) krát. Nevieme sa tohto počítania nejako zbaviť? Vieme!

Ak nám vadí, že sa na nejaký zápas pozeráme viackrát, pozrime sa naň len raz. Napríklad pre posledný zápas máme dve možnosti: buď bol Romankov submit na pozíciách z intervalu \(A = (p_0, p_{\frac{n}{2}})\), alebo \(B = (p_{\frac{n}{2}}+1, p_{n-1})\). Ak bol na intervale \(A\), tak vieme, ktoré submity boli na intervale \(B\) a teda vieme, s kým bude Romankov submit súperiť. To ale znamená, že pre všetky pozície z intervalu \(A\) vieme povedať, či bude musieť Romanko v danom zápase musieť obetovať horalku. Toto isté vieme zjavne urobiť pre pozície z intervalu \(B\).

Následne môžeme samostatne riešiť prípady, keď bol Romankov submit v intervaloch \(A = (p_0, p_{\frac{n}{4}})\) a \(B = (p_{\frac{n}{4}}+1, p_{\frac{n}{2}})\) a v podobných intervaloch v druhej polovici všetkých pozícií. To, že sú intervaly do seba tak pekne vnorené, navádza na použitie rekurzie.

Kým v predošlých riešeniach sme počítali výsledky zdola nahor – pre každú pozíciu Romankovho submitu sme simulovali súboje od prvého po posledný, teraz budeme úlohu riešiť zhora nadol. Pre všetky možné pozície Romankovho submitu najprv zistíme, v ktorých z nich musel obetovať horalku v poslednom súboji, v ďalšej úrovni rekurzie zistíme, na ktorých pozíciách musel obetovať horalku v predposlednom súboji, atď.

Pozrime sa na interval \(I\) pozícií \((p_x, p_y)\). Tento interval si rozdeľme na úsek \(A = (p_x, p_{\frac{x+y}{2}})\) a \(B = (p_{\frac{x+y}{2}}+1, p_y)\).

• Ak bol Romankov submit v intervale \(B\), musel poraziť najúžasnejší submit z \(A\). Jeho úžastnosť vieme ľahko nájsť v našom intervalovom strome, pretože na pozíciách \(p_x, p_{\frac{x+y}{2}}\) budú submity \(a_x, a_{\frac{x+y}{2}}\). V rekurzii si ako parameter posielame počet horaliek, ktoré musel Romanko zatiaľ obetovať. Tento počet zvýšime, ak je víťaz intervalu \(A\) úžasnejší ako Romankov submit, a zavoláme sa rekurzívne na interval \(B\).

• Pokiaľ je Romankov submit z intervalu \(A\), musíme si dávať trochu pozor. V \(B\) totiž budú submity \(p_{\frac{x+y}{2}}, p_y-1\), lebo Romanko je od nich naľavo. Pre tie máme druhý intervalový strom. Opäť porovnáme Romankov submit s víťazom \(B\) a rekurzívne sa zavoláme na \(A\).

• Ak je náš interval \(I\) jednoprvkový, rekurziu ukončíme a v posielanom parametri sme dostali odpoveď pre danú pozíciu – koľko horaliek musel Romanko obetovať, ak začínal na pozícii \(i, I = (p_i, p_i)\).

V riešení teda najprv zavoláme rekurzívnu funkciu na celý interval pozícií \((0, n-1)\) s nula obetovanými horalkami. Následne sa v každom volaní rozdvojíme na intervaly \(A\) a \(B\).

Toto krásne riešenie má časovú zložitosť \(O(n)\). Každé rekurzívne volanie spravíme v konštantnom čase, na každý interval sa totiž zavoláme práve raz a intervalov dĺžky \(1\) je \(n\), intervalov dĺžky \(2\) je \(n/2\), atď. a teda \(n + n/2 + n/4 + \dots + 2 + 1 = 2n - 1\) (\(n\) je mocninou dvojky).

#include <iostream>
#include <algorithm>

using namespace std;

vector<int> ans;
vector<int> max1;
vector<int> max2;
int n, k;

void solve(int down, int up, int pozition, int horalky){
    if(down == up){ // Interval ubsahuje len jednu poziciu
        ans[down] = horalky;
        return ;
    }
    int middle = (down+up)/2;

    // Volanie na prvy interval (A)
    solve(down, middle, 2*pozition, horalky + ((max1[2*pozition+1] > k) ? 1 : 0));
    
    // Volanie na druhy insterval (B)
    solve(middle+1, up, 2*pozition + 1, horalky + ((max2[2*pozition] > k) ? 1 : 0));
}

int main(){
    cin >> n >> k;
    ans.resize(n,0);
    max1.resize(2*n, 0);
    max2.resize(2*n, 0);
    vector<int> submits(n-1);
    for(int i = 0; i < n-1; i++){
        cin >> submits[i];
    }
    for(int i = 0; i < n-1; i++){
        max1[n+i+1] = submits[i];
        max2[n+i] = submits[i];
    }
    
    max1[n+0] = k;
    max2[n+n-1] = k;
    for(int i = n-1; i >= 0; i--){
        max1[i] = max(max1[2*i], max1[2*i+1]);
        max2[i] = max(max2[2*i], max2[2*i+1]);
    }

    solve(0, n-1, 1, 0);

    cout << ans[0];
    for(int i = 1; i < n; i++){
        cout<<" "<<ans[i];
    }
    cout << endl;
    return 0;
}