Zadanie

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Paulínke na psmolarova@gmail.com

Plukovník Abaž očakáva návštevu svojho brata Žabu, a tak sa pre neho rozhodol spraviť veľkolepú vojenskú prehliadku. Všetkých svojich vojakov nechá nastúpiť do radu, aby Žaba videl, aká tvrdá disciplína uňho panuje.

Lenže, usporiadať prehliadku nie je také jednoduché, ako by sa mohlo zdať. Ak by sa dopredu postavil nejaký mamľas, mohol by úplne pokaziť obraz o celom Abažovom pluku. A to Abaž rozhodne nehodlá riskovať.

Našťastie, predvčerom mali vojaci vo svojich kasárňach priateľské majstrovstvá v pretláčaní. Takéto zápasy v pretláčani majú veľmi radi, lebo sa nikdy nestane, že by slabší vojak pretlačil silnejšieho. Na záver takýchto majstrovstiev sa preto vedia vojaci vždy jednoznačne zoradiť od najsilnejšieho po najslabšieho vojaka.

Lenže Abaž velí vojakom z dvoch kasární – južnej a severnej. A tak teraz stojí pred dvoma zástupmi vojakov. Jeden tvoria vojaci severnej kasárne zoradení od najsilnejšieho po najslabšieho a druhí tvoria vojaci vojaci južnej kasárne, taktiež v poradí od najsilnejšieho po najslabšieho.

Rád by z nich spravil jeden rad, v ktorom by boli všetci vojaci oboch kasární a tiež by boli usporiadaný od najsilnejšieho po najslabšieho. Jediné čo mu v tom vie pomôcť je to, že usporiada zápas medzi ľubovoľnými dvoma vojakmi. Takýto zápas však chvíľu trvá a keďže do príchodu Žabu už neostáva veľa času, potrebuje týchto zápasov spraviť čo najmenej.

Úloha

Ku každej z piatich podúloh napíšte slovný popis, v ktorom uvediete ako ste danú podúlohu riešili a dokážete, že vaše riešenie je správne. Nazabudnite na odhady počtu zápasov, ktoré musí Abaž vyhlásiť.

  1. (1 bod) Abaž svojho brata dobre pozná a vie, že sa aj tak ďalej ako na začiatok radu nepozrie. Preto by chcel zistiť, ktorý z jeho vojakov je najsilnejší, aby ho mohol postaviť na začiatok. Na koľko najmenej zápasov to vie Abaž zistiť?

  2. (2 body) Podceňovať Žabu sa však neoplatí. Čo ak sa pozrie nie len na prvého, ale na prvých troch vojakov? Akým spôsobom môže Abaž zistiť, ktorí traja vojaci z jeho pluku sú najsilnejší? Na koľko zápasov to vie dosiahnuť? A ak sa pozrieme na rady severnej a južnej kasárne (predpokladajme, že v každom je práve 10 vojakov), ktorí vojaci sú vôbec rozumní kandidáti na troch najsilnejších vojakov?

  3. (4 body) Z centrály prišla informácia, že okrem Žabu príde na návštevu aj generálka Katka, ktorá je známa tým, že si poriadne vyobzerá všetkých vojakov. Abaž ich preto musí zoradiť všetkých od najsilnejšieho po najslabšieho.

    Predpokladajte, že v severnom aj južnom zástupe je 16 vojakov. Popíšte spôsob, akým má Abaž vyhlasovať súboje, aby sa mu podarilo usporiadať podľa sily všetkých vojakov. Koľko zápasov bude musieť spraviť v najhoršom prípade? Aký by bol počet zápasov, ak by v každom rade bolo \(n\) vojakov?

  4. (3 body) Čo by sa stalo, ak by mal Abaž na starosti štyri kasárne, každú s 8 vojakmi, ktorí sú usporiadaní do štyroch zástupov od najsilnejšieho po najslabšieho? Akým spôsobom by mal usporadúvať zápasy, aby ich spravil čo najmenej a usporiadal všetkých vojakov podľa sily? Pokúste sa pri tom využiť riešenie podúlohy c). Vyskúšajte viacero možností, aby ste našli tú s najmenším počtom súbojov.

  5. (5 bodov) Nanešťastie, vojakom sa podarilo zabudnúť ako dopadli v kasárňových majstrovstvách. Abaž má preto pred sebou 32 vojakov, o ktorých sile netuší vôbec nič. A jediné čo vie robiť je nechať zápasiť ľubovoľných dvoch vojakov. Ako má postupovať pri ich zoraďovaní? Koľko zápasov bude musieť vyhlásiť v najhoršom prípade? A koľko zápasov by potreboval, ak by bolo vojakov \(n\)?

    Riešenie za 5 bodov by pre 32 vojakov nemalo potrebovať viac ako 160 zápasov ani v najhoršom prípade.

