3. Zajačí problém (vzorové riešenie) - Korešpondenčný seminár z programovania

Zadanie

V Krajine Slepačích Paprčiek (ďalej už len KSP) nastal čas zimy. Hlavnou náplňou práce v tejto krajine je chov sliepok a pestovanie špeciálnej mrkvy. Mrkva pestovaná v KSP sa od ostatných druhov odlišuje tým, že žiadne dve mrkvy nenarastú rovnako veľké. Keďže sliepky cez zimu nevynášajú toľko, aby celú krajinu uživili a mrkvu už nikto nechce¹, rozhodla sa vláda využiť svoju špeciálnu mrkvu iným spôsobom. Po dlhom rokovaní sa rozhodlo, že sa kúpia špeciálne zajace typu T2, ktoré sú známe predovšetkým vďaka svojmu vyberavému vkusu v oblasti mrkvy. Problém však nastal, keď sa rozhodli zajace nakŕmiť. Niektoré zajace svoje mrkvy nejedli a iba škaredo zazerali na zajace vedľa seba.

Našťastie bola k zajacom doručená aj príručka chovateľa, z ktorej obyvatelia zistili, že kŕmenie je u zajacov T2 veľmi háklivou kultúrnou záležitosťou. V závislosti na veku, pohlaví a postavení v zajačej hierarchii sú niektoré zajace ochotné jesť iba vtedy, keď má zajac pred nimi väčšiu mrkvu. Iné zajace zasa budú jesť, iba keď má zajac pred nimi menšiu mrkvu.

Po zistení tejto informácie už dokázali obyvatelia zajace nakŕmiť. Na druhý deň sa ale zajace zoradili na kŕmenie v inom poradí a obyvatelia zostali opäť zaskočení. Vláda sa teda rozhodla siahnuť po trvalom² riešení a využiť zostávajúce financie rozumne. Rozhodla sa teda najať si vás na vyriešenie tohto problému.

Úloha

Počet zajacov si označme \(n\). Mrkvy, ktorými chcú v daný deň Slepačopaprčkania nakŕmiť zajace, si očíslujme od najmenšej po najväčšiu číslami \(1, 2, \dots, n\).

Dostanete reťazec tvorený \(n - 1\) znakmi '<' (menší) a '>' (väčší), ktoré určujú vzťah medzi veľkosťami mrkvy susedných zajacov. Vašou úlohou je nájsť takú permutáciu čísel \(1\) až \(n\), v ktorej po sebe idúce členy spĺňajú zadané nerovnosti (permutácia čísel \(1\) až \(n\) je taká postupnosť čísel z rozsahu \(1\) až \(n\), ktorá každé z čísel od \(1\) po \(n\) obsahuje presne raz).

Formát vstupu

Na vstupe sa nachádza jeden riadok skladajúci sa z \(n-1\) znakov “\(<\)” a “\(>\)”. Platí \(2 \leq n \leq 10^6\).

Formát výstupu

Vypíšte jeden riadok a v ňom \(n\) medzerami oddelených čísiel: hľadanú permutáciu. Vždy existuje aspoň jedno riešenie. Ak existuje viac riešení, vypíšte ľubovoľné z nich.

Príklad

Input:

>>>>

Output:

5 4 3 2 1

Platí \(5>4, 4>3, 3>2, 2>1\)

Input:

><><

Output:

4 2 3 1 5

Platí \(4>2, 2<3, 3>1, 1<5\). Tento vstup má rôzne možnosti riešenia – správnym riešením je napríklad aj 2 1 4 3 5.

Všetci vegetariáni z Krajiny Mäsožravých Slonov sa totiž na zimu sťahujú do teplých krajov, kam sa mrkva kvôli diplomatickým problémom nevyváža.↩
samozrejme úspornom↩

Táto úloha sa dala riešiť rôznymi, viac, či menej zložitými spôsobmi (ak ste to chceli potiahnuť do extrému, mohli ste použiť trebárs topologické triedenie). Vzorové riešenie je však až zarážajúco jednoduché.

Vzorové riešenie

Máme čísla \(1, 2, \dots, n\) a potrebujeme ich zoradiť tak, aby spĺňali nerovnosti zo zadania. Pozrime sa na prvý znak vstupu. Môžu nastať dve možnosti:

Ak je prvý znak vstupu <, znamená to, že prvé číslo postupnosti musí byť menšie ako druhé.

