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$ až $k$ obsahoval všetky druhy rezňov. Predstavme si, že úsek od $z+1$ až $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;
}