Zadanie

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahni (liahen.ksp.sk). Keď budeš riešiť sadu loops_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Jarovi na jarko.paska@gmail.com

Prefix má rád rezne. Nedávno pribudla v Bratislave nová reštaurácia a všetci kamaráti, čo ju už navštívili Prefixovi vraveli, že tam robia tie najlepšie rezne. Keďže Prefix rád skúša nové chute rezňov, rozhodol sa, že tam zájde a objedná si všetky druhy rezňov, ktoré tam pripravujú. Po príchode však zistil, že objednávanie funguje v tejto reštaurácii veľmi zvláštnym spôsobom.

V reštaurácii je dlhý pult, na ktorom sú v jednom rade poukladané rezne rôznych druhov – černohorský, kyjevský, horčicový… Pri objednávaní si kupujúci vyberie súvislý úsek rezňov na pulte a čašníci mu naservírujú všetky rezne z tohto úseku. Avšak, pri jednej návšteve je možné si vybrať iba jediný (aj keď ľubovoľný) úsek.

Prefix by si už pri prvej návšteve chcel kúpiť z každého druhu rezňa aspoň jeden (nech teda zistí, ktoré rezne sú najlepšie), nechce to však s kupovaním prehnať a chcel by kúpiť čo najmenej rezňov.

Pomôžte Prefixovi vybrať najkratší úsek rezňov na pulte, ktorý obsahuje aspoň jeden z každého druhu rezňov. Samozrejme, môže sa stať, že na pulte sa nenachádzajú všetky druhy rezňov, ktoré reštaurácia ponúka (napríklad im práve došla horčica) a vtedy bude Prefix veľmi sklamaný.

Úloha

V reštaurácii ponúkajú \(m\) rôznych druhov rezňov a na pulte ich je v jednom rade vyložených \(n\). Vašou úlohou je nájsť dĺžku najkratšieho súvislého úseku, ktorý obsahuje všetkých \(m\) druhov rezňov, poprípade prehlásiť, že taký úsek neexistuje.

Formát vstupu

Na prvom riadku vstupu dostaneme dve celé čísla \(n\) a \(m\) – počet rezňov na pulte a počet rezňov v ponuke. Platí \(m \leq n\). Druhy rezňov si označujeme číslami od \(1\) po \(m\).

Na druhom riadku je \(n\) čísel \(x_1, x_2 ... x_n\) z rozsahu 1 až \(m\), číslo \(x_i\) reprezentuje druh \(i\)-teho rezňa na pulte.

Formát výstupu

Na jediný riadok výstupu vypíšte dĺžku najkratšieho úseku obsahujúceho aspoň jeden z každého druhu rezňov. Ak takýto úsek neexistuje, vypíšte “-1”.

Hodnotenie

Vaše riešenie bude otestované na \(3\) sadách vstupov. Za vyriešenie každej sady získate 5 bodov. Tieto sady sa líšia veľkosťou vstupných údajov.

V nasledujúcej tabuľke označuje \(n\) počet rezňov na pulte. Vo vstupných sadách platí:

Číslo sady 1 2 3
maximálne \(n\) \(100\) \(2\,000\) \(1\,000\,000\)

Príklady

Input:

8 4
1 4 3 4 3 2 2 1

Output:

5

Správnou možnosťou je vybrať úsek začínajúci na pozícii 4 a končiaci na pozícii 8. Tento úsek má dĺžku 5 a naozaj obsahuje všetky čísla od 1 po 4. Rozmyslite si, že kratší úsek s danou vlastnosťou naozaj neexistuje.

Input:

4 3
1 1 2 1

Output:

-1

Na pulte nie je vystavený rezeň druhu 3, preto neexistuje žiaden úsek spĺňajúci požadovanú vlastnosť.

Brute-force

Ak vám nenapadlo žiadne efektívne riešenie, jedna z prvých vecí, ktoré treba skúsiť je riešenie hrubou silou. Každé správne riešenie, hoci aj pomalšie, zväčša získa nejaké body. Preto sa ho nabudúce nebojte odoslať – radšej odovzdať riešenie, ktoré vám napadlo ako prvé, než mať za úlohu 0 bodov.

Najjednoduchšia vec, ktorú môžeme spraviť je vyskúšať všetky možné úseky rezňov a pre každý z nich zistiť, či sa v ňom nachádzajú všetky exisexistujúce druhy. Každý súvislý úsek rezňov vieme určiť jeho začiatkom a koncom, ktoré si označíme premennými \(z\) a \(k\). V dvoch cykloch preto vieme prejsť cez všetky možné dvojice hodnôt \(z\) a \(k\).

