Zoznam úloh

4. Upravovanie nevyšlo

Zadanie

V poslednej dobe sa medzi vedúcimi KSP (a možno aj riešiteľmi, ktovie?) šíri istý nepekný nešvár. Často sa zrazu, len tak, z ničoho nič rozhodnú, že si idú nejako meniť hardvér svojho počítača.

Aj Maťo padol za obeť tomuto nešťastnému trendu, a skončilo to odpadnutým rámom displeja na jeho notebooku. Teraz musí zháňať nový. Našiel však na internete strašne veľa predajných ponúk a v kartách prehliadača má trošku bordel, a navyše ich je toľko, že nevidí, čo v nich je1. Preto ich vie usporiadavať iba tak, že práve otvorenú kartu posunie buď na začiatok alebo na koniec.

Úloha

Na vstupe dostanete pole $n$ čísel od $1$ po $n$ v náhodnom poradí, ktoré predstavujú ceny nových rámov. Môžete ich usporiadať iba presúvaním prvkov na začiatok alebo na koniec. Vašou úlohou je usporiadať ich s čo najmenším počtom krokov.

Formát vstupu

V prvom riadku vstupu je číslo $n$ ($0 \leq n \leq 10^6$) udávajúce počet čísel v poli.

V druhom riadku vstupu je $n$ rôznych čísel oddelených medzerou ($1 \leq a_i \leq n$). Konkrétne sú to čísla od $1$ do $n$, v náhodnom poradí.

Sada 1 2 3 4
$n \leq$ $10$ $20$ $10^4$ $10^6$

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo udávajúce najmenší možný počet krokov potrebných na usporiadanie poľa.

Príklady

Vstup

7
2 6 1 5 3 4 7

Výstup

4

1. krok: presunieme jednotku na začiatok (1 2 6 5 3 4 7)

2. krok: presunieme päťku na koniec (1 2 6 3 4 7 5)

3. krok: presunieme šestku na koniec (1 2 3 4 7 5 6)

4. krok: presunieme sedmičku na koniec (1 2 3 4 5 6 7)

Vstup

5
1 2 3 4 5

Výstup

0

Pole už je usporiadané, takže potrebujeme 0 krokov.


  1. Ľudia, ktorí nevedia, čo toto znamená buď nikdy nepoužívali počítač, alebo sú extrémne poriadkumilovní. Nie som ochotný pripustiť inú možnosť. ↩

Cieľom úlohy bolo zistiť, koľko najmenej krokov potrebujeme na to, aby sme pole náhodne rozhádzaných čísel od $1$ po $n$ utriedili, s tým, že jediná operácia, ktorú môžeme urobiť, je, že zoberieme ktorékoľvek číslo z poľa a dáme ho buď na začiatok, alebo na koniec.

Bruteforce

Ako bruteforce riešenie by sme v tomto prípade postupovali nasledovne:

Každý možný stav poľa, teda každú permutáciu čísel od $1$ po $n$, si predstavíme ako vrchol grafu. Ďalej každú podľa zadania platnú operáciu, ktorá zmení stav poľa, si predstavíme ako hranu tohto grafu.

Takýto graf vieme z počiatočného stavu začať prehľadávať do šírky (BFS) a pre každý vrchol si pamätať, koľko operácií sme potrebovali na to, aby sme sa naň dostali. V momente, keď sa dostaneme do vrcholu, ktorý reprezentuje utriedené pole, vieme, aký počet operácií sme potrebovali.

Existuje $n!$ permutácií, teda $n!$ vrcholov grafu, a z každej permutácie je $2n$ platných operácií, teda z každého vrcholu vedie $2n$ hrán. Všetkých hrán je teda dokopy $2n \cdot n!$. Časová zložitosť tohto riešenia je teda $O(2n \cdot n! + n!)$, respektíve $O(n \cdot n!)$.

Pamätať si treba všetky vrcholy (ktorých je $n!$) a všetky hrany (ktorých je $2n \cdot n!$). Pamäťová zložitosť je teda $O(2n \cdot n! + n!)$, respektíve $O(n \cdot n!)$.

Zaujímavé je uvedomiť si, že teoreticky tento graf vôbec nemusíme konštruovať (čím ušetríme značné množstvo pamäte), pretože na základe platných operácií vieme susednú permutáciu vždy vypočítať. Problém je však v tom, že susedných permutácií je vždy lineárne veľa, a vytvoriť každú z nich trvá lineárne dlho, teda sa nám rozpísaná forma časovej zložitosti zhorší z $O(2n \cdot n! + n!)$ na $O(2n^2 \cdot n! + n!)$.

Zaujímavá myšlienka

Dôležité v tejto úlohe bolo uvedomiť si, že sa dá zmeniť na inú, jednoduchšiu úlohu. Konkrétne ide o hľadanie najdlhšej postupnosti čísel stúpajúcich o 1, ktoré sú navzájom v správnom poradí, ale nie nutne hneď po sebe (v pôvodnom poli sa medzi nimi môžu vyskytovať aj iné čísla, ktoré nie sú súčasťou postupnosti).

Potom totiž už môžeme tieto čísla považovať za utriedené, a teda už treba len vyriešiť, ako utriedime tie ostatné okolo nich, pričom zjavne musí existovať nejaké optimálne poradie operácií, pri ktorom stačí každé z týchto ostatných čísel presunúť raz.

Navyše pre tie ostatné čísla platí, že na základe ich samých a ich polohy vzhľadom na nájdenú postupnosť je jednoznačne určené v akom poradí a na ktorú stranu poľa ich treba presunúť.

