6. Dijkstra inak vzorové riešenie

3
1 2 3

1

5
5 4 3 2 1

5

6
4 5 2 3 1 6

3

Našou úlohou je rozdeliť \(N\) čísel do čo najmenej rastúcich podpostupností tak, aby bolo každé číslo v práve jednej z nich. Vstup si teda predstavme ako pole \(V\) dĺžky \(N\), pričom hodnota \(V[i]\) znamená, že vodič spája \(i\)-ty koniec v ľavom stĺpci s \(V[i]\)-tým koncom v pravom stĺpci.

Riešenie

Úlohu riešme postupne, tak ako ju dostávame na vstupe - ak sa aktuálne snažíme zaradiť číslo \(V[i]\), majme už všetky čísla s indexom menším ako \(i\) roztriedené. Vďaka tomuto si stav riešenia vieme reprezentovať ako niekoľko rastúcich postupností, pričom nové číslo pridávame vždy iba na koniec daných postupností. Keďže číslo pridávame vždy iba na koniec a jediná podmienka ktorú musíme spĺňať je aby boli postupnosti rastúce, stačí si nám pamätať iba posledné číslo z každej postupnosti. Navyše sa s údajmi omnoho ľahšie pracuje ak sú utriedené, preto si tieto konce postupností budeme pamätať v utriedenom poli \(P\).

Intuitívne dáva zmysel, že ak pridávame číslo \(X\), oplatí sa ho umiestniť do postupnosti, ktorej koniec má oproti \(X\) čo najmenší rozdiel (a zároveň sa do nej \(X\) dá umiestniť). Ak máme konce postupnosti utriedené zostupne, znamená to, že \(X\) chceme pridať do postupnosti s čo najmenším indexom pre ktorý je \(P[i]<X\). Kedze toto cislo pridame na koniec tejto postupnosti, \(P[i]\) sa bude po pridani rovnat \(X\). Dolezite pozorovanie je, ze takato uprava pola nam nenarusi jeho utriedenost. Totiz kedze sme cislo umiestnili na \(i\)-ty index pola \(P\), znamena to ze \(P[i+1]<P[i]<X<P[i-1]\) (ak \(i>0\), inak je jednoducho \(X\) začiatkom pola). Posledným detailom je, čo spraviť ak je \(X\) menšie ako ktorékoľvek číslo v \(P\). Vtedy jednoducho pridáme \(X\) na koniec pola \(P\), a zaradíme ho teda do novej postupnosti.

Dôkaz

Je tento postup optimálny? Konkrétna implementácia bude ovplyvňovať časovú zložitosť, poďme sa však teraz pozrieť skôr na optimalitu výsledku a jej dôkaz. Povedzme že budeme dodržiavať tento postup a skončíme s riešením ktoré potrebuje \(R\) vrstiev. Pozrime sa na posledné číslo v tejto poslednej vrstve. Keďže sme ho tam umiestnili, znamená to, že v momente keď sme ho tam umiestňovali mali všetky predchádzajúce vrstvy na konci väčšie číslo. Takúto úvahu vieme uplatniť aj na predposlednú vrstvu a postupne na všetky vrstvy, čím zistíme, že na vstupe sa musela nachádzať klesajúca podpostupnosť dĺžky \(R\). Vieme si však uvedomiť, že klesajúcu postupnosť nevieme rozdeliť lepšie ako na rovnako veľa jednoprvkových rastúcich postupností. Teda vieme, že pre daný vstup určite neexistuje lepšie riešenie a teda toto riešenie je optimálne.

Riešenie druhej sady

Teraz keď už vieme čo chceme robiť stačí to iba spraviť! Vlastne jediný problém ktorý máme, je hľadanie najmenšieho indexu s hodnotou menšou ako \(X\). Na to aby sme vyriešili druhú sadu, teda \(N<2000\), nám stačí vyhľadávanie s časovou zložitosťou \(O(N)\). Teda jednoducho prejdeme polom zľava doprava, pri prvom valídnom čísle sa zastavíme a pole upravíme. Nakoniec vypíšeme veľkosť pola.

Vzorové riešenie

Vzorové riešenie si vyžaduje vyhľadávanie s časovou zložitosťou \(O(log N)\) a keďže si pole udržiavame utriedené, môžeme na ňom binárne vyhľadávať. Jediný rozdiel oproti predchádzajúcemu riešeniu je teda jeden riadok, keďže väčšina jazykov má binárne vyhľadávanie ako súčasť štandardnej knižnice.

Vzorových riešení je však viacero. Jedným z nich je použitie intervalového stromu.

Totiž postupnosti si nemusíme reprezentovať ako hodnoty koncov v postupnosti, Vieme sa na to pozrieť z inverzného uhla. Budeme mať pole \(S\) o \(N\) prvkoch, pričom ak sa v predchádzajúcom riešení končila \(i\)-ta postupnosť číslom \(P[i]\), tentoraz bude v poli \(S\) na pozícii \(P[i]\) hodnota \(i\) (teda \(S[P[i]]=i\)). Index najskoršej postupnosti, ktorej koniec je menší ako \(X\) nájdeme tak, že v prefixe dĺžky \(X\) poľa \(S\) nájdeme najmenšiu hodnotu. Keď ju nájdeme, vymažeme ju a uložíme na index \(X\) pola \(S\). Keďže potrebujeme tieto operácie vykonávať v \(O(log N)\), použijeme minimový intervalový strom.