3. Andrej triedi ovocie vzorové riešenie

5
8
10 20 30 40 50 60 60 80
1 0 1 1 0 0 1 0
5
39 25 77 91 95
1 0 0 1 1
3
5 71 57
0 0 0
6
0 1 1 2 3 5
1 1 1 1 1 1
4
22 11 113 50
1 0 0 1

Ano
Ano
Nie
Ano
Ano

Jednoduché prípady

Ak máme ovocie na vstupe už zoradené podľa kvality, tak nemusíme nič riešiť a vieme nezávisiac od typov ovocí proste odpovedať Ano (už sme v usporiadanom stave, čiže aj s 0 výmenami sa vieme dostať do usporiadaného stavu).
Ak by sme mali iba ovocie jedného typu, tak vieme odpovedať Ano iba vtedy, ak už je usporiadané podľa kvality a v každom inom prípade Nie. Je to tak preto, lebo ak máme iba ovocie jedného typu, nedokážeme vymeniť žiadnu dvojicu ovocí. Čiže ak nie je usporiadané podľa kvality na začiatku, tak s ním nevieme nič spraviť.

Ostatné prípady

Zostávajú nám prípady, kedy máme ovocia rôznych typov a nie sú usporiadané podľa kvality. Verte či neverte, ale v každom takom prípade vieme odpovedať Ano. Teraz si ale musíme aj zdôvodniť, prečo to tak naozaj je.

Jedno iné ovocie

Ak by sme mali skoro všetky ovocia typu 0 a presne jedno ovocie typu 1 (alebo naopak), tak určite vieme nejakými výmenami usporiadať celý rad ovocí typu 0 podľa kvality. Na to si úplne vystačíme s jedným ovocím druhého typu.
Postup ktorým to vieme dosiahnuť môže byť napr. takýto:

1. Ak ovocie typu 1 nie je prvým ovocím v rade, tak ho vymeníme s prvým ovocím v rade.
2. Ovocie typu 1 vymeníme s ovocím typu 0, ktoré má spomedzi všetkých ovocí typu 0 najnižšiu kvalitu.
3. Opakujeme kroky 1 a 2 s postupne sa zvyšujúcou pozíciou ovocia typu 1 v rade (začali sme s 0, teraz budeme s 1, potom s 2, …).

Teraz sme skončili s usporiadaným radom ovocí typu 0 a jedným ovocím typu 1 na konci. Ešte ale potrebujeme dostať ovocie typu 1 na správnu pozíciu. To dosiahneme tak, že ho postupne budeme vymienať s ovocím typu 0, ktoré je v rade hneď pred ním, až kým sa nedostane tam kam patrí.

Takže rad s jedným ovocím iného typu vieme vždy usporiadať podľa kvality.

Viac ovocí iného typu

Ak by sme mali viac ovocí iného typu, tak vieme postupovať veľmi podobne ako v predchádzajúcom prípade. Začneme s tým, že si s pomocou jedného z ovocí typu 1 usporiadame všetky ovocia typu 0 podľa kvality na začiatok našeho radu. Následne použijeme posledné ovocie typu 0 z už usporiadaného radu ako pomocné ovocie, ktorým budeme vymieňať ovocia typu 1 na správne pozície. Ako posledný krok vrátime pomocné ovocie na jeho pôvodnú pozíciu, podobne ako v predchádzajúcom prípade.

Teraz sme sa ocitli v stave, kedy máme usporiadané všetky ovocia typu 0 na začiatku radu a všetky ovocia typu 1 za nimi. Čo ale teraz potrebujeme urobiť je, premiešať ich navzájom tak, aby zostali usporiadané podľa kvality. To urobíme v podstate rovnako ako v predchádzajúcom prípade, ale namiesto jedného ovocia typu 1 budeme postupne presúvať všetky ovocia typu 1 na správne pozície.

Takže aj rad s viacerými ovociami iného typu vieme vždy usporiadať podľa kvality.

Typy ovocia ktoré boli použité v tejto časti sú vymeniteľné, nezáleží na tom či budeme mať na začiatku typ 0 a na konci typ 1 alebo naopak.

Zhrnutie

Keď sa pozrieme na to čo sme si práve povedali, môžeme si všimnúť, že jediný prípad s výstupom Nie nastane vtedy, ak máme ovocie rovnakého typu a nie je usporiadané. V každom inom prípade vieme odpovedať Ano.

Implementácia

Implementácia bude opísaná v jazyku Python, ale dá sa veľmi ľahko aplikovať aj na C++.

