Zadanie

Ján Ploštica sa spolu s rodinou nedávno presťahoval do mesta Gaučislava. Je to novozaložená kolónia ploštíc v T2, ktorá láka na pestrú a súdržnú susedskú komunitu, ale aj ľahkú dostupnosť služieb a občianskeho vybavenia, či prepracovanú a udržiavanú sieť tunelov. Celá navyše leží v príjemnom prostredí molitánu, ktorý plošticiam poskytuje zdravé a podnetné prostredie pre napĺňajúci každodenný život.

Pri návrhu komunikácií sa ploštičím inžinierom podarilo naplánovať mesto bez jedinej zbytočnej cesty – medzi každými dvoma miestami v Gaučislave sa dá dostať práve jedným spôsobom, pokiaľ sa ploštice po ceste nevracajú späť. Zároveň každá lokácia v meste má presne podľa plánu zaznačenú nadzemnú výšku, v ktorej sa nachádza, v jednotkách nožičkomilióntiny (nm). S rôznymi nadzemnými výškami sa totiž spájajú rozdielne podmienky, ktoré rozličným plošticiam vyhovujú rozdielnym spôsobom. Tým si ale lámať hlavu nemusíme, pretože to už predsa inžinieri vyriešili a navrhli.

Ján P. by sa rád pochválil svojim ploštičím kamarátom tým, aké veľké je mesto, kam sa presťahoval. Preto sa vydal na prechádzku tunelmi od svojho domu, a pri každej budove, ktorú minul, si poznačil jej nadzemnú výšku. Je si pritom istý, že sa mu podarilo navštíviť každé miesto v Gaučislave.

Dostal tak postupnosť výšok, ktorú ukázal kamarátom. Tí ale namietali, že ak navštívil nejaké miesto veľakrát, tak v zápise sa tiež vyskytlo veľakrát, a teda sa bude zdať, že Gaučislava je väčšia, než v skutočnosti. Preto potrebuje zistiť, aké najmenšie mesto môže byť, aby ich presvedčil, že určite musí byť masívne.

Úloha

Trochu formálnejšie, mesto Gaučislava tvorí strom – neorientovaný súvislý acyklický graf. To znamená, že medzi každými dvoma vrcholmi vedie práve jedna cesta (postupnosť vrcholov a hrán, v ktorej sa žiadny vrchol ani hrana neopakuje). Každý vrchol má svoju určenú výšku v nm, v rozsahu \(0\) až \(10^9\) (zhruba výška gauča aj s operadlom). Rôzne vrcholy môžu mať rovnakú výšku.

Dostanete číslo \(n\) a postupnosť výšok navštívených vrcholov \(v_1 ... v_n\). Vašou úlohou je vypísať najmenšie číslo \(m \leq n\) také, že existuje strom s \(m\) vrcholmi nejakých výšok, ktorého prechádzaním vieme dostať zadanú postupnosť výšok, pričom si zapisujeme každý vrchol, na ktorý vstúpime (a ten istý vrchol nevieme zapísať znova bez toho, aby sme z neho najskôr odišli a vrátili sa).

Formát vstupu

Na prvom riadku dostanete číslo \(n\) – počet zaznamenaných výšok. Na druhom riadku dostanete \(n\) čísel v rozsahu \(\langle 0, 10^9 \rangle\) – postupnosť výšok navštívených vrcholov.

Formát výstupu

Vypíšte jedno číslo \(m\) spĺňajúce zadanie – najmenší možný počet vrcholov stromu.

Obmedzenia

Sú \(4\) sady vstupov po \(2\) body. Platia v nich nasledovné obmedzenia:

Sada \(1\) \(2\) \(3\) \(4\)
\(1 \leq n \leq\) \(100\) \(3\,000\) \(100\,000\) \(1\,000\,000\)

Príklad

Input:

4
4 20 4 20

Output:

2

Naozaj masívne mesto, ktoré obsahuje dva domy s výškami 4 a 20. Videli ste hádam niekedy väčšie ploštičie mesto?

Input:

8
4 20 20 4 4 4 20 10

Output:

6

Prvých 5 výšok je síce podobných, no popisujú rôzne budovy. Šiesta výška popisuje štvrtú budovu, siedma tretiu, ôsma predtým nenavštívenú šiestu, ktorá susedí s tretiou.

Našou úlohou je nájsť najmenší možný strom (čiže súvislý acyklický graf), ktorý zodpovedá popisu. V takomto strome, pre každú zadanú výšku, existuje vrchol danej výšky, ktorý susedí s vrcholmi výšok zadaných tesne pred a po jeho výške.

Ako vyzerá najmenší strom

