Zadanie

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 loops_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 Danovi na danoravec@gmail.com

Globálne otepľovanie sa prejavuje stále viac a viac. Ľadovce sa topia. Hladiny oceánov sa dvíhajú. Živočíchy vymierajú. V ťažkej situácií je ale potrebné neprepadnúť panike a šíriť medzi ľuďmi radosť v podobe hudby. Na to však potrebujeme najdokonalejší hudobný nástroj. Tým je jednoznačne Panova flauta. Rozhodli ste sa, že nám ju vyrobíte z bambusu. My vás dovedieme ku bambusovému záhonu. V ňom sú bambusy rôznych výšok rastúce tesne vedľa seba v jednom dlhom rade. Sú medzi nimi také malé rozostupy, že nie je možné odseknúť bambus, ktorý je medzi dvoma inými bambusmi. V každom momente teda viete odseknúť iba bambus, ktorý je úplne vľavo, alebo úplne vpravo. Okamžite po odseknutí celý odseknutý bambus prilepíme na pravú stranu flauty.

Určite nechcete plytvať materiálom, preto bambus odseknete vždy celý a neostane z neho nad zem trčať ani kúsok. Zároveň však potrebujete bambusy sekať v takom poradí, aby bol každý ďalší odseknutý bambus dlhší, ako ten predchádzajúci. To je preto, že sa ponáhľame a nemáme dosť času na usporiadavanie toľkých paličiek ešte pred samotnou výrobou flauty. Bambusy musia byť vo flaute usporiadané podľa dĺžky, aby boli podobné tóny vedľa seba. No a nechceme predsa nejaký bambus odseknúť a zahodiť ho len preto, aby sme sa tým dostali k nejakému dlhšiemu. To je predsa zbytočný výrub lesov a proti tomu bojujeme.

Pozrime sa na príklad. Bambusy v záhone majú postupne zľava doprava výšky 1, 2, 5, 3, 2. Nám sa oplatí zobrať najskôr bambus naľavo s výškou 1. Máme teda flautu z jedného bambusu výšky 1. Ostane nám záhon s výškami 2, 5, 3, 2. Teraz zoberieme bambus úplne napravo s výškou 2. Flauta už je 1, 2 a záhon je ešte 2, 5, 3. Teraz zoberieme dvakrát bambus sprava a získame tak flautu 1, 2, 3, 5 a ostane nám záhon s jediným bambusom výšky 2. Postavili sme teda flautu šírky 4.

Čím viac tónov vieme zahrať, tým viac zachránime svet, to vie predsa každý. Chcete teda, aby flauta pozostávala z čo najviac bambusov. Akú najširšiu flautu nám viete postaviť?

Úloha

My vám popíšeme výšky bambusov tak, ako vedľa seba rastú v záhone. Vy chcete vyrobiť z bambusov flautu. To znamená, že sa v každom momente rozhodnete, či odseknete bambus vľavo, alebo bambus vpravo. Ten odseknete a pridáte ho ku flaute sprava. Odseknuté bambusy musia tvoriť rastúcu postupnosť.

Variant A

Zistite iba dĺžku najdlhšej rastúcej postupnosti, ktorú vieme vytvoriť vyššie popísaným spôsobom. Ináč povedané, vypíšte, koľko najviac bambusov vieme odseknúť tak, aby nám z toho vznikla flauta.

Variant B

Na získanie plného počtu bodov stačí vyriešiť Variant B

Nemusíte nám hovoriť dĺžku postupnosti. Vypíšte namiesto toho nejaký postup seknutí, ktorý nás dovedie k nejakej najdlhšej možnej flaute.

Formát vstupu

Na prvom riadku je číslo \(n\) - počet bambusov v záhone.

Na druhom riadku je \(n\) čísiel \(b_1\)\(b_n\), výšky bambusov zľava doprava. Bude platiť, že \(1 \leq b_i \leq 2n\).

Formát výstupu

Variant A

Na jediný riadok výstupu vypíšte číslo \(k\) - najväčší možný počet bambusov vo flaute.

Variant B

Na jedinom riadku výstupu vypíšte reťazec dĺžky \(k\), kde \(k\) je najväčší možný počet bambusov vo flaute, ktorý sa dá dosiahnúť. Tento reťazec bude predstavovať postupnosť seknutí. Za každé odseknutie ľavého bambusu dajte znak L, za každé odseknutie bambusu sprava dajte znak R. Reťazec LRR teda bude znamenať, že sme najskôr odsekli ľavý potom pravý a potom znova pravý bambus.

Hodnotenie

Je 15 testovacích sád. Za každú viete získať 1 bod. Približne platí, že čím vyššie je číslo sady, tým väčšie je \(n\).

Ak riešite Variant A, vaše riešenia sa otestujú na všetkých sadách okrem 3, 6, 12, 15. Za toto riešenie teda viete získať až 11 bodov. Plný počet bodov dostanete, ak vyriešite Variant B. Takéto riešenie sa otestuje na všetkých sadách.

Interne testovanie vašich riešení funguje jednoduchým pravidlom. Ak je výstupom vášho programu číslo, testovač sa k nemu správa ako k riešeniu Variantu A. V opačnom prípade ho označí za riešenie Variantu B.

Číslo sady 1, 2, 4, 5 3,6 7 8 9 10 až 15
maximálne \(n\) \(10\) \(20\) \(100\) \(10\,000\) \(50\,000\) \(200\,000\)

Navyše, sadách 1, 2, 3, 8, 9, 10, 11 a 12 sú všetky výšky bambusov rôzne. V ostatných sadách môžu byť niektoré výšky rovnaké.

Príklady

Variant B

Input:

5
1 2 5 3 2

Output:

LRRR

Vznikne flauta, kde dĺžky bambusov budú zľava doprava postupne 1, 2, 3, 5. Určite nemôžeme použiť všetky bambusy zo vstupu, pretože sú tam dva rovnakej dĺžky, takže by vzniknutá postupnosť určite nebola ostro rastúca.

Variant A

Input:

4
1 2 4 3

Output:

4

Môžeme použiť všetky bambusy zo vstupu

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

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ť.