Zadanie

Kubo je veľký milovník štipľavých jedál. Na poličke v kuchyni má \(N\) koreničiek zoradených od najmenej po najviac štipľavú. Každá korenička je označená číslom od \(1\) po \(N\).
Raz však vyskúšal známu kalifornskú papričku a keď so slzami v očiach odkladal koreničky naspäť, všetky ich poprehadzoval.

Keď sa neskôr spamätal a rozhodol sa ich znova upratať, zistil, že nemá dosť síl na veľké presuny. Dokáže vždy vymeniť len dve susedné koreničky – teda tie, ktoré stoja na pozíciách \(A\) a \(A + 1\).

Úloha

Vašou úlohou je zistiť, na koľko najmenej susedných výmen vie Kubo dosiahnuť,
aby sa K najmenej štipľavých koreničiek (čísel \(1\) až \(K\)) nachádzalo na prvých \(K\) pozíciách,
v ľubovoľnom poradí.

Formát vstupu

V prvom riadku vstupu sú dve celé čísla \(N\) a \(K\) – počet koreničiek a počet najmenej štipľavých koreničiek, ktoré chce Kubo dostať na začiatok.

V druhom riadku je \(N\) rôznych celých čísel od \(1\) po \(N\), oddelených medzerami — aktuálne poradie koreničiek na poličke.

Sada 1 2 3 4
\(1 \leq N \leq\) \(20\) \(10^3\) \(10^6\) \(10^6\)

vo všetkých sadách platí \(1 \leq K \leq N\) ## Formát výstupu

Vypíšte jedno celé číslo — minimálny počet susedných výmen, ktoré musí Kubo vykonať,
aby sa najmenších \(K\) koreničiek presunulo na prvé \(K\) pozície (v ľubovoľnom poradí).

Príklad

Input:

4 2
2 3 1 4

Output:

1

Stačí vymeniť 3-ku s 1-kou

Input:

7 1 
1 6 5 7 4 2 3

Output:

0

V tomto vstupe už netreba nič vymieňať

Input:

5 3
4 1 5 3 2

Output:

5

Riešenie hrubou silou

Úlohu vieme riešiť pomocou hrubej sily. Iterujeme zľava doprava po prvých \(K\) pozíciách. Ak sa na nejakej pozícii nachádza korenička s číslom väčším než \(K\), nájde sa najbližšia správna korenička s číslom \(≤ K\) napravo a pomocou postupných susedných výmen sa presunie na túto pozíciu. Každá takáto výmena sa započíta do výsledku. Algoritmus pokračuje, kým prvých K pozícií neobsahuje iba koreničky 1 až K, pričom ich vnútorné poradie nie je dôležité. Týmto postupom sa nikdy nerobia zbytočné výmeny, pretože každá výmena rieši konkrétny problémový pár. Problémový pár je dvojica koreničiek, kde korenička s číslom väčším než K stojí pred koreničkou s číslom menším alebo rovným K, a každá takáto inverzia musí byť odstránená aspoň jednou susednou výmenou.

Optimálne riešenie

Kľúčové je uvedomiť si, že koreničky na indexoch \(i\) a \(j\) vieme vymeniť pomocou \(|i - j|\) susedných výmen, takže nie je potrebné jednotlivé výmeny simulovať. Nech \(p_i\) označuje index \(i\)-tej koreničky s číslom \(\le K\) v pôvodnom poradí poľa (číslované zľava doprava). Korenička na pozícii \(p_i\) má pred sebou presne \(p_i - i\) koreničiek s číslom väčším než \(K\), s ktorými tvorí problémové dvojice. Pole prechádzame zľava doprava. Pri každej koreničke s číslom \(\le K\) pripočítame do výsledku jej aktuálny index \(i\), čím získame hodnotu \[ \sum p_i. \] Z tejto hodnoty následne odčítame \[ \sum_{i=0}^{K-1} i = \frac{(K-1)K}{2}. \] Výsledkom je presný počet problémových dvojíc, a teda aj minimálny počet potrebných susedných výmen.

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

Takéto riešenie bude mať časovú zložitosť \(O(n)\) a pamäťovú zložitosť \(O(1)\)

V riešení sa využíva iba lineárne iterovanie cez prvky, pričom ich nie je potrebné ukladať do pamäte. A zopár premenný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ť.