5. Poradie tanečníkov vzorové riešenie

1

1

5
5 2
4 3
2 4
3 1

1
3
4
2
5

6
2 3
4 6
5 1
1 2
6 5

3
2
1
5
6
4

V tomto vzorovom riešení začneme tým, že si ukážeme ako zistiť, ktorý žiak je prvý v rade. S pomocou tejto informácie navrhneme algoritmus na riešenie úlohy a pokúsime sa ho čo najviac zefektívniť. Pripravení?

Kto je prvý v poradí?

Zadanie nám garantuje, že v polovici testovacích sád bude prvý vždy žiak s číslom 1. To nám však k vzorovému riešeniu nestačí. Na vstupe dostaneme o \(n-1\) študentoch informáciu, kto sa nachádza pred nimi. Prečo o \(n - 1\) a nie \(n\)? Pretože niekto musí byť vždy prvý v rade. A pred ním sa už nenachádza nikto. Potrebujeme teda nájsť číslo žiaka, o ktorom nedosatneme na vstupe informáciu o žiakovi pred ním.

Použijeme na to \(n\) prvkové pole videni[], ktoré bude najskôr obsahovať samé 0. Na pozíciu videni[i] zapíšeme 1, ak sme na vstupe dostali informáciu o žiakovi, ktorí stojí pred žiakom \(i\). Na konci celé pole prejdeme a pozícia, na ktorej sa nachádza 0, je náš hľadaný prvý žiak v poradí. Ak používame C++, musíme si ešte dať pozor na indexovanie prvkov poľa – spraviť ho buď o 1 prvok väčšie, alebo všetky čísla žiakov zmenšovať o 1.

#include <iostream>

using namespace std;

int main() {
    int prvy, n, x, y;
    cin >> n;
    int videni[n+1];
    for (int i = 1; i <= n; ++i) videni[i] = 0;

    for (int i = 0; i < n-1; ++i) {
        cin >> x >> y;
        videni[x] = 1;
    }
    for (int i = 1; i <= n; ++i) {
        if (videni[i] == 0) {
            prvy = i; break;
        }
    }
    cout << prvy << endl;
}

Základná myšlienka

Teraz už vieme, kto je na prvej pozícii – nech je to žiak s číslom \(k\). Potrebujeme zistiť, kto sa nachádza na druhom mieste. Niekde na vstupe sme určite dostali dvojicu v tvare z k, ktorá hovorila, že pred tanečníkom \(z\) sa nachádza tanečník \(k\). To ale znemená, že na pozícii \(2\) musí byť žiak s číslom \(z\). Následne môžeme zobrať číslo \(z\) a zopakovať rovnaký postup pre zistenie čísla na tretej pozícii. Stačí ak nájdeme na vstupe dvojicu y z. A toto môžeme opakovať postupne pre všetky pozície, teda \(n-1\) krát (\(n-1\) preto, lebo prvý prvok sme zisťovali zvlášť).

Teraz už potrebujeme iba pre každého žiaka vedieť rýchlo vyhľadať, kto stojí za ním (tohto človeka nazvime prechodcom nášho žiaka), aby sme sa mohli postupne posúvať ďalej. Ukážeme si 2 možné riešenia.

Pomalšie riešenie

Prvé riešenie spočíva v tom, že zakaždým budeme prechádzať všetky údaje, ktoré sme dostali na vstupe, až kým nenájdeme hľadanú informáciu. Vstup si budeme pamätať ako \(n\) prvkové dvojrozmerné pole ziaci[n+1][2], kde sa na \(i\)-tej pozícii nachádza \(i\)-ta dvojica zo vstupu.

Keď budeme hľadať predchodcu čísla \(k\), postupne prejdeme celé pole ziaci[][], až kým sa prvok ziaci[i][1] nebude rovnať \(k\). Potom vieme, že v rade stojí za žiakom \(k\) žiak s číslom ziaci[i][0].

Nakoľko budeme \(n-1\) krát prechádzať \(n-1\) prvkov poľa, náš algoritmus spraví rádovo \((n-1)^2\) operácií, čo je zhruba \(n^2\). Povedané vznešenejšie, náš algoritmus má časovú zložitosť \(O(n^2)\). Keďže používame iba dve \(n\) prvkové polia, pamäťová zložitosť bude \(O(n)\).

#include <iostream>

using namespace std;

int main() {
    int n, x, y, k, z;
    cin >> n;
    int ziaci[n+1][2], videni[n+1];

    for (int i = 1; i <= n; ++i) videni[i] = 0;

    for (int i = 0; i < n-1; ++i) {
        cin >> x >> y;
        ziaci[i][0] = x;
        ziaci[i][1] = y;
        videni[x] = 1;
    }

    for (int i = 1; i <= n; ++i) {
        if (videni[i] == 0) {
            k = i; break;
        }
    }

    cout << k << endl;

    for (int i = 0; i < n-1; ++i) {
        //vyhladavame nasledovnika k
        for (int j = 0; j < n-1; ++j) {
            if (ziaci[j][1] == k) {
                z = ziaci[j][0];
                break;
            }
        }
        //nasli sme ho, vypiseme ho a stava sa novym k
        cout << z << endl;
        k = z;
    }
}

Vzorové riešenie

Čo ak by sme si vstup pamätali trochu prefíkanejšie? Vytvorme \(n\) (alebo \(n+1\)) prvkové pole ziaci[n+1], kde na \(i\)-tej pozícii bude číslo žiaka, ktorý stál v rade za žiakom \(i\). Ak potom budeme chcieť v našom algoritme nájsť ďaľšieho v poradí po \(k\), stačí sa pozrieť na pozíciu ziaci[k].

Informácia zo vstupu v tvare x y nám hovorí, že pred tanečníkom \(x\) sa nachádza tanečník \(y\). To ale inak povedané znamená, že za tanečníkom \(y\) sa nachádza tanečník \(x\). A to je práve tá informácia o predchodcovi, ktorú sme hľadali. Do nášho poľa si preto poznačíme ziaci[y] = x. Opäť si dajte pozor na indexovanie.

Nájdenie nasledovníka nám teraz zaberie iba konštantný čas \(O(1)\), pretože sa stačí pozrieť na jeden prvok poľa. Tento proces budeme opakovať \(n-1\) krát, preto časová zložitosť optimálneho riešenia je \(O(n)\). Pamäťová zložitosť sa oproti pomalšiemu riešeniu nezmenila, nakoľko stále používame iba 2 polia dlhé \(n\), a je stále \(O(n)\).

#include <iostream>

using namespace std;

int main() {
    int n, x, y, k, z;
    cin >> n;
    int ziaci[n+1], videni[n+1];

    for (int i = 1; i <= n; ++i) videni[i] = 0;

    for (int i = 0; i < n-1; ++i) {
        int x, y; cin >> x >> y;
        videni[x] = 1;
        ziaci[y] = x;
    }

    for (int i = 1; i <= n; ++i) {
        if (videni[i] == 0) {
            k = i;
            break;
        }
    }

    cout << k << endl;
    for (int i = 0; i < n-1; ++i) {
        z = ziaci[k];
        cout << z << endl;
        k = z;
    }
}

n = int(input())

ziaci = [0] * (n+1)
videni = [0] * (n+1)

for i in range(n-1):
    x,y = [int(x) for x in input().split()]
    videni[x] = 1
    ziaci[y] = x

k = 0
for i in range(1,n+1):
    if videni[i] == 0:
        k = i
        break

print(k)
for i in range(n-1):
    k = ziaci[k]
    print(k)