Podúloha a)

Jeden zo spôsobov, ako túto úlohu riešiť je skúšanie všetkých možností. Ako spoznáme najsilnejšieho vojaka? Najsilnejší bude predsa ten, ktorý vyhrá nad každým iným vojakom. Môžeme teda usporiadať zápas medzi každou dvojicou vojakov, čím vyhlásime \(\frac{n(n-1)}{2}\) zápasov a potom nájsť toho vojaka, ktorý nebol ani raz porazený.

Takéto riešenie však vôbec nevyužíva informáciu, že vojaci už nejak zoradení sú!

Ak vyberieme niektorého vojaka, potom vieme, že všetci vojaci, ktorí stoja v rade pred ním sú silnejší a všetci, ktorí stoja za ním sú slabší. Keď sa preto chceme o nejakom vojakovi rozhodnúť, či je najsilnejší, najskôr sa pozrieme, či pred ním nestoja nejaký vojaci. Ak áno, znamená to, že títo vojaci sú od neho silnejší a daného vojaka nemusíme ani uvažovať ako možného kandidáta.

Ktorí vojaci potom pripadajú do úvahy? Všetci vojaci, okrem prvých v oboch radoch, majú niekoho pred sebou. To znamená, že iba prví vojak z každého radu je relevantný kandidát. Pomocou jedného zápasu potom vieme ľahko zistiť, ktorí z nich je skutočne najsilnejší zo všetkých.

Stačí nám teda iba jediný zápas.

Podúloha b)

Pozrime sa na riešenie predchádzajúcej úlohy. Kandidát na najsilnejšieho vojaka bol ten, pred ktorým nestál žiaden iný vojak. To však dáva zmysel, ak v rade pred nejakým vojakov stojí \(k\) iných vojakov, je jasné, že tento vojak nemôže skončiť lepšie ako \(k+1\)-vý najsilnejší. Ak teda chceme nájsť troch najsilnejších vojakov, stačí nám uvažovať prvých troch vojakov v každom rade.

My však týchto troch vojakov potrebujeme aj zoradiť podľa sily. Vďaka podúlohe a) už vieme, ako nájsť najsilnejšieho vojaka. Usporiadajme teda zápas medzi prvými vojakmi a víťaza pošlime bokom. Čo sa zmenilo? Ako zistíme, ktorý vojak je celkovo druhý najsilnejší?

Uvedomme si, že ak sme najsilnejšieho vojaka poslali bokom, tak druhý najsilnejší vojak celkovo je teraz najsilnejší z tých, ktorí nám zostali. A ich relatívna sila v rade sa nijak nemenila. Môžeme preto použiť rovnaký princíp ako predtým. Z každého radu si zoberieme prvého (najsilnejšieho) vojaka, ktorý tam ostal (jeden z radov je o jedného vojaka kratší). Medzi nimi usporiadame zápas a víťaza vyhlásime za druhého najsilnejšieho a pošleme ho nabok.

