Zadanie

Dušan je vášnivý turista. Pri svojej poslednej návšteve Vysokých Tatier sa rozhodol písať si denník. Po každom kilometri si zapíše, či išiel hore alebo dole kopcom jeden výškový meter. Dušanovi však zmokol batoh a niektoré zápisky niesú čitateľné. Po príchode domov chcel svojím kamarátom ukázať, kde jedol fajnový obed. Pamätal si, že obed jedol na najvyššom kopci. Avšak kvôli nekompletným záznamom si nie je istý, kde to naozaj bolo. Pomôž mu zistiť koľko takýchto miest mohlo cestou byť.

Úloha

Pre jednoduchosť môže predpokladať stúpanie + a klesanie - za konštantné, posunieme sa hore alebo dole vždy o tú istú hodnotu. ?, znamená, že z poznámok nie je jasné kam sa Dušan posunul ale určite vieme povedať, že išiel buď dole alebo hore – nikdy neostal na tej istej výške. Chceme zistiť koľko kopcov mohlo byť tými najvyššími, a ktoré to mohli byť.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) udávajúce počet zápiskov.

Na druhom riadku sa nachádza \(n\) zápiskov (+, -, ?), označujúcich Dušanov pohyb hore a dole. ? znamená, že nevieme určiť, či Dušan išiel hore alebo dole.