Začnime časťou kódu, ktorá sa postará o načítanie vstupu. Tým, že sa v tejto úlohe jeden vstup skladá z viacerých testov sa zatiaľ nebudeme trápiť.

n = int(input())

a = list(map(int, input().split()))
b = set(map(int, input().split()))

Tu si môžeme všimnúť, že prvky v polliach a a b sme načítali trošku odlišne. Zatiaľ čo prvky v poli a sme načítali ako štruktúru list, prvky v poli b sme načítali ako štruktúru set. Dôvodom prečo sme to tak urobili je, že pre a nám záleží na presnom poradí hodnôt \(a_i\) na vstupe, zatiaľ čo pri b nám záleží iba na tom, či sa objavili oba typy ovocia alebo iba jeden.

set je štruktúra, ktorá uchováva iba rôzne hodnoty. Ak by sme sa pokúsili dosetu pridať hodnotu, ktorá sa v ňom už nachádza, tak sa nič nestane.

Teraz môžme pridať jednoduchú kontrolu, či sa v poli b nachádzajú oba typy ovocia.

if len(b) == 2:
    print("Ano")
else:
    ...

Zostáva nám overiť tú zložitejšiu vec, a to či je rad ovocia usporiadaný podľa kvality. To vieme urobiť tak, že budeme postupne prechádzať radom kvalít a budeme si pamätať predchádzajúcu hodnotu. Ak sa nám stane, že aktuálna hodnota je menšia ako predchádzajúca, tak vieme, že rad nie je usporiadaný a môžme odpovedať Nie.

if len(b) == 2:
    print("Ano")
else:
    pred = a[0]
    for i in range(1, n):  # index 0 sme už spracovali, takže začíname od 1
        if a[i] < pred:
            print("Nie")
            break
        pred = a[i]
    else:
        print("Ano")

A toto je celá implementácia hotová!

Finálny kód, ktorý berie do úvahy aj viacero testov na vstupe vyzerá takto:

t = int(input())

for _ in range(t):
    n = int(input())

    a = list(map(int, input().split()))
    b = set(map(int, input().split()))

    if len(b) == 2:
        print("Ano")
    else:
        pred = a[0]
        for i in range(1, n):
            if a[i] < pred:
                print("Nie")
                break
            pred = a[i]
        else:
            print("Ano")

Implementácia v C++

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t, n;
    cin >> t;

    for(int i = 0; i < t; i++) {
        cin >> n;

        int lastA = 0, is_sorted = true;
        cin >> lastA;
        for(int j = 1; j < n; j++) {
            int a;
            cin >> a;
            if(a < lastA) {
                is_sorted = false;
                // Nemôžeme použiť break, lebo by sme nenačítali hodnoty zostávajúce na vstupe
            }
            lastA = a;
        }

        int bhas0 = false, bhas1 = false;
        for(int j = 0; j < n; j++) {
            int b;
            cin >> b;
            if(b == 0) bhas0 = true;
            if(b == 1) bhas1 = true;
        }

        // Ano je buď ak sme videli typ 0 aj 1 alebo ak je rad usporiadaný
        if((bhas0 && bhas1) || is_sorted) {
            cout << "Ano\n";
        } else {
            cout << "Nie\n";
        }
    }
}

Časová a pamäťová zložitosť

Časová zložitosť pre jeden test je \(O(n)\), kde \(n\) je počet ovocí v rade, keďže pri najdlhšom overovaní budeme musieť raz prejsť celý rad.

Najlepšia dosiahnuteľná pamäťová zložitosť je \(O(1)\), keďže pri prechádzaní radu a nám stačí si pamätať predchádzajúcu hodnotu a hodnotu na aktuálnej pozícii. Pri prechádzaní radu b nám stačí pamätať si iba to, či sme v ňom videli jednotlivé typy ovocia. Dokopy je to teda konštantne veľa pamäte.

Je treba poznamenať, že v Python kóde ukázanom vyššie si pamätáme naraz celý rad a a b. Takže v tejto implementácii je pamäťová zložitosť \(O(n)\). V Pythone je o niečo komplikovanejšie čítať zo vstupu medzerami oddelené hodnoty postupne.

Finálnu časovú zložitosť ale ešte musíme prenásobiť počtom testov, čo nám dáva celkovú časovú zložitosť \(O(t \cdot n)\), kde \(t\) je počet testov.
Pamäťovú zložitosť takto upravovať nepotrebujeme a tedá je stále \(O(1)\).