Pre zistenie tretieho najsilnejšieho vojaka spravíme to isté. Opäť predsa platí, že zo zvyšných vojakov bude on ten najsilnejší. No a jediní kandidáti na najsilnejších vojakov sú tí, ktorí stoja na začiatku radov. Stačí nám preto porovnať týchto dvoch kandidátov.

Na obrázku nižšie si môžete pozrieť ako vyzerá druhý zápas v závislosti od toho, či je najsilnejší vojak červený alebo čierny:

Pomocou troch zápasov preto vieme určiť troch najsilnejších vojakov.

Podúloha c)

Určite vám neuniklo, že pri výbere troch najsilnejších vojakov sme postupovali zakaždým rovnako. A táto podúloha nie je nič iné ako rozšírenie tejto myšlienky pre všetkých vojakov.

Kľúčové pozorovanie je, že ak sa nám podarilo nájsť \(k\) najsilnejších vojakov, tak \(k+1\) je vlastne najsilnejší z ešte nevybraných vojakov. A hľadanie najsilnejšieho vojaka sme vyriešili v podúlohe a). Stačilo porovnať vojakov na začiatku radov a zobrať víťaza. A napriek tomu, že sa naše rady postupne skracujú, stále platí, že vojak, ktorý má pred sebou v rade iného nevybraného vojaka nemôže byť najsilnejší.

Riešenie tejto podúlohy je preto pomerne priamočiare. Budeme opakovať nasledovnú operáciu: z každého radu vyber prvého (najsilnejšieho), ešte nezaradeného, vojaka. Medzi týmito dvoma vojakmi sprav súboj, víťaza zaraď ako ďalšieho v poradí a porazeného vráť späť do jeho radu.

Jediný problém môže nastať, ak sa nám “minú” vojaci v jednom rade. To však vôbec nevadí. V takom prípade môže byť najsilnejší zo zvyšných vojakov už len jediný vojak – prvý v ostávajúcom rade. Nepotrebujeme preto ani ďalšie zápasy, aby sme ho úspešne vybrali a zaradili do výslednej postupnosti.

Koľko zápasov budeme potrebovať ak máme dva rady po 16 vojakov? Ak by sme mali šťastie, tak po 16 súbojoch sa nám minie celý jeden rad a zvyšok už vieme vyriešiť bez dodatočných súbojov. Pri odhadovaní toho, ako dobré je naše riešenie sa však oplatí počítať s tým, že šťastie nemáme, ba priam máme tú najväčšiu smolu. V takom prípade musíme usporiadať súboj až 31 krát. Po 31 súbojoch totiž ostáva posledný vojak a je jasné, že to je ten najslabší zo všetkých a už ho len zaradíme na koniec.

No a v prípade, že je v každom rade \(n\) vojakov, budeme potrebovať \(2n-1\) zápasov. To môže nastať napríklad vtedy, ak sú najsilnejší vojaci rozmiestnený v radoch na striedačku. Teda najsilnejší je v prvom rade, druhý najsilnejší v druhom, tretí opäť v prvom, štvrtý v druhom rade atď..

Podúloha d)

S radou, že si máme pomôcť podúlohou c), sa pustíme do riešenia.

Teraz sa nám počet radov zdvojnásobil. Mohli by sme však použiť rovnakú myšlienku, v ktorej sme sa snažili vždy nájsť najsilnejšieho vojaka, z tých, ktorých sme ešte nezaradili. Teraz však nemáme len dvoch kandidátov, ale štyroch. Medzi týmito štyrmi vojakmi by sme mohli usporiadať “pavúkový” turnaj, vďaka ktorému by sme našli najsilnejšieho z nich na tri zápasy. Dokopy by sme preto potrebovali \(31\cdot 3 = 93\) zápasov1.

Ide to však aj lepšie. Pre aké podmienky vieme úlohu riešiť?