V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1 2 3 4 5 6 7 8
\(1 \leq n \leq\) \(1\,000\,000\) \(10\) \(100\) \(1\,000\) \(5\,000\) \(100\,000\) \(500\,000\) \(1\,000\,000\)
\(0 \leq \#? \leq\) \(0\) \(5\) \(50\) \(500\) \(1\,000\) \(10\,000\) \(100\,000\) \(300\,000\)

Formát výstupu

Vypíš dva riadky. V prvom jedno celé číslo, ktoré hovorí, na koľkých pozíciach sa mohol nachádzať najvyšší kopec Dušanovej cesty. Na druhý riadok napíš pozície, na ktorých sa tieto kopce mohli nachádzať. Na poradí vypísaných pozícií nezáleží.

Príklady

Input:

2
?-

Output:

2
0 1

Vrchol môže byť na 0., kde stál pred tým ako sa pohol. Alebo na 1. pozícii. Ak by sa Dušan najprv posunul dole kopcom (? -> -) tak ak začíname vo výške 0, by mohol stáť vo výškach 0, -1, -2. Ak by sa Dušan najprv posunul hore kopcom (? -> +) tak ak začíname vo výške 0, by mohol stáť vo výškach 0, 1, 0 .

Input:

6
+??-+-

Output:

4
1 2 3 5

Rozoberme si postupne všetky možnosti:

  • +++-+- -> 0, 1, 2, 3, 2, 3, 2
  • +---+- -> 0, 1, 0,-1,-2,-1,-2
  • +-+-+- -> 0, 1, 0, 1, 0, 1, 0
  • ++--+- -> 0, 1, 2, 1, 0, 1, 0

Najvyššie miesto cesty môže byť na 1., 2., 3. alebo 5. pozícii. V prvom prípade by najvyšší kopec bol ten na tretej pozícii a piatej pozícii. V druhom prípade by to bol iba ten na prvej pozícii. v treťom prípade by to bol ten na prvej, tretej a piatej pozícii a v poslednom prípade by to bol kopec na druhej pozícii.

Naším zadaním bolo nájsť miesta, na ktorých mohol byť najvyšší kopec.

Bruteforce

Predstavme si jednoduchší prípad, že tam otázniky nie sú. V tomto prípade stačí prejsť celú trasu a vypočítať si výšky kopcov. Taktiež si vyrátame maximálnu výšku počas celej trasy. Nakoniec vypíšeme miesta, na ktorých sa nachádzali najvyššie kopce, teda pozície s maximálnou hodnotou a koľko ich bolo.

Pridajme do úlohy otázniky. Za každý ? vieme doplniť + alebo -. Skúsme úlohu vyriešiť hrubou silou. V takomto riešení chceme vygenerovať všetky možnosti. Tých je \(2^q\), kde \(q\) je počet otáznikov.

Pre každú z možností použijeme predchádzajúce riešenie. Tu nastáva problém, lebo môžeme nejakú pozíciu zarátať aj viackrát, v dvoch rôznych možnostiach bol najvyšší kopec na rovnakom mieste. Preto si chceme pamätať informáciu, či už daný kopec maximom bol.

Pozrime sa na časovú zložitosť tohto riešenia. Vygenerujeme si všetkých \(2^q\) možností. Pre každú v lineárnom čase spočítame polohy všetkých maxím. Na záver prejdeme všetky polohy, čo už časovú zložitosť neovplyvní. Vo výsledku budeme mať exponenciálnu časovú zložitosť \(O(n \cdot 2 ^ q)\).

Pamäťová zložitosť je \(O(n)\), lebo si musíme pamätať vstup, ktorý následne budeme upravovať, a finálne pozície najvyšších kopcov. Ale počas jedného prechodu si už nič väčšie pamätať nemusíme, iba priebežné maximum.

Niečo lepšie

Skúsme sa na to pozrieť z inej strany. Na to aby bol kopec na \(i\)-tom mieste najvyšší, musí platiť, že pred príchodom na tento kopec sme sa snažili čo najviac stúpať, a po ňom čo najviac klesať. Preto chceme za všetky otázniky pred daným kopcom pridávať + a za všetky otázniky po ňom pridávať -.

Prejdime teda všetky pozície a pre každú overme, či by na danom mieste mohlo byť maximum.

Pre každý kopec musíme prejsť celé pole dĺžky \(n\), takže časová zložitosť je \(O(n^2)\).

Pamäťová zložitosť zostáva \(O(n)\), pretože si musíme pamätať počiatočné informácie, ktoré budeme postupne prepočítavať.

Optimálne riešenie

Skúsme sa zamyslieť nad tým, aké výpočty robíme opakovane v predchádzajúcom riešení. Pre každú pozíciu zisťujeme, či sa na nej nevie nachádzať najvyšší kopec. Teraz môžeme porozmýšľať, či pri rátaní \((i+1)\)-vej pozície nevieme znova využiť niečo z tej predošlej pozície. V predchádzajúcom riešení sme to robili tak, všetko “naokolo” sme sa snažili znížiť.

Pri posune o 1 je teda výsledok takmer rovnaký. Všetky ? pred \(i\)-tou pozíciou sme nahradili za + a všetky za \((i+1)\)-vou pozíciou sme nahradili za -. Teda ak by sme si zapamätali predchádzajúce hodnoty stačí ich upraviť iba podľa znaku medzi \(i\)-tou a \((i+1)\)-vou pozíciou.

Toto si vieme pomerne jednoducho predrátať. V jednom poli si zapamätáme výšky na pozíciách ak nahradíme ? za + a v druhom ak ich nahradíme -.

Doteraz sme pre každú pozíciu zisťovali, či môže byť maximom celého poľa nasledovne: vždy sme prešli celé pole a zistili, aké výšky môžu jednotlivé pozície nadobudnúť a priebežne si pamätali tú najvyššiu. Tento postup je však zbytočne zdĺhavý a pre rôzne pozície vykonáva rovnaké výpočty. Môžeme ho výrazne zjednodušiť, ak si problém rozdelíme na dve časti: pre každú pozíciu si zapamätáme najväčšiu výšku, ktorú vieme dosiahnuť pred ňou, a najväčšiu výšku, ktorú vieme dosiahnuť za ňou. Na výpočet prvej použijeme predrátané hodnoty, v ktorých sme za ? dopĺňali + a na výpočet druhej tie hodnoty kde sme dopĺňali -.

Ak je výška na danej pozícii väčšia ako všetky výšky pred ňou a zároveň väčšia alebo rovná všetkým výškam za ňou, potom môže byť práve táto pozícia najvyšším kopcom.

Aby sme tieto hodnoty vedeli efektívne zistiť, predpočítame si ďalšie dve pomocné polia maxím. Prvé bude prefixové maximum, kde všetky otázniky ? nahradíme za stúpanie + a budeme postupne sledovať maximálnu výšku dosiahnutú zľava doprava. Druhé bude sufixové maximum, kde všetky otázniky ? nahradíme za klesanie - a budeme sledovať maximálnu výšku zprava doľava.

Pomocou týchto dvoch predpočítaných polí vieme pre každú pozíciu v konštantnom čase rozhodnúť, či môže byť najvyšším kopcom.

Časová zložitošť bude lineárna \(O(n)\), potrebujeme si zrátať štyri polia a nakoniec tieto polia piatykrát vyhodnotiť. Polia výšok kopcov (1 - vždy ideme dole, 2 - vždy ideme hore), prefixové maximum a suffixové maximum. Nakoniec overíme, ktoré kopce môžu byť tými najvyššími.

Pamäťová zložitosť bude \(O(n)\), lebo v pamäti máme uložené 4 polia veľkosti \(n\), rovnako veľký vstup a zopár premenných.

Jeden z prípadov, ktoré musíme pri implementácii ošetriť je ak na prvej pozícii (nultej v poli) v suffixovom maxime hodnota menšia alebo rovná 0, znamená to, že prvý kopec môže byť najvyšší. Prečo? Lebo ak všetko za ním iba klesá, tak náš prvý kopec musí byť buď najvyšší, alebo jeden z najvyšších.

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