Pre daný úsek však potrebujeme vedieť zistiť, či sa v ňom nachádzajú všetky druhy rezňov. Na to si vytvoríme pole videli[], do ktorého si budeme značiť, koľko rezňov daného typu sa nachádza v úseku od \(z\) po \(k\). Presnejšie, v premennej videli[i] bude počet rezňov typu \(i\). Pomocou cyklu potom prejdeme zadaný úsek, do poľa videli[] si spočítame počty rezňov daného typu a posledným cyklom zistíme, či je každá hodnota videli[i] aspoň 1 – v úseku je aspoň jeden rezeň typu \(i\). Ak náš úsek spĺňa zadanú podmienku a je najkratší z dobrých úsekov, ktoré sme zatiaľ videli, tak si ho zapamätáme.

Časová zložitosť tohto riešenia je \(O(n^3)\). Rôznych úsekov, teda dvojíc \(z\) a \(k\), je zhruba \(n^2\) a pre každý z nich musíme prejsť vybraný úsek a zistiť, či je v ňom každý rezeň aspoň raz, čo bude trvať \(O(n+m)\) operácií. Pamätať si potrebujeme iba rezne zo vstupu, ktorých je \(n\), a pole videli[]. Pamäťová zložitosť je preto \(O(n + m)\)

#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000000;

int main () {
    int n, m;
    cin >> n >> m;
    vector<int> rezne(n);
    for (int i = 0; i < n; i++) {
        cin >> rezne[i];
        rezne[i]--;
    }

    int najkratsi = INF;
    for (int z = 0; z < n; z++) {
        for (int k = z; k < n; k++) {
            vector<int> videli(m, 0);
            for (int i = z; i <= k; i++) {
                videli[rezne[i]]++;
            }
            for (int i = 0; i < m; i++) {
                if (videli[i] < 1) break;
                if (i+1 == m) {
                    najkratsi = min(najkratsi, k-z+1);
                }
            }
        }
    }

    if (najkratsi == INF) cout << -1 << endl;
    else cout << najkratsi << endl;
}

Zrýchlenie predchádzajúceho riešenia

Ďalším dôvodom, pre ktorý je dobré začať s pomalým riešením je, že pomalé riešenie slúži často ako základ efektívnejšieho riešenia. Skúsme sa teda pozrieť na to, čo robilo naše predchádzajúce riešenie naviac. Keď sa pozrieme, v akom poradí skúšame úseky, zistíme, že po úseku od \(z\) po \(k\) nasleduje úsek od \(z\) po \(k+1\). Ten sa však od predchádzajúceho úseku líši iba tým, že má o jeden rezeň viac – rezeň na pozícii \(k+1\). Teda ani pole videli[] sa veľmi nezmení, stačí pridať tento jeden rezeň. Namiesto toho, aby sme teda opäť prechádzali celý úsek, pridáme iba jediný rezeň.

Pre každý z \(n^2\) úsekov tak spravíme iba jednu operáciu na zmenu poľa videli[] a následne sa pozrieme, či je v tomto poli každý rezeň aspoň raz. Časová zložitosť je teda \(O(n^2m)\), čo je o kúsok lepšie. Ešte však nie sme hotoví.

Prechodom na ďalší úsek nám pribudol jediný rezeň. Ak úsek od \(z\) po \(k\) neobsahoval každý rezeň aspoň raz, tak úsek od \(z\) po \(k+1\) ho obsahuje iba ak na pozícii \(k+1\) bol posledný chýbajúci druh rezňa. Ak sme teda pridali rezeň typu \(i\), tak hodnota videli[i] sa zmenila z 0 na 1 (rezeň \(i\) v úseku nebol a zrazu tam jeden je). Naše riešenie si teda bude všímať, či sa hodnota poľa videli[] zmenila z 0 na 1 a bude počítať, koľko takýchto udalostí nastalo. Počet týchto udalostí si bude pamätať v premennej \(d\). V okamihu, keď uvidí \(m\) takýchto zmien tak vie, že v danom úseku je každý druh rezňa aspoň raz – každý druh totiž vytvorí jednu takúto udalosť prvýkrát keď ho do nášho úseku pridáme.

Výsledná časová zložitosť je \(O(n^2)\). Pre každý úsek totiž iba zmeníme jednu hodnotu v poli videli[] a pozrieme sa, či táto zmena pridala do úseku nový druh rezňov.

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main () {
    int n, m;
    cin >> n >> m;

    vector<int> rezne(n);
    for (int i = 0; i < n; i++) {
        cin >> rezne[i];
        rezne[i]--;
    }

    int najkratsi = INF;
    for (int z = 0; z < n; z++) {
        vector<int> videli(m, 0);
        int d = 0;
        for (int k = z; k < n; k++) {
            videli[rezne[k]]++;
            if (videli[rezne[k]] == 1) d++;
            if (d == m) {
                najkratsi = min(najkratsi, k-z+1);
            }
        }
    }
    if (najkratsi == INF) cout << -1 << endl;
    else cout << najkratsi << endl;
}

