4. Sekanie bambusu vzorové riešenie

5
1 2 5 3 2

LRRR

4
1 2 4 3

4

V tejto úlohe sme dostali \(n\) čísel. V každom momente sme mohli zobrať buď číslo zľava, alebo sprava. Našou úlohou bolo vytvoriť čo najdlhšiu rastúcu postupnosť.

Rýchlejšie riešenie nie je vždy zložitejšie

Najskôr sa pozrieme na možné riešenia hrubou silou. Nezľaknite sa však toho, že niektoré časti možno nebudú úplne zrozumiteľné hneď na prvý pohľad. Toto je totiž úloha, kde je vzorové riešenie jednoduchšie, ako riešenie hrubou silou.

Hrubá sila

Chceli by sme asi nejak vyskúšať všetky možnosti. Predstavme si, že sme už nejaké čísla zobrali a chceme zobrať ďalšie. Nachádzame sa teda v nejakom stave. Ten vieme popísať troma číslami. Tie budú hovoriť, kde je aktuálne ľavý okraj, kde je aktuálne pravý okraj a aké bolo posledné číslo, ktoré sme zobrali. Nazvime tieto čísla lavy, pravy a posledne. Zo stavu (lavy, pravy, posledne) sa vieme dostať do stavov (lavy + 1, pravy, b[lavy]) a (lavy, pravy - 1, b[pravy]). Samozrejme, do prvého z uvedených stavov sa vieme dostať iba ak b[lavy] > posledne a do druhého sa vieme dostať iba ak b[pravy] > posledne.

Toto nám už stačí na napísanie rekurzívnej funkcie, ktorá bude postupne skúšať všetky validné postupnosti výberov strán, z ktorých berieme. Vždy, keď nájde nejakú postupnosť, ktorá je dlhšia, ako doteraz najdlhšia nájdená, zapamätá si ju ako novú doteraz najdlhšiu nájdenú. Na konci teda stačí vypísať túto najdlhšiu nájdenú postupnosť.

Výsledok teda získame zavolaním funkcie do stavu (lavy = 0, pravy = n - 1, posledne = -1). Ako parameter posledne tu samozrejme môžeme použiť akékoľvek číslo menšie, ako je najkratšia možná dĺžka bambusu.

Časová zložitosť takéhoto riešenia vyzerá ako \(O(2^n)\), pretože v každom rekurzívnom volaní sa zavoláme do dvoch ďalších. Ak ale vhodne spravíme podmienky v našej funkcii, a budeme sa správne rozhodovať, vieme z toho spraviť \(O(n^3)\), či dokonca aj riešenie so zložitosťou \(O(n)\). To, ako sa správne rozhodovať si ukážeme v nasledujúcich sekciách vzoráku. Pamäťová zložitosť bude \(O(n)\).

Takéto rekurzívne riešenie však bude padať na tom, že rekurzia pôjde veľmi hlboko a minie sa nám pamäť.

Stále hrubá sila

Možno jednoduchšou možnosťou, ako spraviť riešenie hrubou silou, je postupne skúsiť všetky možnosti brania zľava a sprava bez rekurzie. Na to vieme použiť niečo, čo sa volá bitmask. Čísla sú v počítači reprezentované v dvojkovej sústave. Sú tam teda iba nuly a jednotky. V \(n\)-bitovom čísle je dokopy \(n\) núl a jednotiek. Predstavme si, že 0 bude reprezentovať výber čísla zľava a 1 bude reprezentovať výber čísla sprava. Potom napríklad číslo 105, ktoré je v dvojkovej sústave 01101001, bude znamenať náš postup výberov strany LRRLRLLR.

Pozrime sa na všetky bitmasky dĺžky 3. Budú to teda čísla \({0, 1, 2, ... 2^3 - 1}\), teda čísla od 0 po 7 vrátane. Tieto čísla v dvojkovej sústave postupne zapíšeme ako 000, 001, 010, 011, 100, 101, 110, 111. Všimnime si, že naozaj žiadna iná kombinácia núl a jednotiek dĺžky 3 neexistuje.

