Zadanie
Predseda Kúl Spolku Pandemiológov sa v rámci aktuálnej krízy rozhodol zvolať zasadnutie odborníkov zo všetkých krajov. Takéto zasadnutie je veľmi prestížne a prirodzene tak má určité absurdné pravidlá. Jedno z nich je napríklad to, že sa zasadá vždy výlučne za okrúhlim stolom a každý kraj má pri danom stole svoje pevne stanovené miesto. Preto každý, kto si sadne na miesto daného kraju, musí rozprávať iba o tom konkrétnom kraji. Každý odborník, ktorý sedí na mieste svojho kraju je tak výrazne efektívnejší ako keď sedí na mieste iného kraju o ktorom nič nevie.
Odborníci sú tvrdohlavé stvorenia a za stôl si sadajú v poradí, v ktorom prišli do miestnosti a odmietajú si presadnúť. Predseda avšak potrebuje presné informácie z čo najviac krajov a tie mu vie dať iba odborník z daného kraja. Jedinou možnosťou ako tento stav dosiahnuť, je otočiť stôl o niekoľko miest do ktorejkoľvek strany tak, aby čo najviac odborníkov sedelo na svojom mieste. A keďže stôl je veľmi ťažký, ideálne ho chce otočiť o čo najmenej miest.
Úloha
Tvojou úlohou je pomôcť predsedovi určiť o koľko najmenej miest treba otočiť okrúhly stôl tak, aby čo najviac odborníkov sedelo na svojom mieste. Predsedu taktiež zaujíma koľko odborníkov tak bude sedieť na svojom mieste. Odborníci si sadajú za stôl v poradí v akom prišli, odborník \(n_i\) si tak vždy sadne na pozíciu \(i\). Odborník sedí na svojom mieste vtedy, ak je z kraja \(i\) a zároveň sedi na mieste \(i\) pri stole. Stôl je možné otočiť do oboch strán.
Formát vstupu
Na prvom riadku vstupu dostanete číslo \(n\), (\(1 \leq n \leq 10^6\)), ktoré označuje počet krajov z ktorých prichádzajú jednotlivý odborníci. Na druhom riadku sa nachádza \(n\) čísiel \(n_i\), (\(1 \leq n_i \leq n\)) označujúcich kraj z ktorého pochádza \(i\)-ty oborník. Každé čislo od \(1\) po \(n\) sa na vstupe nachádza práve raz.
Formát výstupu
Na výstup vypíš dve čísla, \(k\) - posun stola, \(t\) - počet odborníkov na svojom mieste, tak aby čo najviac odborníkov sedelo na svojom mieste.
Príklady
Input:
5
3 4 5 2 1
Output:
2 3
Ak otočíme stôl o dve miesta, odborníci 3, 4 a 5 budú sedieť na svojom mieste.
Input:
4
4 1 2 3
Output:
1 4
Prvý prišiel odborník zo štvrtého kraja, následne už prišli odborníci po poradí. Stôl nám tak stačí otočiť o jedno miesto aby všetci odborníci sedeli na mieste so správnym číslom.
Input:
4
2 3 4 1
Output:
1 4
Podobne ako pri predchádzajpcom príklade nám stačí otočiť stôl iba o jedno miesto, tento krát avšak do druhej strany.
Riešenie hrubou silou
Prvé riešenie, ktoré si ukážeme, využíva jednoduchý prístup, kedy si pre každý možný posun stola spočítame, koľko ľudí bude sedieť na správnom mieste. Toto vieme spraviť jednoducho, stačí ak ku každému odborníkovi \(n_i\) pripočítame otočenie stola \(j\). Ak sa následne \(n_i + j\) rovná \(i\), vieme, že odborník sedí na správnom mieste. Úlohou je taktiež otočiť stôl o čo najmenej pozícií. Preto v prípade, že máme \(k\) otočení s rovnakým a zároveň najväčším počtom správne usadených odborníkov, musíme vybrať najmenšie otočenie do ľubovolnej strany. To vieme spraviť jednoducho. Vieme, že ak sme stôl otočili o viac ako polovicu miest, otočenie do druhej strany je efektívne. Stôl nám tak stačí otáčať iba do jednej zo strán. Stôl tak otočíme o najviac \(\lfloor \frac{n}{2} \rfloor\) miest.
Časová zložitosť tohto riešenia je kvadratická. Pre každú pozíciu pri stole sme museli prejsť všetkých sediacich pri stole. Keďže pozícií je \(n\), rovnako ako sediacich, časová zložitosť je \(O(n^2)\). Pamäťová zložitosť tohto riešenia je \(O(n)\) keďže sme si potrebovali pamätať všetky pozície zo vstupu.
Vzorové riešenie
Pri riešení hrubou silou sme si postupne pre každú pozíciu pri stole vypočítali, koľko ludí sedí na správnom mieste. Tento krok vieme zjednodušiť. Každý odborník pri stole buď sedí na svojom mieste, alebo vieme otočiť stôl práve dvoma spôsobmi tak, aby sedel na svojom mieste. Ako sme si avšak ukázali pri riešení hrubou silou, stôl nám stačí v skutočnosti otáčať iba do jednej strany. Nepotrebujeme preto pre každého odborníka uvažovať každú možnú pozíciu otočenia stola. Pre každého odborníka nám stačí vypočítať, o koľko treba otočíť stôl, ak má daný odborník sedieť na správnom mieste. Vytvoríme si tak pole veľkosti \(n\), kedy pre každé otočenie stolu dostaneme počeť odborníkov sediacich na správnom mieste. Následne nám stačí iba nájsť také otočenie, ktoré má najväčší počet odborníkov na správnom mieste a zároveň otáčame stôl o čo najmenej miest do ktorejkoľvek strany.
Časová zložitosť tohto riešenia je lineárna vzhľadom na počet odborníkov \(n\). Pre každého odborníka sme v konštantnom čase vypočítali otočenie stola tak, aby sedel na správnom mieste. Následne sme prešli všetky možné otočenia. Keďže odborníkov aj možných otočení je \(n\), časová zložitosť je tak \(O(n)\). Pamäťová zložitosť je taktiež lineárna vzhľadom na počet obdorníkov \(n\). Počiatočné pozície odborníkov si pamätať nemusíme, stačí nám pamätať si pole s počtom odborníkov pre jednotlivé otočenie stolu. Keďže možných otočení je \(n\), pamäťová zložitosť je \(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ť.