Vzorové riešenie

Nerobíme však stále niečo zbytočne? Pozrime sa ešte raz na to, čo robíme. Zvolíme si začiatok \(z\) a postupne zväčšujeme pozíciu konca \(k\). Do poľa videli[] si značíme počty rezňov jednotlivých druhov, ktoré sú v tomto úseku. A vždy, keď nájdeme nový druh rezňa, hodnota videli[i] sa zmení z 0 na 1, tak zväčšíme hodnotu \(d\). Ak pre úsek platí, že \(d = m\) tak vieme, že daný úsek obsahuje každý druh rezňa aspoň raz.

Hodnota \(d\) sa však iba zväčšuje. To znamená, že keď raz pre nejaký úsek platí \(d = m\), tak aj všetky dlhšie úseky začínajúce na pozícii \(z\) obsahujú všetky druhy rezňov. Tieto úseky sú však dlhšie, preto sa nám ich neoplatí ani skúšať. Ako teda zväčšujeme hodnotu \(k\), tak v okamihu, keď \(d = m\), sme našli najkratší úsek začínajúci na \(z\), ktorý obsahuje každý druh rezňa. Ďalšie, väčšie hodnoty \(k\) nemusíme ani skúšať a môžeme začať skúšať ďalší začiatok \(z+1\).

Toto ešte nestačí, uvedomme si však nasledujúcu vec. Najkratší úsek obsahujúci všetky rezne, ktorý začína na pozícii \(z+1\) nemôže končiť skôr ako aktuálna hodnota \(k\). Pozícia \(k\) bola prvá taká, že úsek \(z\)\(k\) obsahoval všetky druhy rezňov. Predstavme si, že úsek od \(z+1\)\(k'\) obsahuje všetky rezne, pričom \(k' < k\). Tak potom zjavne aj úsek od \(z\) po \(k'\) obsahuje všetky druhy rezňov. Je to predsa úsek, ktorý obsahuje o jeden rezeň viac ako úsek od \(z+1\) po \(k'\). Hodnota \(k\) však bola najmenšia taká, takže žiadne menšie \(k'\) existovať nemôže.

Keď teda začneme so začiatkom \(z+1\) nemusíme skúšať všetky úseky, ktoré končia skôr ako \(k\). Tie totiž určite všetky rezne obsahovať nebudú. Vieme však vhodne upraviť hodnoty v poli videli[] a \(d\)? Úseky od \(z\) po \(k\) a od \(z+1\) po \(k\) sa líšia iba v rezni na pozícii \(z\), ktorý sme odobrali. Ak bol druhu \(i\) tak to znamená, že musíme zmenšiť hodnotu videli[i] o 1. A počet druhov v tomto úseku (hodnota \(d\)) sa zmení iba ak sme odstránili jediný rezeň svojho druhu, teda ak sa hodnota videli[i] zmenila z 1 na 0.

Ľahko teda upravíme naše polia a hodnotu \(d\). Následne môžeme opäť zvyšovať koniec \(k\), až kým sa \(d\) nebude znova rovnať hodnote \(m\). Vtedy posunieme začiatok \(z\) a pokračujeme. Pre každý začiatok tak nájdeme najkratší úsek obsahujúci všetky druhy rezňov. Z týchto úsekov zoberieme ako výsledok najkratší z nich.

Časová zložitosť takéhoto riešenia je \(O(n)\). Uvedomme si, že v každom kroku nášho algorimu o 1 zväčšíme buď hodnotu \(z\) alebo \(k\). Obe tieto hodnoty môžeme zväčšiť najviac \(n\) krát, preto spravíme najviac \(2n\) operácií. Pri každom posune pritom upravíme iba jedinú pozíciu poľa videli[] a premennú \(d\). Pamäťová zložitosť je stále \(O(n + m)\).

Všimnite si, ako sme sa z najľahšieho riešenia postupne prepracovali až k vzoráku. A stačilo si iba všímať, čo robíme navyše.

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main () {
    int n, m;
    cin >> n >> m;

    vector<int> rezne(n);
    for (int i = 0; i < n; i++) {
        cin >> rezne[i];
        rezne[i]--;
    }

    int najkratsi = INF;
    vector<int> videli(m, 0);
    int d = 0;
    int k = 0;
    for (int z = 0; z < n; z++) {
        while(k < n && d != m) {
            videli[rezne[k]]++;
            if (videli[rezne[k]] == 1) {
                d++;
            }
            k++;
        }
        if (d == m) {
            najkratsi = min(najkratsi, k-z);
        }
        videli[rezne[z]]--;
        if(videli[rezne[z]] == 0) {
            d--;
        }
    }
    if (najkratsi == INF) cout << -1 << endl;
    else cout << najkratsi << endl;
}

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