Môžeme si všimnúť, že nemá zmysel, aby jeden vrchol \(V\) mal dvoch susedov rovnakej výšky. Keby takí dvaja susedia existovali, nazvime ich \(S\) a \(T\), mohli by sme zobrať všetkých susedov vrcholu \(S\) (vrátane \(V\)) a napojiť ich do \(T\) namiesto do \(S\). Potom by sme mohli vrchol \(S\) úplne zmazať, pretože by nemal žiadnych susedov. Postupnosť výšok by bola stále validná, pretože medzi každými dvoma susedmi pôvodného vrcholu \(S\) by viedla rovnaká cesta cez \(T\) (čo sa týka poradia výšok), ako viedla cez \(S\). Zároveň by náš nový strom mal o jeden vrchol (\(S\)) menej, čo by bol spor s tvrdením, že pôvodný strom bol najmenší možný. Preto vieme, že žiadny vrchol nemá dvoch rovnako vysokých susedov.

To už nám v podstate hovorí, ako vytvoriť najmenší strom – budeme si vždy pamätať posledný navštívený vrchol a pre každú výšku sa pozrieme, či tento vrchol už má suseda danej výšky. Ak má, iba sa do tohoto suseda presunieme. Ak nemá, vytvoríme si nový vrchol danej výšky a presunieme sa do neho.

Ideálny strom nemôže byť menší, pretože sa nevieme presúvať medzi vrcholmi, ktoré nesusedia (a keďže ide o strom, vrcholy, ktoré nie sú zadané tesne po sebe v nejakej časti postupnosti výšok, spolu susediť nemôžu, inak by existoval cyklus).

Ako to implementovať

Vrcholy si budeme pamätať v poradí, v akom sme ich prvý krát videli. Na to vieme použiť obyčajné pole, kam vždy pri vytvorení nového vrcholu pridáme jeho výšku. Vrcholy budeme inde reprezentovať indexami tohoto poľa.

Zároveň si pre každý vrchol chceme pamätať výšky všetkých jeho susedov, a to tak, aby sme sa vedeli čo najrýchlejšie spýtať, či má aktuálny vrchol suseda danej výšky. A ak áno, ktorý to je. Pomalá implementácia by mohla vyzerať takto:

Pre každý vrchol máme pole, v ktorom si ukladáme všetkých jeho susedov. Keď chceme zistiť, či má vrchol suseda s danou výškou, prejdeme všetkých jeho susedov a skúsime nájsť jedného so správnou výškou. Takáto implementácia je kvadratická, čo sa najlepšie predstavuje na grafe tvaru hviezdy – každý druhý raz navštívime stredový vrchol a potom prejdeme až lineárne mnoho vrcholov, aby sme zistili, či treba pridať nový.

Aby sme zlepšili časovú zložitosť, môžeme namiesto poľa susedov použiť rýchlejšiu dátovú štruktúru - napríklad slovník alebo vyhľadávací strom. Pri použití slovníku a hashovania sa nám lineárny čas na otázku zlepší na konštantný a taký bude aj čas pridávania vrcholu. Pri použití vyhľadávacieho stromu budú oba časy logaritmické.

Časová a pamäťová zložitosť

Prechádzame celý vstup a pre každú výšku robíme konštantne mnoho operácií, preto je celková časová zložitosť \(O(n)\) (respektíve \(O(n log n)\) pri použití vyhľadávacieho stromu namiesto slovníka). Pamäťová zložitosť je rovná počtu vrcholov plus počtu hrán, ale keďže graf je strom, je oboch lineárne mnoho.

Pri praktickej implementácií môžeme tiež použiť jeden slovník pre všetky vrcholy tak, ako v autorskom riešení.

def solve():
    vysky = [] # Zoznam vsetkych vrcholov podla poradia prveho navstivenia
    susedia = dict() # Index suseda (3) vrcholu cislo (1) s vyskou (2),
                     # indexujeme susedia[(1, 2)] = 3
    prvy_vrchol = True 
    n = int(input())

    for vyska in map(int, input().split()):
        # Prejdeme postupne cely zoznam vysok:
        if prvy_vrchol:
            # Ak je to uplne prvy vrchol, len ho pridame
            prvy_vrchol = False
            vysky.append(vyska)
            index = 0 # Index oznacuje aktualny vrchol v zozname vysok
            continue

        if (index, vyska) in susedia.keys():
            # Ak ma uz aktualny vrchol suseda hladanej vysky, len sa presunieme
            index = susedia[(index, vyska)]
        else:
            vysky.append(vyska) # Pridame novy vrchol
            susedia[(len(vysky) - 1, vysky[index])] = index
            # Pridame prepojenie z noveho vrcholu na aktualny
            susedia[(index, vyska)] = len(vysky) - 1
            # Pridame prepojenie z aktualneho vrcholu na novy
            index = len(vysky) - 1 # Presunieme sa do noveho vrcholu

    return len(vysky)
    # Nakoniec vratime pocet rozdielnych navstivenych vrcholov

print(solve())

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