2. Znova zašpinení programátori vzorové riešenie

5 6
2 2 1 3 5 2

2 5 3 1 4

Táto úloha sa dala riešiť viacerými spôsobmi. V tomto vzoráku si ukážeme jedno pomalé a dve rýchle riešenia.

Naivná simulácia

Budeme robiť presne to, čo nám hovorí zadanie. V jednom poli si budeme pamätať, v akom poradí sú gély na kope a postupne budeme simulovať sprchovanie programátorov. Vždy, keď sa nejaký programátor osprchuje, nájdeme jeho gél v našom poli, všetky gély nad ním posunieme o jednu pozíciu nižšie a náš hľadaný gél dáme na samý vrch. Na konci vypíšeme poradie, v akom sú gély na kope. Pri implementácii si treba dať pozor na to, aby sme gély posúvali v dobrom poradí, inak sa nám môže stať, že si jedným gélom postupne prepíšeme celú posúvanú časť poľa.

Zložitosť

Vždy, keď sa nejaký programátor osprchuje, budeme musieť posunúť všetky gély, ktoré sú v kope nad jeho gélom. V najhoršom prípade sa nám môže stať, že po každom sprchovaní budeme musieť posunúť všetkých \(n\) gélov. Časová zložitosť je teda \(O(mn)\), pamäťová zložitosť je \(O(n)\).

#include <cstdio>

int kopa[200000];

int main() {
    int n, m;
    scanf("%d %d",&n,&m);
    for(int i=0; i<n; i++)
        kopa[i] = i+1;

    for(int i=0; i<m; i++) {
        int aktualny;
        scanf("%d",&aktualny);
        int kde_je;
        for(int j=0; j<n; j++)
            if(kopa[j] == aktualny) // najdeme gel v kope
                kde_je = j;

        for(int j=kde_je; j>0; j--) // vsetky gely nad aktualnym klesnu
            kopa[j] = kopa[j-1];
        kopa[0] = aktualny;         // a aktualny pojde na vrch kopy
    }

    for(int i=0; i<n; i++) {
        printf("%d",kopa[i]);
        if(i < n-1) printf(" ");
        else printf("\n");
    }
}

Spájaný zoznam

Opäť budeme celý dej simulovať, ale informáciu o kope si budeme pamätať trochu šikovnejšie. Namiesto toho, aby sme si pamätali poradie všetkých gélov, budeme si pre každý gél pamätať, ktorý gél je v kope hneď pod ním a ktorý gél je hneď nad ním (prípadne, že daný gél je na úplnom vrchu, alebo spodku kopy). K tomu si budeme navyše pamätať číslo gélu, ktorý je aktuálne na vrchu kopy. Všimnime si, že keď presúvame gél z nejakého miesta na vrch kopy, väčšine gélov sa susedia nezmenia. Konkrétne, ak chceme presunúť gél \(A\), pričom nad ním bol gél \(B\), pod ním bol gél \(C\) a na vrchu kopy bol gél \(D\), tak po presune pod gélom \(B\) už nebude \(A\), ale \(C\), nad gélom \(C\) bude gél \(B\), nad gélom \(D\) bude \(A\) a gél \(A\) bude na vrchu kopy, pričom pod ním bude gél \(D\). Nič iné už v pamäti meniť nepotrebujeme.

Na konci vypíšeme gél, ktorý je na vrchu kopy, potom gél tesne pod ním, potom gél, ktorý bol pod ním atď., až kým neprídeme na spodok kopy.

Aby sme pri implementácii nemuseli špeciálne ošetrovať spodok a vrch kopy, môžeme urobiť nasledovný trik: na spodok aj na vrch kopy si pridáme po jednom virtuálnom géli (s číslami \(0\) a \(n+1\)), s ktorými nikdy nebudeme hýbať. Vďaka tomu nikdy nebudeme musieť hýbať s gélami, ktoré sú na vrchu, alebo na spodku kopy. Potom si ani nebudeme musieť pamätať, ktorý gél je na vrchu skutočnej kopy, keďže to vždy bude gél tesne pod gélom \(0\).

Zložitosť

