Čtvrtá série začátečnické kategorie dvacátého osmého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 28-Z4-1: Půdorys
- 28-Z4-2: Vykopávky
- 28-Z4-3: Mocniny
- 28-Z4-4: Čtyřková
- 28-Z4-5: Vyhlazení GPS
- 28-Z4-6: Klučičí drby
28-Z4-1 Půdorys (Zadání)
Důležitou součástí řešení bylo uvědomit si, že hledané obdélníky mají jednu zajímavou vlastnost – body ležící na jedné straně obdélníka mají vždy stejnou jednu souřadnici. Takže svislé hrany obdélníka mají stejnou x-ovou souřadnici a vodorovné zase y-ovou.
My musíme pro každý bod na vstupu ověřit, zda leží na nějaké hraně obdélníka. K tomu potřebujeme nejdříve znát souřadnice těchto hran. To už zvládneme jednoduše.
Všechny body na levé svislé hraně budou mít nejmenší x-ovou souřadnici, body na pravé svislé hraně budou mít největší x-ovou souřadnici. Stačí nám tedy pouze projít x-ové souřadnice všech bodů a zapamatovat si minimum a maximum. Pro vodorovné hrany analogicky s y.
Teď už jenom ověříme, že každý bod leží na nějaké hraně jednoduchým porovnáním jeho souřadnic se zjištěnými souřadnicemi hran.
28-Z4-2 Vykopávky (Zadání)
Je zřejmé, že když mají mít všechny čtyři obdélníkové oblasti stejný součet, bude to právě součet všech políček vydělený čtyřmi. Abychom ho tedy spočítali, projdeme si nejdřív jednou všechna čísla a sečteme je. Zatím nezáleží na tom, v jakém pořadí je projdeme.
Dále si všimneme, že část nahoře od bodu S (všichni se tu mají potkat) a část dole budou mít stejný součet, a to právě polovinu součtu celkového. Budeme tedy procházet čísla ještě jednou, tentokrát po řádcích, budeme je opět sčítat, ale zastavíme se, když se dosčítáme k polovině celkového součtu. Zapamatujeme si, kolik řádků jsme zatím prošli, to bude totiž výška obdélníku, kterou chceme zjistit.
Do třetice všeho dobrého projdeme čísla ještě jednou, tentokrát po sloupcích. Opět je budeme sčítat, dokud se nedostaneme k polovině celkového součtu. Počet zatím prošlých sloupců nám dá hledanou šířku obdélníku.
Protože jsme čísla na vstupu prošli třikrát, složitost bude O(RS), což je počet řádků vynásobený počtem sloupečků, tedy počet všech políček.
Ještě se zamyslíme, jak by se dala uspořit paměť – co kdybychom si nemuseli pamatovat všech R čísel? Vždy potřebujeme počítat součty celých řádků a celých sloupců. Takže by stačilo si při načítání vstupu průběžně sčítat všechna čísla v každém řádku a sloupci, a pamatovat si jen tyto údaje, kterých je R + S.
28-Z4-3 Mocniny (Zadání)
Přímočarým řešení Kevinova problému je si pro každé číslo x spočítat jeho druhou a třetí mocninu, a pak ověřit, že i ony leží v naší posloupnosti. To můžeme udělat třeba sekvenčním vyhledáním x2 a x3. Zapamatujeme si právě ta x, pro která jsme našli dané mocniny. Ze zapamatovaných x už jenom stačí najít minimum.
Toto řešení má kvadratickou složitost O(N2), kde N je počet čísel na vstupu. Pro každé číslo projdeme všechna ostatní a zjistíme, jestli mezi nimi je i jeho druhá a třetí mocnina.
Rychlejší řešení získáme úpravou toho přímočarého. Nejvíce času strávíme hledáním x2 a x3. Tento krok můžeme urychlit tím, že si na začátku celou posloupnost setřídíme. Poté už můžeme mocniny hledat pomocí binárního vyhledávání.
Navíc nám stačí se zastavit u prvního x v setříděné posloupnosti. Toto x je
totiž první pro které jsme našli mocniny, takže všechna další čísla už budou
pouze větší. (V Pythonu se hodí použít set, který je přímo dělaný na podobné vyhledávání.)
Setřídění nám zabere O(N log N) času. Binární vyhledání jednoho prvku má logaritmickou složitost a jelikož hledané x může být téměř až na konci setříděné posloupnosti, provedeme jej pro každý prvek. Tj. celé vyhledávání trvá O(N log N) času, což je stejné jako složitost setřídění, bude to tedy i výsledná složitost.
Pokud váš programovací jazyk disponuje datovou strukturou pro množinu, často
pojmenovanou set, můžete ji s výhodou použít. Ta si interně udržuje čísla
setřízená a vlastně na nich binární vyhledávání provádí – jen nemá čísla uložená
v seznamu. Rychlé řešení pak vyjde velmi elegantně na jeden řádek.
28-Z4-4 Čtyřková (Zadání)
Úloha byla trochu podlá, protože zjistit odpověď pro jedno číslo je vlastně stejně těžké, jako ji zjistit pro všechna najednou. Pojďme se na to podívat.
Začínáme s jednou čtyřkou. Jaká čísla jsme schopni vyrobit, pokud použijeme čtyřky dvě? Jsou to 8 = 4 + 4, 0 = 4 - 4, 16 = 4 * 4 a 1 = 4 / 4. Protože tato čísla s jednou čtyřkou určitě nevyrobíme, zapamatujme si o nich že jdou vyrobit nejlépe se dvěmi.
A co když si dovolíme další čtyřku navíc? Pak se stačí podívat na ta čtyři čísla, která umíme vyrobit se dvěma čtyřkami, a zkusit k nim všemi čtyřmi operacemi přidat třetí. Tím, že se operace vyhodnocují zleva doprava, snadno spočítáme výsledek nezávisle na tom, jak jsme dokázali vyrobit číslo původní.
Vytvoříme si tedy pole výsledků v a pro každé číslo od 0 do 9 999
si do něj uložíme třeba -1, protože jej zatím vyrobit neumíme. Jen pro číslo
4 víme, že jej umíme vyrobit za pomocí jedné čtyřky.
Pak si pořídíme frontu čísel, která jsme dokázali vyrobit, ale ještě z nich neprozkoumali možnosti rozšíření o další čtyřku. Na začátku bude obsahovat jen tu první čtyřku.
Následně vždy vezmeme číslo x z fronty a podíváme se na výsledek operace
x + 4 = y. Pokud jsme y ještě neviděli, ve v[y] bude stále mínus
jednička. V tom případě toto musí být nejkratší způsob, jak y vyrobit,
a můžeme do v[y] uložit v[x] + 1. Současně y přidáme do fronty.
To samé provedeme pro ostatní operace. Dáme si při tom pozor, abychom přeskočili dělení, pokud x není dělitelné čtyřmi.
Ve výpočtech jsme trochu zanedbali to, že Sářina kalkukačka umí počítat jen s čtyřcifernými čísly. Jak bylo napovězeno v zadání, s výhodou použijeme operaci modulo. Každé y proženeme jednoduchým výrazem:
Přičítat můžeme bezpečně, i když je číslo kladné, protože se 10 000 modulením zase odečte.
Až frontu vyprázdníme, určitě jsme našli všechna čísla, která vyrobit jdou,
a v poli v máme výsledky, které chceme vracet. Stačí se do v
podívat na správné místo a vypsat výsledek.
Pokud trochu znáte grafové algoritmy, můžete si všimnout, že popsaný způsob je vlastně prohledávání grafu do šířky. V tomto grafu jsou vrcholy čísla a z každého vedou tři nebo čtyři hrany za operace.
Můžeme prozradit, že každé číslo takto vytvořit jde, a dokonce je nejkratší
výraz až na dvě čísla jednoznačný. Pokud byste chtěli zároveň výraz vypsat,
můžete si do v uložit i x a operaci, kterou jste y vyrobili,
a z těchto pak výraz zpětně poskládat.
Algoritmus má trochu překvapivě konstantní časovou složitost. Nejprve proběhne předvýpočet, který není závislý na vstupu, a tedy je z principu konstantní. Po přečtení vstupu už se jen podíváme na správné místo do pole. Pokud bychom neměli pevně zadaný rozsah 10 000 čísel, ale nějaké nejvyšší číslo K, časová složitost by byla lineární s K. Stejně tak paměťová.
Aby byl váš výpočet ještě rychlejší, mohli jste použít trik. Na co výsledky počítat při každém startu programu znovu, když si je můžete spočítat jednou a uložit pro příště například do souboru? Pro získání plného počtu bodů to ale vůbec nebylo nutné, 10 000 čísel spočítáte popsaným způsobem i v Pythonu bleskově.
28-Z4-5 Vyhlazení GPS (Zadání)
Úlohu si trochu upravíme – místo toho, abychom počítali průměr, budeme počítat pouze součet posledních K hodnot. Každé číslo pak jen před vypsáním vydělíme K, takže vyřešíme původní zadání, ale přemýšlet se o tom bude lépe.
Použijeme myšlenku pohyblivého okénka. Prohlasíme na chvíli, že K je 3. Známe součet S1 = x1 + x2 + x3, a dostaneme x4. Jak z nich spočítat součet S2 = x2 + x3 + x4?
Každý vidí, že stačí odečíst x1 a přičíst x4. Důležité je, že K může být úplně libovolné a vždy stačí nejstarší číslo odečíst a nové přičíst, tedy provést konstantní počet operací.
Pořídíme si proto pole, do kterého si budeme ukládat posledních K čísel, a jejich součet si budeme počítat průběžně. Vždy první číslo z pole vyhodíme a na konec jiné přidáme.
Počkat, tady něco nehraje. Vyhodit první číslo z pole nám zabere spoustu času, protože musíme ta ostatní posunout!
Představte si, že byste si mohli pořídit pole zatočené do kruhu, takový prstenec. Někdy se mu proto anglicky říká ring buffer, cyklický buffer. Prstenec bude stát před námi na stole a místo abychom my točili s prstencem, budeme obcházet okolo stolu.
Tolik představa, teď jak to implementovat. Pole zůstane rovné a bude mít K prvků jako předtím. V prvním kole budeme pracovat s prvním prvkem s indexem 0. V druhém s druhým… až v K-tém s K-tým s indexem K-1. Potom by se nám hodilo, abychom pokračovali znovu od začátku. K tomu nám poslouží stará známá funkce modulo. V i-tém kole budeme pracovat s prvkem s indexem i mod K.
Nechť se tedy průběžný součet jmenuje S a udržujeme cyklický buffer B. Jak S, tak všechny prvky B budou na začátku nulové. V i-tém kole odečteme od S prvek B[i mod K] a následně na jeho místo vložíme nové číslo xi, a zpátky ho přičteme do S.
Pokud by se nám nelíbilo, že počítadlo kroků i roste do nekonečna a může přetéci, budeme ho průběžně modulit. To totiž ničemu nevadí, my ho k jinému účelu nepotřebujeme.
Takto se nám podařilo udržovat průběžný součet s konstantní časovou složitostí na jeden krok. K celému výpočtu potřebujeme paměť velikosti O(K), kterou si ale vynulujeme na začátku, a v každém kroku přistupujeme pouze k jednomu prvku.
28-Z4-6 Klučičí drby (Zadání)
Nejprve si uvědomíme, že drb se vždy přestane šířit – kluků je konečně mnoho a každý říká drb právě jednomu, takže časem se určitě dostane k někomu, kdo už jej zná.
Navíc víme, že o přestávce je stejný drb sdělován nejvýše jednou (říkáme ho pouze svému nejlepšímu kamarádovi). Proto se každý drb dostane do skupiny kamarádů, kteří si drby předávají do kruhu. Drb se zastaví tehdy, když se jej dozví všichni z nějakého cyklu.
Zkusme pro každý drb spočítat, kolik kluků jej bude znát. Uděláme to přesně tak, jak se drby šíří. Začneme u našeho nejlepšího kamaráda, poté je na řadě nejlepší kamarád toho našeho, pak jeho nejlepší kamarád, … A tak dál, dokud nenarazíme na nějakého, který už drb zná.
A abychom věděli, kolik kluků se ho dozvědělo, stačí si postupně nejlepší kamarády počítat (v každém kroku přičteme jedničku k počítadlu).
Jak poznáme, že jsme se právě dostali k někomu, kdo už drb zná? Budeme si kluky značit. Pořídíme si třeba pole plné nul, kde máme pro každého kluka jedno políčko. Vždy, když se někdo dozví drb, uložíme si do jeho políčka jedničku. Před šířením dalšího drbu si celé pole vynulujeme.
Složitost tohoto řešení je kvadratická vzhledem k počtu kluků ve třídě – každý drb sledujeme zvlášť, drbů je stejně jako kluků. Drb se navíc může rozšířit až ke všem klukům.
Ale jde to ještě zrychlit! Všimněte si, že často počítáme vícekrát, jak dlouho se šíří nějaký drb od stejného kluka. Mohli bychom si tedy pro každého kluka pamatovat, ke kolika dalším se od něj drb dostane. Tomuto číslu budeme říkat společenský dopad.
Jak společenské dopady získat a jak si je pamatovat? Jednoduše. Jako paměť nám poslouží další pole. Začneme opět simulovat šíření nějakého drbu. Postupně procházíme a počítáme nejlepší kamarády jako v prvním řešení, počítadlo si označíme jako K.
Rozdílem oproti kvadratickému řešení bude, že se zastavíme i tehdy, řekneme-li drb někomu, jehož společenský dopad už známe (budiž to číslo L). K + L nám udává celkový počet kluků, kteří se dozví právě simulovaný drb.
Skočíme zpátky na začátek a projdeme stejnou cestu znovu, ale budeme u toho ukládat dopady jednotlivých kluků – první má K + L, druhý K + L - 1, další K + L - 2, … Těm, kteří už mají společenský dopad spočítaný, ho nepřepisujeme, dokonce u prvního takového se opět zastavíme.
Pořád se nám může stát, že se simulace zastaví kvůli podmínce z prvního řešení (přestane se i šířit drb). Připomeňme, že drb se zastaví, když se dostane do cyklu, a dozví-li se ho někdo z cyklu, dozví se ho i všichni ostatní z něj. To znamená, že společenský dopad všech kluků na cyklu bude stejný – délka cyklu (drb se z tohoto kruhu nikdy nikam dál nedostane).
Místo, kde se v cyklu zastavíme, je zároveň i to místo, kde do něj vstoupíme. Zapamatujeme si ho. Opět skočíme na začátek a ukládáme K, K - 1, K - 2, … Jakmile znovu narazíme na cyklus, přestaneme odečítat jedničku a ukládáme stejné číslo (právě délku cyklu).
Poznámka na konec: Tuto vylepšenou simulaci postupně spustíme pro každý drb (nemusí totiž existovat kluk, jehož společenský dopad postihne všechny).
Zrychlili jsme řešení? Simulujeme opět všechny drby a simulace může trvat lineárně s počtem kluků ve třídě. Jenže čím déle trvá, tím více společenských dopadů spočítáme. Trvá-li K kroků, zapamatujeme si tím i K dosud neznámých dopadů. To ovšem znamená, že už je žádná další simulace nebude počítat – od každého kluka šíříme drb pouze jednou.
Dohromady uděláme tolik kroků, kolik je ve třídě kluků. Celková časová složitost je lineární, paměťová také.
Pokud by nás zajímala časová složitost jedné simulace, můžeme o ní tvrdit, že je amortizovaně konstantní. Sice můžou některé trvat dlouho, ale v průměru (když pustíme simulaci pro všechny drby) nám jedna trvá pouze konstatně dlouho.