V tomto prípade za prvé číslo môžeme vziať najmenšie z čísel, ktoré máme k dispozícii (teda číslo \(1\)). To nám zaručí, že nech akokoľvek usporiadame zvyšné čísla, táto nerovnosť bude určite platiť.
Ak je prvý znak >, prvé číslo musí byť väčšie ako druhé. V takom prípade môžeme za prvé číslo zobrať najväčšie možné číslo (teda \(n\)). Opäť budeme mať zaručené, že táto nerovnosť bude platiť bez ohľadu na to, ako usporiadame ostatné čísla.

V oboch prípadoch teda vieme určiť prvé číslo tak, aby nerovnosť určená prvým znakom vstupu zaručene platila. Ak sa nám potom podarí usporiadať zvyšné čísla tak, aby boli splnené zvyšné nerovnosti, máme vyhrané – všetky nerovnosti už budú platiť.

Ako zoradiť zvyšných \(n-1\) čísel tak, aby spĺňali zvyšné nerovnosti? Môžeme použiť tú istú myšlienku. Tento raz sa pozrieme na druhý znak vstupu. Ak je to <, potom môžeme za druhé číslo postupnosti zvoliť najmenšie z \(n-1\) čísel, ktoré nám zostali a aj táto nerovnosť bude zaručene splnená (bez ohľadu na to, ako zoradíme zvyšných \(n-2\) čísel). Ak bude druhý znak vstupu >, potom za druhé číslo postupnosti vezmeme najväčšie možné číslo.

Takto budeme pokračovať, až kým neprečítame celý vstup. Keď spracujeme všetkých \(n-1\) znakov vstupu, budeme mať určených prvých \(n-1\) čísel postupnosti. Za posledné číslo postupnosti vezmeme to jediné, čo nám zostane. Vzniknutá postupnosť bude určite spĺňať všetky nerovnosti na vstupe – prvú nerovnosť bude spĺňať vďaka tomu, ako sme zvolili prvé číslo postupnosti, druhú vďaka spôsobu voľby druhého čísla postupnosti, tretiu vďaka voľbe tretieho čísla atď.

Implementácia

Otázkou zostáva, ako tento algoritmus dobre implementovať. Asi najťažšou otázkou je, ako si pamätať zoznam doteraz nepoužitých čísel. Mohli by sme si ich pamätať v nejakom poli, ale ide to aj jednoduchšie. Stačí si uvedomiť, že zoznam nepoužitých čísel je v každom okamihu nášho algoritmu nejaká súvislá postupnosť prirodzených čísel: na začiatku je to \(1, 2, \dots, n\) a vždy keď z neho niečo vyhadzujeme, tak je to buď najväčšie, alebo najmenšie číslo (teda aj po vyhodení zostane súvislý). Preto si stačí v dvoch premenných pamätať najmenšie a najväčšie číslo v zozname.

Výslednú postupnosť by sme si mohli pamätať v poli. To ale tiež nie je nutné, keďže ju môžeme počas konštruovania rovno vypisovať.

#include <string>
#include <iostream>

using namespace std;

int main(){
    
    string vstup;
    cin >> vstup;
    
    int minimum = 1, maximum = (int)vstup.size() + 1;
    
    for (int i = 0; i < (int)vstup.size(); i++)
    {
        if(vstup[i]=='<')
            cout << minimum++ << " ";
            // vyraz `premenna++` najprv vrati hodnotu premennej 
            // (tato hodnota sa teda vypise) a potom ju o 1 zvysi  
        else
            cout << maximum-- << " ";
    }
    
    cout << minimum++ << "\n";

    
    return 0;
}

Zložitosť

Časová zložitosť algoritmu je \(O(n)\) – lineárna od počtu znakov na vstupe. Pamäťová zložitosť tohto algoritmu je tiež \(O(n)\), keďže je potrebné načítať vstup do poľa. Zvyšok operácií využíva už iba premenné \(minimum\) a \(maximum\). Všimnime si, že jediný dôvod, prečo potrebujeme čítať celý vstup už na začiatku je, že potrebujeme vedieť aký je dlhý (aby sme vedeli, aké najväčšie číslo má byť vo výslednej permutácii). Keby sme na začiatku na vstupe dostali číslo \(n\) a až potom postupnosť znakov < a >, úloha by sa dala riešiť v konštantnej pamäti – vstup by sme čítali po znakoch a vždy by sme si pamätali len znak, ktorý práve spracúvame.

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

3. Zajačí problém vzorové riešenie