5. Obrovská rekonštrukcia vzorové riešenie

5 3
0 1 0 1 0
1 3
2 5
4 5

2

5 4
0 1 2 1 1
1 3
2 3
1 4
3 5

0

Pozrieme sa, ako sa dá táto úloha riešiť hrubou silou, a pomocou niekoľkých dôležitých pozorovaní sa dostaneme ku vzorovému riešeniu.

Bruteforce

Jednoduchý bruteforce môžeme naprogramovať tak, že budeme robiť presne to, čo hovorí zadanie. Pre každú linku sa pozrieme aké najmenšie číslo na nej chýba, (napríklad tak že sa pre každé číslo pozrieme na celý interval a hľadáme či tam je) a vypíšeme najmenšie z nich. Takéto riešenie má časovú zložitosť \(O(m\cdot n^2)\) a dostane dva až tri body.

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> dni(n+1);
    for(int i = 1; i <= n; i++) cin >> dni[i];
    int mi=n+2;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        for(int j = 0; j <= b-a+1; j++){
            bool mam=0;
            for(int k = a; k <= b; k++){
                if (dni[k] == j){
                    mam = 1;
                    break;
                }
            }
            if (!mam){
                mi = min(mi, j);
                break;
            }
        }
    }
    cout << mi << endl;    
}

Vzorové riešenie

Môžeme si všimnúť, že náš bruteforce robí veľa krát to isté. Najme, ak sa intervaly prekrývajú, alebo dokonca opakujú. Niektoré prípady sa dajú vyriešiť jednoducho. Napríklad, ak sa nejaký interval presne zopakuje, môžeme si pamätať aký bol výsledok a druhý krát sa naň len pozrieť. Tiež nie je zložité vyriešiť prípady, keď je jeden interval celý obsiahnutý v inom. Vtedy stačí zistiť riešenie pre vnútorný, lebo vonkajší obsahuje všetko to čo vnútorný (možno niečo viac).

Na plný počet to však stále nestačí. Musíme vyriešiť aj prípady, keď sa intervaly čiastočne prekrývajú. Spravíme to tak, že si budeme jeden interval posúvať a postupne pri tom pokryjeme každý interval, ktorý v sebe nemá obsiahnutý žiaden menší interval.

Koniec nášho intervalu budeme posúvať od začiatku po koniec, a vždy sa pozrieme iba na najmenší z intervalov, ktoré končia na tomto políčku. Všetky ostatné čo na ňom končia ho celý obsahujú. Môžeme si všimnúť, že ak sa v jednom kroku pozeráme na interval, ktorý začína na políčku \(z\), ďalej nás zaujímajú len intervaly, ktoré začínajú ďalej. Ak narazíme na interval ktorý nezačína ďalej, znamená to, že obsahuje celý interval na ktorý sme sa už pozerali.

Ak ďalší začína ďalej, potrebujeme začiatok z predošlého kola posunúť. Spravíme to tak, aby sme rovno zistili výsledok pre nový interval. Budeme si pamätať pre každé číslo, koľko krát sa nachádza v našom intervale, a pri posúvaní ľavého konca ich budeme z tade vyhadzovať (pri posúvaní pravého pridávať). Takto budeme vždy vedieť, aké čísla sú v intervale, na ktorý sa práve pozeráme. Stále však nevieme, či tam nejaké číslo chýba. Preto si budeme okrem toho pamätať aj koľko rôznych čísel tam je. Ak zistíme, že pole je dlhšie ako počet rôznych čísel, znamená to, že tam nejaké chýba. Tiež to znamená, že v ďalšom výpočte nás nemusia zaujímať čísla od neho väčšie, a preto môžeme pole v ktorom si ich pamätáme skracovať, kým naša podmienka nezačne platiť (počítame len čísla ktoré boli do teraz v každom intervale). Ak pri tom vyhodíme nejaké číslo ktoré sa v intervale nachádzalo, musíme aj zmenšiť počet rôznych čísel ktorý si pamätáme.

Keď takýmto spôsobom prejdeme celé pole a všetky intervaly, stačí nám vypísať počet rôznych čísel, lebo v každom intervale na ktorý sme sa pozerali, ich aspoň toľko je.

Časová zložitosť takéhoto riešenia je \(O(m+n)\), pretože začiatok aj koniec intervalu na ktorý sa práve pozeráme posúvame iba doprava, a to sa dá najviac \(n\) - krát. Keď nesedí počet rôznych čísel, pole vždy len zmenšujeme, čo sa tiež dá najviac \(n\) - krát.

Pamäťová zložitosť je \(O(n)\), pretože pre každé políčko v poli nám stačí pamätať si začiatok najkratšieho intervalu, ktorý na ňom končí.

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> dni(n + 1);
    for(int i = 1; i <= n; i++) cin >> dni[i];
    
    vector<int> zacina(n + 1, -1);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        zacina[b] = max(zacina[b], a);
    }
    vector<int> kolkokrat(n + 1, 0);
    int kolko = 0;
    int lavy = 1;
    for (int pravy = 1; pravy <= n; pravy++){
        if (dni[pravy] < kolkokrat.size()){
            kolkokrat[dni[pravy]]++;
            if (kolkokrat[dni[pravy]] == 1) kolko++;
        }
        if(zacina[pravy] == -1) continue;
        while(lavy < zacina[pravy]){
            if(dni[lavy] < kolkokrat.size()){
                kolkokrat[dni[lavy]]--;
                if(kolkokrat[dni[lavy]] == 0)kolko--;
            }
            lavy++;
        }
        while (kolko < kolkokrat.size()){
            if(kolkokrat[kolkokrat.size() - 1] != 0)kolko--; 
            kolkokrat.pop_back();
        }
    }
    cout<<kolkokrat.size()<<endl;
}