Na začiatku musíme nastaviť všetkým gélom susedov (v čase \(O(n)\)). Pri každom sprchovaní musíme zmeniť konštantne veľa premenných (dokopy v čase \(O(m)\)) a na konci musíme prejsť cez všetky gély a vypísať ich (v čase \(O(n)\)). Celková časová zložitosť je teda \(O(m + n)\). Pamäťová zložitosť je \(O(n)\)

#include<cstdio>

int nad[200002], pod[200002];

int main() {
    int n, m;
    scanf("%d %d",&n,&m);

    for(int i=0; i<=n; i++) pod[i] = i+1;
    for(int i=1; i<=n+1; i++) nad[i] = i-1;

    for(int i=0; i<m; i++) {
        int aktualny;
        scanf("%d",&aktualny);
        pod[nad[aktualny]] = pod[aktualny];
        nad[pod[aktualny]] = nad[aktualny]; // vyberieme aktualny gel z kopy
        pod[aktualny] = pod[0];
        nad[aktualny] = 0;                  // pridame ho na vrch kopy
        nad[pod[0]] = aktualny;
        pod[0] = aktualny;                  // a aktuailzujeme gely na vrchu kopy
    }

    int gel = pod[0];
    for(int i=0; i<n; i++) {
        printf("%d", gel);
        if(i < n-1) printf(" ");
        else printf("\n");
        gel = pod[gel];
    }
}

Naspäť v čase

Nakoniec si ukážeme jedno riešenie, ktoré je myšlienkovo trochu náročnejšie, ale má jednoduchšiu implementáciu. Všimnime si, že ak sa programátor niekedy počas dňa osprchoval, potom všetci, ktorí sa sprchovali po ňom (presnejšie povedané, po tom, ako sa náš programátor osprchoval posledný raz), budú mať svoje gély v kope nad jeho gélom a všetci ostatní budú mať gély pod jeho gélom. Inými slovami, na konci bude na vrchu kopy gél programátora, ktorý sa sprchoval ako posledný. Pod ním bude gél programátora, ktorý sa sprchoval ako predposledný, atď.. Gély programátorov, ktorí sa nesprchovali, budú úplne na spodku kopy v rovnakom poradí, ako boli na začiatku.

Úlohu teda vyriešime nasledovne: budeme prechádzať zoznamom sprchovaní v opačnom poradí, ako bol na vstupe. Vždy, keď nájdeme nejakého programátora, ktorého sme ešte nevideli (teda sme našli posledné sprchovanie tohto programátora), vypíšeme jeho číslo. Keďže všetkých programátorov, ktorí sa sprchovali po ňom, sme už videli (a teda aj vypísali), tak sa nám nestane, že by sme niektoré číslo vypísali príliš skoro. Nakoniec ešte prejdeme všetky gély v poradí, v akom boli na začiatku (teda od \(1\) do \(n\)) a vypíšeme tie, ktoré sme ešte nevypísali.

Zložitosť

Musíme načítať a prejsť \(m\)-prvkový zoznam sprchovaní a potom ešte \(n\)-prvkový zoznam gélov. Časová zložitosť je teda \(O(m + n)\). Potrebujeme si pamätať celý zoznam sprchovaní (lebo ho budeme prechádzať v opačnom poradí, ako bol na vstupe) a pre každého programátora si potrebujeme pamätať, či sme ho už videli (či sme už vypísali číslo jeho gélu). Preto aj pamäťová zložitosť je \(O(m + n)\).

#include <cstdio>

bool videl_som[200001];
int sprchovanie[200000];
int vypisanych = 0;

int main()
{
    int n, m;
    scanf("%d %d",&n,&m);
    for(int i=1; i<=n; i++)
        videl_som[i] = 0;
    for(int i=0; i<m; i++)
        scanf("%d",&sprchovanie[i]);

    for(int i=m-1; i>=0; i--) {
        if(!videl_som[sprchovanie[i]]) {
            printf("%d",sprchovanie[i]);
            vypisanych++;
            if(vypisanych < n) printf(" ");
            else printf("\n");
            videl_som[sprchovanie[i]] = 1;
        }
    }
    for(int i=1; i<=n; i++) {
        if(!videl_som[i]) {
            printf("%d",i);
            vypisanych++;
            if(vypisanych < n) printf(" ");
            else printf("\n");
        }
    }
}