Ak teda vygenerujeme postupne všetky bitmasky dĺžky \(n\) a pre každý overíme, akú najdlhšiu rastúcu postupnosť nám takýto bitmask prinesie, tak určite nájdeme nejaké správne riešenie. To je preto, že skúšame všetky možné postupy.

Naprogramovať niečo takéto je celkom jednoduché. Ako bitmasky budeme používať obyčajné čísla od \(0\) do \(2^n - 1\). Na to sa vám bude hodiť poznať nejaké bitové operácie, no o nich sa tu nejdem rozpisovať a určite si o nich niečo zvládnete naštudovať aj sami.

Časová zložitosť je \(O(2^n \cdot n)\), pretože skúšame \(2^n\) bitmaskov a pre každý zistíme, akú dlhú rastúcu postupnosť vytvorí v \(O(n)\). Pamäťová zložitosť bude \(O(n)\).

Takéto generovanie bitmaskov je použiteľné vo veľmi veľa úlohách na napísanie riešenia hrubou silou. Určite sa teda oplatí ho naučiť používať, pretože vám môže priniesť aspoň čiastočné body v úlohách, ktoré neviete vyriešiť optimálne.

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> v;

int main() {
    cin >> n;
    v.resize(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];

    string ans;
    // Ideme cez bitmasky od 0 po 2^n - 1
    for(int mask = 0; mask < (1 << n); mask++) {
        int last = -1, l = 0, r = n - 1;
        string now;
        for(int j = 0; j < n; j++) {
            if(mask & (1 << j)) {
                if(v[r] <= last)
                    break;
                last = v[r];
                r--;
                now.push_back('R');
            }
            else {
                if(v[l] <= last)
                    break;
                last = v[l];
                l++;
                now.push_back('L');
            }
        }
        if(now.size() > ans.size())
            ans = now;
    }
    cout << ans << '\n';

    return 0;
}

Variant A

V tejto variante boli všetky výšky bambusov rôzne.

Riešenie variantu A je veľmi jednoduché. Vždy chceme zobrať najmenšie číslo, ktoré je väčšie, ako posledné doteraz zobrané.

Prečo to funguje? Ak sú aj ľavé aj pravé číslo menšie, ako posledné zobrané, tak sme skončili. Ak je iba jedno z nich väčšie, ako posledné, tak nemáme moc na výber a zoberieme ho, lebo je to lepšie ako skončiť a nezobrať nič. Čo ak sú obe väčšie, ako posledné zobrané? Ak by sme zobrali väčšie z nich, tak to menšie už nikdy nezoberieme. Dostaneme teda postupnosť nejakej dĺžky \(d\) končiacu na nejaké číslo \(c\). Ak zoberieme menšie z čísel, tak stále budeme môcť zobrať aj to väčšie. Určite tak teda dokážeme vytvoriť postupnosť dĺžky aspoň \(d + 1\) končiacu na \(c\), čo je lepšie, ako prvá možnosť, lebo je dlhšia a končí na rovnaké číslo.

Časová zložitosť tohto riešenia je \(O(n)\), čo je zjavne optimálne, pretože rovnako dlho nám trvá samotné načítanie vstupu. Pamäťová zložitosť bude tiež \(O(n)\).

Variant B

V tejto variante už mohli byť niektoré výšky bambusov rovnaké.

Od riešenia variantu \(A\) k riešeniu variantu \(B\) už nechýba veľa. Postupujeme rovnako, ako vo variante \(A\). Jediná vec, ktorá sa nám doteraz nemohla stať a teraz už môže je, že aj naľavo aj napravo budú rovnaké čísla. Tu si však stačí uvedomiť, že ak zoberieme jedno z nich, tak už nikdy určite nebudeme môcť zobrať to druhé. To znamená, že od momentu, keď sa nám stane, že aj vľavo aj vpravo sú rovnaké čísla, máme iba dve možnosti. Buď zoberieme čo najviac čísel iba zľava, alebo zoberieme čo najviac čísel iba sprava. Ako ale máme vedieť, ktorá z týchto možností je lepšia? Jednoducho skúsime obe a zoberieme tú z nich, ktorá nám pridá viac čísel do postupnosti.

Časová aj pamäťová zložitosť budú stále \(O(n)\).