Úlohu vieme riešiť, keď máme dva usporiadané rady vojakov. Výsledkom je vtedy usporiadaný rad vojakov a na jeho usporiadanie sme potrebovali \(k-1\) zápasov, kde \(k\) je počet vojakov v oboch spájaných radoch.

Môžeme preto úlohu riešiť postupne. Najskôr zoberieme ľubovoľné dva rady a spojíme ich dokopy. K tomuto radu (ktorý je utriedený) potom pripojíme tretí rad a nakoniec aj štvrtý. Pri prvom spájaní potrebujeme spraviť 15 zápasov – spájame rady veľkosti 8. Pri druhom spájame už rad veľkosti 16 s radom veľkosti 8, takže budeme potrebovať 23 zápasov. A nakoniec spájame rad veľkosti 24 s radom veľkosť 8, čo nám zaberie 31 súbojov. Dokopy potrebujeme 69 zápasov.

V tomto riešení však zakaždým pracujeme s postupne a pomaly rastúcim radom. To napríklad spôsobuje, že prvé dva rady sa spájajú až trikrát. Spravíme to preto inak. Naše štyri rady si rozdelíme do dvojíc a tieto dvojice spojíme. To nás stojí 30 zápasov (15 za každé spojenie). Dostali sme dva utriedené rady, každý so 16 vojakmi, ktoré vieme spojiť na 31 súbojov. Dokopy je to 61 zápasov, čo je už naozaj optimálne riešenie.

Podúloha e)

V tejto podúlohe už nemáme žiadne rady, iba veľa vojakov, ktorých potrebujeme zoradiť podľa sily. Niečo také nevieme riešiť, jediné čo zvládame je zobrať dva rady vojakov, ktoré už zoradené sú a na \(n-1\) súbojov z nich spraviť spoločný zoradený rad.

Predstavme si preto na chvíľu, že by sme tieto dva usporiadané rady mali. Potom je úloha jednoduchá. Ako ich však vytvoríme? Rozdeľme si vojakov na dve polovice, je úplne jedno akým spôsobom. Z oboch týchto polovíc potrebujeme vytvoriť usporiadaný rad, a tieto dva rady potom spojiť dokopy. To je však tá istá úloha ako sme mali pred tým, akurát teraz už nechceme spraviť usporiadaný raz z \(n\) vojakov, ale dva usporiadané rady, každý s \(\frac{n}{2}\) vojakmi.

Vieme túto myšlienku posunúť ešte o úroveň ďalej? Ak by sme mali dva usporiadané rady dĺžky \(\frac{n}{4}\) tak ich spojením vieme vytvoriť usporiadaný rad dĺžky \(\frac{n}{2}\), takže v podstate potrebujeme 4 usporiadané rady dĺžky \(\frac{n}{4}\).

No a pôjdeme ďalej a ďalej, budeme chcieť stále viac stále menších radov. Až prídeme k situácii, keď budeme potrebovať \(n\) usporiadaných radov dĺžky \(1\). Ale to sú predsa jednotliví vojaci a keďže sú v rade sami, tak tento rad je usporiadaný.

V tomto momente sa môžeme začať vracať spať používajúc podúlohu c) (a celé sa to nápadne podobá podúlohe d)). Zakaždým si zoberieme dvoch vojakov, spravíme medzi nimi súboj a vytvoríme tak usporiadaný rad dĺžky 2. Tieto rady dĺžky dva potom po dvojiciach spájame, čím vytvoríme usporiadané rady dĺžky 4. No a rovnako budeme postupovať, až kým nám neostanú 2 usporiadané rady dĺžky \(\frac{n}{2}\), ktoré spojíme dokopy, čím získame výsledok.

Náš postup si vieme zapísať aj nasledovným pseudoprogramom:

"Zoraď" m vojakov:

    ak je m rovné 1:
        tento vojak je zoradený, ďalej nič nerobím
    prvý rad = "Zoraď" m/2 vojakov
    druhý rad = "Zoraď" zvyšných m - m/2 vojakov
    výsledný rad = zatiaľ je prázdny
    kým sú v prvom aj druhom rade vojaci:
        ak zápas medzi prvým z prvého radu a prvým z druhého radu vyhral prvý:
            prvý vojak z prvého radu sa zaradí na koniec výsledného radu
        inak:
            prvý vojak z druhého radu sa zaradí na koniec výsledného radu
    ak sú vojaci iba v prvom rade:
        prvý rad sa pripojí na koniec výsledného radu
    ak sú vojaci iba v druhom rade:
        druhý rad sa pripojí na koniec výsledného radu
    výsledný rad tvorí m zoradených vojakov

Všimnite si, ako sa v tejto akoby funkcii “Zoraď” volá tá istá funkcia na menšie množstvo vojakov. To je presne preto, lebo chceme robiť tú istú vec dookola akurát s menším množstvom vojakov. Skúste si napríklad odsimulovať, akoby takýto výpočet prebiehal. Tento princíp sa naviac volá rekurzia, v programovaní je nesmierne dôležitý a viac si o ňom môžete prečítať napríklad tu: Zborník PRASKu strana 11.

Na nasledujúcom obrázku si môžete pozrieť ako by vyzeral priebeh tohto algoritmu s 8 vojakmi. Číslo vo vnútri farebnej guličky určuje silu daného vojaka. Na spodnom riadku sú vojaci samostatne, teda v usporiadaných radoch dĺžky 1 a postupne sa spájajú do dlhších a dlhších radov.

Posledná otázka je, koľko otázok použijeme na usporiadanie tohto počtu vojakov. Všimnime si, že počas algoritmu máme niekoľko úrovní. Na najspodnejšej sú rady dĺžky 1, na ďalšej rady dĺžky 2, potom 4 atď.. Na každej ďalšej úrovni sa dĺžka radu zdvojnásobí. Ak teda potrebujeme usporiadať dvakrát viac vojakov, budeme potrebovať iba o jednu úroveň viac. A možno sa to nezdá, týchto úrovní je naozaj málo. Ak by sme chceli usporiadať napríklad \(1\,000\,000\) vojakov, tak nám stačí iba 20 úrovní.

Matematicky povedané, týchto úrovní bude logaritmicky veľa. Ak niekde uvidíte napísané \(\log_x y\), tak to musíte prečítať: Koľkokrát musím vynásobiť 1 číslom \(x\) aby som dostal aspoň \(y\)? A to je presne to čo potrebujeme – koľkrát musíme vynásobiť 1 číslom 2 aby som dostal aspoň číslo \(n\).

Ostáva nám určiť, koľko zápasov sa udeje na každej úrovni. Vypočítať to presne by mohol byť problém, ale my si to zaokrúhlime nahor, čím určite nič nepokazíme. Na každej úrovni sa spraví najviac \(n\) súbojov. To môžeme vidieť napríklad z toho, že vždy keď spravíme nejaký súboj, tak výherca sa posunie o úroveň vyššie.

Celkový počet súbojov potrebný na utriedenie \(n\) vojakov je preto najviac \(n \log_2 n\). Mimochodom, tento algoritmus sa volá aj triedenie spájaním alebo mergesort. Je to jeden z najznámejších a najrýchlejších triediacich algoritmov.


  1. Vlastne o niečo menej, keďže rady sa nám budú postupne míňať. V najhoršom prípade potrebujeme len 90 zápasov

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

  • Eliška Macáková

    8. december 2016 19:34

    Tento priklad sa mi velmi pacil :) bola by som rada, keby sa vyskytlo v dalsej serii pokracovanie.

    • Michal Anderle

      8. december 2016 23:35

      To sme velmi radi :) Ak si ches (a hocikto iny) skusit tento algoritmus implementovat, mozes to vyskusat na tejto ulohe: https://testovac.ksp.sk/tasks/ls14-utried2/ Aspon sa ti automaticky overi spravnost programu :)