4. Zašpinení programátori vzorové riešenie

5
1 5 3 2 4
1 3 4 5 2

2
5

Poďme si princíp vysvetliť na príkade. Majme 7 sprchových gélov, ktoré boli na začiatku na kope v stave 0, 1, 2, 3, 4, 5, 6 a po jednom dni sprchovania v stave 0, 1, 3, 4, 6, 5, 2 (v týchto príkladoch za “spodok” kopy považujeme ľavú stranu riadku).

Najmenší možný počet

Keď sa programátor sprchuje, tak vytiahne svoj sprchový gél z ľubovoľnej pozície v kope a položí ho na vrch kopy. To nič nemení na kope pod ním ani nad ním, okrem najvyššej pozície. Preto, ak sa spodky počiatočnej aj výslednej kopy zhodujú, znamená to, že tieto gély neboli použité – v našom prípade gély 0, 1. Použitý gél sa prejaví tak, že chýba vo výslednej postupnosti na svojom očakávanom mieste – gél 2 v druhej postupnosti chýba. Gély nad ním (ak nie sú použité) sú ale stále v nezmenenom poradí – gély 3, 4. Ďalej je pôvodné poradie opäť narušené, lebo bol použitý gél 5.

Vo výslednej postupnosti na pôvodných miestach teda chýbajú gély 2, 5, a preto je v tomto príklade odpoveďou \(2\).

Najväčší možný počet

Tu je odpoveď celkom zrejmá. Každý programátor sa sprchuje najviac raz za deň. Nech výsledná kopa vyzerá akokoľvek, vždy ju vieme vytvoriť tak, že sa osprchujú všetci programátori práve v poradí, v akom sú gély vo výslednej kope. Teda, ak sa chce sprchovať čo najväčší počet programátorov, každý sa bude sprchovať práve raz. Odpoveď je teda \(n\).

Poďme implementovať

Základná myšlienka algoritmu je, že máme 2 ukazovatele, jeden do každého z dvoch polí. Najskôr ukazujú na počiatočnú pozíciu. Máme tiež premennú, kde si pamätáme, koľko použitých šampónov sme našli.

Ak sa čísla šampónov, na ktoré ukazovatele ukazujú, zhodujú, oba sa posunú o jednu pozíciu doprava. Našli sme nepoužitý gél.

Ak sa niekde nezhodujú,¹ zvýšime počet osprchovaných programátorov a preskočíme použitý gél v pôvodnej postupnosti (posunieme ukazovateľ o jedno doprava). Postupnosti sa budú zhodovať, až kým nenájdeme ďalší použitý gél.

Postup opakujeme, kým neprejdeme celú pôvodnú postupnosť. Na konci budeme mať najmenší možný počet osprchovaných programátorov.

Zložitosti

Z popisu algoritmu je zrejmé, že časová zložitosť bude \(O(n)\), lebo každú postupnosť prejdeme nanajvýš raz. Lepšia časová zložitosť sa dosiahnuť nedá, lebo musíme načítať celý vstup. Pamäťová zložitosť bude tiež \(O(n)\). Lepšie to opäť nejde, lebo keď postupnosti prechádzame, musíme si aspoň jednu pamätať celú.

#include<cstdio>

#define For(i, n) for(int i = 0; i < n; i++) 

int n;
int povodna[500042], vysledna[500042];

int main() {
    scanf(" %d", &n);
    For(i, n) scanf(" %d", &povodna[i]);
    For(i, n) scanf(" %d", &vysledna[i]);

    int a = 0, b = 0, pouzite = 0;
    
    while(a < n){
        if(povodna[a] == vysledna[b]) {
            a++;
            b++;
        } else {
            a++;
            pouzite++;
        }
    }

    printf("%d\n%d\n", pouzite, n);
    return 0;
}

input()                # n nas nezaujima :P
povodna_kopa = input().split()
vysledna_kopa = input().split()

b = 0
vysledok = 0

for gel in povodna_kopa:
    if gel == vysledna_kopa[b]:
        b += 1         # Kopy sa zhoduju, ideme dalej
    else:
        vysledok += 1  # Niekto sa osprchoval

print('{0}\n{1}'.format(vysledok, len(povodna_kopa)))