Druhá série začátečnické kategorie třicátého pátého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
35-Z2-1 Párty (Zadání)
Celou situaci můžeme jednoduše simulovat: U každého kamaráda si budeme pamatovat, jestli už je na párty. Dále si budeme udržovat potvrzený počet kamarádů na párty. Poté budeme procházet všechny kamarády, co ještě nejsou na párty, a když už je pro daného kamaráda dost přítomných lidí, tak si ho označíme jako účastníka a zvýšíme počítadlo. Toto procházení všech kamarádů budeme opakovat pořád dokola.
Když projdeme všechny kamarády, aniž bychom alespoň jednoho z nich přidali, tak víme, že ani v dalších průchodech nikoho nepřidáme, protože průchod bude probíhat úplně stejně. Tedy v ten moment můžeme algoritmus zastavit a odpovědět, jaký je celkový počet lidí na párty.
Popsané řešení až (N+1)-krát opakuje procházení, protože vždy přibude na párty alespoň jeden účastník. Na každém průchodu stráví O(N) času. Celková časová složitost je tedy O(N2). Když kamarádi budou vyžadovat postupně (N-1) až 0 účastníků, tak skutečně každým průchodem přidáme jen jednoho kamaráda, tedy složitost algoritmu nelze odhadnout lépe.
Pojďme tedy řešení zrychlit. Seznam kamarádů si setřídíme podle požadovaného počtu účastníků párty. Tím se odpověď nezmění. Nahlédneme, že když na setříděný seznam spustíme předešlý algoritmus, tak bude stačit jen jeden průchod. Podíváme se na prvního kamaráda, který po prvním průchodu nebude na párty. Každý další kamarád také na párty nedorazí, protože vyžaduje alespoň stejný počet účastníků, ovšem ten se už nezvýší. Při druhém průchodu se také nic nezmění. Již účastnící se kamarády přeskočíme a u ostatních budeme porovnávat se stejným počtem potvrzených účastníků jako při prvním průchodu.
Implementaci lze ještě trošku zjednodušit jedním pozorováním. Dokud procházíme kamarády, kteří dorazí, tak počet potvrzených účastníků se rovná indexu aktuálně posuzovaného kamaráda (když indexujeme od 0). Hledáme tedy index prvního kamaráda, jehož index je menší než jeho požadovaný počet účastníků.
Časová složitost algoritmu je za použití třídění sléváním O(N log N). Pomocí count sortu by šla složitost zlepšit na O(N), stačí si jen všimnout, že kamarádi vyžadující více než N účastníků nikdy nemůžou dorazit, a tedy je můžeme rovnou ignorovat.
Program s přihrádkovým tříděním (Python 3)
35-Z2-2 Železnice (Zadání)
Představme si, že budujeme železnici z Xaverova do Yndyanapolis. Pro každé políčko si budeme počítat, kolik nejméně stojí vybudování železnice z Xaverova na toto políčko.
Z Xaverova může železnice jít na políčka do 4 směrů. Na těchto sousedních políčkách můžeme jít zase do 4 směrů a cestou si udržovat nejmenší cenu.
Problém s tímhle přístupem je, že budeme chodit neustále sem a tam a vlastně nikdy neskončíme.
Povšimněte si, že nedává smysl počítat znovu cenu pro všechny sousedy, když se cena železnice do aktuálního políčka nezmenšila. Spočítali bychom vlastně znova ceny, které už máme. Raději použijeme myšlenku prohledávání do šířky.
Pořídíme si frontu, do které budeme vkládat políčka, ze kterých máme zkoušet stavět železnici. Dokud nebude fronta prázdná, vybereme políčko z fronty a zkusíme postavit železnici do všech 4 směrů. Spočítáme cenu postavení železnice do každého z těchto sousedních políček. To bude cena postavení železnice do aktuálního políčka, ke které přičteme 1 nebo K podle toho, jestli je na sousedním políčku louka či hora.
Pokud se zmenšila cena do nějakého směru, přidáme daného souseda do fronty a zapamatujeme si pro něj lepší cenu.
Zrychlení
Představme si situaci, kdy zlevnění políčka zmenší cenu jeho sousedního políčka, to změní cenu jeho sousedů a tak dále. V nejhorším případě zjistíme, že jsme se hned na začátku vydali špatným směrem, a budeme muset vše přepočítat. Tento problém se vyřeší využitím prioritní fronty. Prioritní fronta udržuje „na vrchu“ prvek s nejmenší nebo největší prioritou. My využijeme tu s nejmenší prioritou. Prioritní fronta se dá imlementovat pomocí haldy. Jako prioritu využijeme cenu postavení železnice do daného políčka. Myšlenka je taková, že už od startu si chceme počítat pro každé políčko jenom nejmenší cenu železnice. Výhodou tohoto řešení je, že každé políčko navštívíme pouze jednou. Tento algoritmus se jmenuje Dijkstrův algoritmus.Připravíme si prioritní frontu a přidáme do ní Xaverov s cenou 0. Vytáhneme prvek z vrchu fronty, a pokud jsme dané políčko ještě nezpracovali, pro všechny 4 sousedy spočítáme ceny postavení železnice a přidáme je do fronty. Toto opakujeme, dokud se nevyprázdní fronta. Důležité je zmínit, že musíme navíc kontrolovat, že krokem do směru nevyskočíme z naší mapy, např. stojíme-li u pravého kraje, nemůžeme udělat krok doprava. Nakonec stačí vypsat cenu postavení železnice na políčku Yndyanapolis.
Časová složitost je O(RS log(RS)), protože operace s prioritní frontou (haldou) trvají O(log(RS)) a na každé políčko (až na start) šáhneme nejvýše 4-krát: Jedenkrát z každého souseda.
35-Z2-3 Mince (Zadání)
Existuje více způsobů jak úlohu řešit, ukážeme jeden z nich. Nejdříve si spočítáme počet panen P=N-O. Pro jednoduchost budeme předpokládat, že O ≥ P, pokud tomu tak nebude, stačí symboly prohodit. Výstup si předpřipravíme tak, že začneme jedním orlem, a poté budeme střídavě přidávat jednu pannu a jednoho orla, dokud nám nedojdou panny. Pokud nám ještě zbývají orli, nejdříve vypíšeme jednoho na konec a poté přerozdělíme zbývající orly mezi už existující skupinky orlů. Pokud je už ve všech skupinkách K-1 orlů a potřebujeme přidat dalšího, úloha nemá řešení – všechny skupinky orlů jsou plné a jsou od sebe oddělené jednou pannou, proto jich nejde vytvořit více.
Pracovat přímo s textovým řetězcem by však bylo pomalé, protože při přidání znaku doprostřed se musí část řetězce za tímto znakem posunout. Místo toho si vytvoříme pole, ve kterém si budeme pamatovat délky skupinek orlů.
Každý hod do posloupnosti přidáváme právě jednou. Jedno přidání zvládneme v konstantním čase, jenom přičteme jedničku a posuneme se na další pozici v poli. Tuto část zvládneme v čase O(N). Nakonec musíme výstup podle hodnot v poli vypsat, což bude také v čase O(N).
Pro inspiraci uvedeme ještě alternativní řešení. To vždy vypíše K-1 těch symbolů, kterých zbývá vypsat více, a jeden symbol, kterého zbývá vypsat méně. Kterého symbolu zbývá více a méně se mezi iteracemi mění, ale je potřeba, aby se panny a orlové pořád pravidelně střídali – nesmí se stát, abychom v jedné iteraci vypsali nejdříve orly a pak panny a v další naopak. Nakonec, když zbývá obou symbolů méně než K, prostě vypíšeme všechny zbývající. Musíme začít početnějším symbolem, protože v některých případech (např. K=2 a O=P+1) můžeme potřebovat vypsat početnější symbol na začátku i na konci.
Alternativní řešení (Python 3)
35-Z2-4 Supervěž (Zadání)
Našim cieľom je nájsť také voľné políčko, ktoré má vo svojom riadku a stĺpci najväčší možný počet figuriek.
Bruteforce riešenie
Najskôr si zo vstupu načítame šachovnicu do tabuľky N×N. Potom ju budeme postupne prechádzať po políčkach. Pre každé voľné políčko zistíme počet figuriek v jeho riadku a stĺpci, jednoducho tak, že si oba celé prejdeme. Potom počet figuriek, ktoré z daného políčka vieme zasiahnuť, je súčtom riadku a stĺpca (nestane sa, že by sme nejakú figurku zarátali dvakrát, pretože prienik riadku a stĺpca je len to políčko, ktoré práve počítame, a to je voľné). Ak je nájdený počet väčší, než doterajšie maximum, zapamätáme si ho (aj so súradnicami aktuálneho políčka).Toto riešenie má časovú zložitosť O(N3), pretože pre každé z N2 políčok prejdeme celý jeho riadok a stĺpec, ktoré majú N prvkov.
Lepšie riešenie
Môžeme si všimnúť, že v predošlom riešení sme sa veľakrát pozerali na každé políčko v tabuľke, keď sme zisťovali súčty stĺpcov a riadkov. Tie by sme si mohli predpočítať. Na začiatku si vytvoríme dve polia dĺžky N, jedno pre súčty jednotlivých riadkov a druhé pre súčty stĺpcov. Potom prejdeme celú tabuľku, a vždy, keď nájdeme figúrku, pripočítame ju k súčtom riadka a stĺpca, v ktorých leží.Nakoniec prejdeme tabuľku druhý raz. Pre každé voľné políčko si zoberieme súčet jeho riadku a stĺpca, a nájdeme maximum. Predpočítavanie aj hľadanie optimálneho políčka zvládneme v čase O(N2), čo je aj výsledná časová zložitosť.
Ešte lepšie riešenie
Určite neexistuje rýchlejšie riešenie, než O(N2). Ak totiž nenačítame všetky políčka šachovnice, nemáme istotu, že sme našli najlepšie riešenie, pretože to mohlo závisieť od tých, ktoré sme nenačítali. Tak ako môže existovať Ešte lepšie riešenie? Predošlé riešenia si potrebovali pamätať celú šachovnicu, teda mali pamäťovú zložitosť O(N2). Úlohu však dokážeme vyriešiť aj tak, že nám stačí pamätať si O(N) informácii:Zapamätáme si súčty stĺpcov, ktoré postupne zvyšujeme vždy, keď v danom stĺpci nejakého riadku nájdeme figúrku. Okrem toho si pre každý stĺpec zapamätáme najlepší súčet riadku, ktorý mal v danom stĺpci voľné políčko.
Konkrétne: Šachovnicu čítame po riadkoch. Pri každom načítaní riadku najskôr zistíme jeho súčet. Potom každému stĺpcu, v ktorom práve je figúrka, zvýšime súčet o 1. A pre každý stĺpec, kde práve figúrka nie je, sa pozrieme na jeho zatiaľ najlepší súčet riadku, a ak je aktuálny riadok ešte lepší, prepíšeme ním maximum. Nakoniec si pre každý stĺpec zrátame súčet jeho najlepšieho riadku so súčtom samotného stĺpca. Maximálny výsledok má naše hľadané políčko – je to voľné políčko, ktorého riadok a stĺpec majú najväčší možný súčet.