My však nepotrebujeme vedieť, aké operácie treba vykonať, ale iba koľko ich treba vykonať. Keďže je tento počet rovný počtu čísel mimo postupnosti, dá sa s konštantnou časovou zložitosťou vypočítať, ak máme nájdenú postupnosť s vyššie opísanými vlastnosťami (a teda aj jej dĺžku).

Naivná implementácia

Najjednoduchší spôsob, ako nájsť takúto postupnosť, je vyskúšať všetky možné súvislé aj nesúvislé postupnosti. To sa dá reinterpretovať ako skúšanie každej možnej podmnožiny.

Nájsť všetky podmnožiny sa dá pomocou jednoduchej rekurzie. Potom iba pri každej skontrolujeme, či čísla v nej rastú postupne (rozdiel medzi susednými by mal byť $1$), a spomedzi takých vyberieme tú najväčšiu.

Podmnožín je $2^n$, každá z nich najviac $n$ veľká (a musíme ich všetky kvôli kontrole podmienky prejsť), takže časová zložitosť tohto riešenia bude $O(n \cdot 2^n)$, respektíve $O(2^n)$. Všetky podmnožiny musíme mať aj uložené v pamäti, takže pamäťová zložitosť bude rovnaká.

Niečo lepšie

Ak chceme vymyslieť efektívnejšie riešenie, musíme k úlohe pristupovať trochu inak. Spomeňme si, že hľadáme nie nutne súvislú, o 1 rastúcu, postupnosť čísel, teda postupnosť tvaru

$l, l + 1, \cdots, r$

kde $l$ je najmenšie číslo v postupnosti a $r$ je najväčšie. Teda $l$ môže byť akékoľvek číslo od $1$ do $n$ a $r$ môže byť akékoľvek číslo od $l + 1$ do $n$. (Nemá zmysel riešiť situáciu $r = l$, pretože taká môže nastať pri akomkoľvek $l$, a teda môžeme proste počítať s tým, že akákoľvek platná postupnosť bude mať dĺžku aspoň $1$.)

To znamená, že existuje iba kvadratické množstvo postupností, ktoré treba skontrolovať. (V každej pozícii v poli sa môže postupnosť začínať a môže mať maximálne $n$ prvkov.) Keď pri každej z nich nekontrolujeme, či pokračuje niekde ďalej v poli, ale či sa jej pokračovanie nenachádza niekde ďalej v poli (čo sa dá zisťovať pažravo, lebo ak sme také číslo ešte nevideli, znamená to, že je ďalej v poli), vieme všetky postupnosti skontrolovať v časovej zložitosti $O(n^2)$.

Pamätať si potrebujeme iba pôvodné pole a pozície jednotlivých čísel v ňom, takže pamäťová zložitosť je $O(n)$.

Optimálne riešenie

Najlepšie riešenie dosiahneme použitím dynamického programovania. Opäť si budeme pamätať pozície jednotlivých čísel, no tentoraz si ich nepotrebujeme predpočítavať, ale stačí si ich zapisovať za chodu.

Pre každé číslo v poli sa spýtame, či už vieme, kde sa nachádza o jedno menšie od neho (okrem jednotky, pre tú to logicky nevieme za žiadnych okolností).

Ak nie, znamená to, že je niekde za aktuálnou pozíciou v poli, a teda pre aktuálne číslo začíname novú postupnosť a zapíšeme si preň dĺžku postupnosti $1$.

Ak áno, znamená to, že pokračujeme v postupnosti toho o jedno menšieho čísla, a teda si pre aktuálne číslo zapíšeme dĺžku postupnosti o $1$ väčšiu, ako máme zapísanú pre to o jedno menšie číslo.

Popri tom si pamätáme, akú najdlhšiu postupnosť sme videli.

Takýmto spôsobom nám stačí pole prejsť iba raz, a teda časová zložitosť takéhoto riešenia je $O(n)$.

Pamätať si musíme pôvodné pole, pozície jednotlivých čísel v ňom, a dĺžku postupnosti pre každú pozíciu v poli, teda pamäťová zložitosť je tiež $O(n)$.

n = int(input())
pole = [int(i) for i in input().split(" ") if i.isnumeric()]
najdlhsia_podpostupnost, podpostupnosti, idxs = 0, [], [-1 for _ in range(n)]
for idx, cislo in enumerate(pole):
    prev_idx = idxs[cislo - 1 - 1] if cislo > 1 else -1
    if prev_idx == -1:
        podpostupnosti.append(1)
    else:
        podpostupnosti.append(podpostupnosti[prev_idx] + 1)
    idxs[cislo - 1] = idx
    najdlhsia_podpostupnost = max(najdlhsia_podpostupnost, podpostupnosti[-1])
print(n - najdlhsia_podpostupnost)
#include <iostream>

using namespace std;

int main() {
    int n, idx;
    cin >> n;
    int pole[n], najdlhsia_podpostupnost = 0, idxs[n], podpostupnosti[n], podpostupnosti_pointer = 0;
    for (idx = 0; idx < n; idx++) idxs[idx] = -1;
    for (idx = 0; idx < n; idx++) {
        cin >> pole[idx];
        int prev_idx = pole[idx] > 1 ? idxs[pole[idx] - 1 - 1] : -1;
        if (prev_idx == -1) podpostupnosti[podpostupnosti_pointer++] = 1;
        else podpostupnosti[podpostupnosti_pointer++] = podpostupnosti[prev_idx] + 1;
        idxs[pole[idx] - 1] = idx;
        najdlhsia_podpostupnost = max(najdlhsia_podpostupnost, podpostupnosti[podpostupnosti_pointer - 1]);
    }
    cout << n - najdlhsia_podpostupnost << "\n";
    return 0;
}
Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty