Zadanie

Ako už viete z tretej úlohy v predošlej sérii1, starosta Kocúrkova plánuje rekonštrukciu autobusových zástávok.

Na pripomenutie, Kocúrkovo je jedna dlhá ulica pozdĺž ktorej je postavených \(n\) autobusových zastávok. Každá autobusová linka má dve konečné zastávky, medzi ktorými jej autobusy jazdia hore-dolu, pričom stoja aj na každej zastávke po ceste. Keďže Kocúrkovo je Kocúrkovo, môže sa stať, že niektorá linka začína aj končí na rovnakej zastávke (a teda autobus iba stojí na tejto zastávke).

Z politických dôvodov (o ktorých sa môžete dočítať v zadaniach minulej série) starosta chce, aby od začiatku rekonštrukcie čo najdlhšie platilo, že každý deň sa na každej linke rekonštruuje aspoň jedna zastávka.

Starosta vyhlásil verejnú súťaž a dostal veľa ponúk. Teraz potrebuje zistiť, ktorá z nich je najlepšia. Pomôžete mu ohodnotiť jednotlivé ponuky?

Ponuka o každej zastávke hovorí, ktorý deň sa má rekonštruovať. Kvalita ponuky je najmenšie číslo dňa, v ktorý sa na niektorej linke nebude rekonštruovať ani jedna zastávka.

Úloha

Na vstupe dostanete jednu ponuku rekonštrukcie – pre každú zastávku dostanete deň, v ktorý sa podľa tejto ponuky má rekonštruovať. Ďalej dostanete zoznam všetkých liniek aj s ich konečnými zastávkami. Vypočítajte (a vypíšte) kvalitu tejto ponuky. Inými slovami, pre danú postupnosť dní a zoznam liniek vypíšte najmenšie číslo dňa, v ktorý sa na niektorej linke nerekonštruuje žiadna zastávka.

Formát vstupu

V prvom riadku vstupu sú dve medzerou oddelené celé čísla \(n\) a \(m\) (\(1 \leq n,m \leq 1\,000\,000\)) – počet zastávok a počet autobusových liniek.

Zastávky si očíslujme číslami \(1\)\(n\) od začiatku Kocúrkova po jeho koniec.

V druhom riadku vstupu je \(n\) medzerou oddelených čísel \(d_1, d_2, \dots, d_n\) (\(0 \leq d_i \leq 10^9\)), kde \(d_i\) udáva číslo dňa od začiatku rekonštrukcie, kedy sa bude rekonštruovať zastávka číslo \(i\). Rekonštrukcia začína dňom číslo \(0\).

Nasleduje \(m\) riadkov, v každom z nich sú dve medzerou oddelené čísla \(z_i\) a \(k_i\) – čísla konečných zastávok \(i\)-tej linky. Platí, že \(1 \leq z_i \leq k_i \leq n\).

Formát výstupu

Vypíšte jediné číslo – najmenšie číslo dňa, v ktorý sa na niektorej linke nerekonštruuje žiadna zastávka.

Príklad

Input:

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

Output:

2

V dni číslo \(0\) a \(1\) sa na každej linke niečo rekonštruuje. V deň číslo \(2\) sa však už nerekonštruuje nič, takže dokonca pre každú linku platí, že sa tam nič nerekonštruuje.

Input:

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

Output:

0

Na linke \(2\) \(3\) sa nič nedeje v deň číslo \(0\).


  1. https://www.ksp.sk/ulohy/zadania/1259/

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

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