4. Prefixove rezne vzorové riešenie

8 4
1 4 3 4 3 2 2 1

5

4 3
1 1 2 1

-1

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;
}