Třetí 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-Z3-1: Místo oslavy
- 28-Z3-2: Zlomkovník
- 28-Z3-3: Posloupnost za trest
- 28-Z3-4: Zbývající úkoly
- 28-Z3-5: Ukotvení stromu
- 28-Z3-6: Šíření drbů
28-Z3-1 Místo oslavy (Zadání)
K vybrání vhodného místa pro pořádání oslavy stačí vedení školy najít první a poslední dům od začátku města, kde bydlí zájemci o oslavu. Je zřejmé, že právě obyvatelé těchto domů to budou mít nejdále. Ovšem to znamená, že stačí najít minimum a maximum v zadané posloupnosti čísel, což zvládneme během jediného průchodu vstupem.
My ale ještě chceme, aby to oba nejvzdálenější zájemci měli co nejblíže, tj. aby tato nejdelší vzdálenost byla co nejmenší. Proto budeme hledat střed mezi dvěma zmíněnými domy, vzdálenost z obou pak bude stejná.
Vzhledem k tomu, že čísla budov jsou celočíselná, chceme opět celočíselný výsledek. Pokud je vzdálenost mezi prvním a posledním domem liché číslo, jsou dvě možnosti pro konání oslavy, obě stejně výhodné. My můžeme vybrat libovolnou z nich, zvolme si vždy třeba tu s nižším číslem. Nyní bude stejný postup pro obě varianty, tedy když je ona vzdálenost liché i sudé číslo. Minimum si označíme Min, maximum jako Max, výsledná pozice sálu bude (Max + Min) div 2.
28-Z3-2 Zlomkovník (Zadání)
| A |
| A+B |
| A+B |
| B |
Stačí nám tedy v podstatě projít zpět ke kořeni a zaznamenat, kde jsme byli. Jak taková cesta bude vypadat, zjistíme právě porovnáváním čitatele a jmenovatele. Zapamatované pořadí bude obrácené, než jaké máme vypsat v odpovědi, proto jej nesmíme zapomenout poté obrátit.
| A |
| A+B |
| A |
| A+B-A |
| A |
| B |
| A+B-B |
| B |
| A |
| B |
Pokračovat budeme opět k novému otci aktuálního syna. Tento postup budeme opakovat, až dokud se nedostaneme do kořene stromu. Poté nezapomeneme vypsat posloupnost R a L v obráceném pořadí a máme výsledek.
28-Z3-3 Posloupnost za trest (Zadání)
Nejdříve samozřejmě zkusíme počítat postupně členy posloupnosti P1,P2,… ,PN. První člen P1 je triviální, Pi+1 vyrobíme z Pi tak, že budeme procházet číslice zleva doprava a počítat, jak dlouhé úseky stejných číslic potkáme. To pokaždé zvládneme v čase O(počet cifer).
Zpočátku to půjde dobře, jenže cifer bude rychle přibývat. (Dokonce exponenciálně: i-tý člen má přibližně 1.304i číslic. To dokázal John Conway fascinujícím způsobem. Pokud máte chuť na trochu pokročilejší matematiky, směle se začtěte do článku ve wikipedii a odkazů, které z něj vedou.)
Nás naštěstí zajímá jen prvních K číslic výsledku. Zkusíme tedy počítat jen prvních K číslic každého členu posloupnosti. Je to trochu riskantní, protože by se mohlo stát, že při vytváření dalšího členu budeme potřebovat víc číslic předchozího členu, než jsme spočítali. Pokusem si ale můžeme ověřit, že posloupnost roste dost rychle, takže se to pro K≥ 10 nestane.
Z toho dostaneme řešení o složitosti O(NK), dost rychlé na to, aby vyřešilo všechny naše vstupy během pár desítek sekund. Přesto ho zkusíme ještě trochu zrychlit.
Označme Qi hodnotu Pi zkrácenou na prvních K číslic. Pokud je K malé, začnou se hodnoty Q1,Q2,… brzy opakovat. Náš algoritmus si proto bude ve slovníku pamatovat všechna Qi, která už viděl, a číhat na první opakování. Jakmile zjistí, že Qi=Qj pro nějaké j<i, musí se od i-té pozice neustále opakovat úsek Qj, Qj+1, … , Qi-1. Stačí tedy zjistit, který z opakovaných členů vyjde na hledané QN, a vypsat ho.
Zdálo by se, že perioda bude pro velká K dostatečně daleko, takže tento trik nepomůže. Neváhejme a zkusme to. Překvapení: pro maximální povolené K=300 000 je Q55 = Q52 a zjevně to platí i pro všechna menší K. Stačí tedy spočítat prvních 55 členů posloupnosti a známe odpověď pro jakékoliv N.
Program k základnímu řešení (Python 3)
Program k rychlejšímu řešení (Python 3)
28-Z3-4 Zbývající úkoly (Zadání)
Nejprve vymyslíme jednoduché řešení, a pak si jej prostým trikem velmi zrychlíme. Pojďme na to.
Začneme tím, že si načteme celý vstup. Pro každý úkol si budeme chtít pamatovat jeho délku a seznam úkolů, na kterých je závislý. Toto nejde udělat jinak, než že celý vstup načteme do paměti. V poli t uschováme délky, v poli dep potom seznamy úkolů, které musíme provést dříve. Jak to udělat pohodlně se můžete podívat do programu v Pythonu.
Potom si napíšeme rekurzivní funkci, která spočítá, kdy nejdříve může být úkol x dokončený:
def finish_time(x):
deptime = 0
for d in dep[x]:
deptime = max(deptime, finish_time(d))
return deptime + t[x]
V této funkci vezmeme maximum z času dokončení všech úkolů, na kterých je x závislý, a přičteme dobu trvání x. Jak ji použijeme?
Abychom si zjednodušili kód, můžeme použít podlý trik. Přidáme si neexistující úkol A, který bude trvat 0 jednotek času, zato ale bude závislý na všech ostatních. Jeho čas dokončení je pak přesně to, co po nás úloha žádá.
Jak to bude rychlé? Představte si takový vstup:
V takovém případě se funkce zavolá postupně s těmito parametry:
Zde je nutno si všimnout, že se funkce volá mnohokrát třeba pro jedničku, přestože její návratová hodnota bude vždy stejná. Vždyť si výsledky můžeme uložit:
def finish_time(x):
if x not in fintime:
deptime = 0
for d in dep[x]:
deptime = max(deptime, finish_time(d))
fintime[x] = deptime + t[x]
return fintime[x]
Jak bude vypadat seznam volání teď?
Nemůžeme říct, že by se nyní volala pro každé x pouze jednou. Čeho jsme se ale zbavili, je neustálé opakování „ocásků“, pro které už známe odpověď, a můžeme ji vrátit daleko dříve.
Pokud bychom chtěli časovou složitost vyčíslit, všimneme si že funkci zavoláme jednou jako závislost na virtuálním úkolu A, a jednou pro každou závislost jiného úkolu y na tomto úkolu x – to právě tehdy, když poprvé počítáme y. Dohromady víme, že závislostí je K, takže celkový počet volání bude N+K. N (počet úkolů) musíme započítat, protože může být klidně větší než K.
Úplně stejně se na to podíváme, pokud budeme počítat čas pro funkci samotnou. Všechna volání dohromady ve vnitřním for cyklu stráví O(K) času, všechno ostatní už je jen konstantní zpomalení. Proto bude mít výpočet časovou složitost O(N + K). Do tohoto času se vejdeme i s načtením vstupu a vypsáním výstupu, a stejnou funkcí odhadneme i prostorovou složitost.
Doteď se úloha zdála růžová. Bohužel jsme si při testování úlohy nevšimli výrazného omezení jazyka, který pro řešení úloh propagujeme – Pythonu. Ten totiž ve výchozím nastavení neumožňuje zanořit volání funkcí více než tisíckrát.
Tentokrát tedy přidáváme tři zdrojové kódy. První problém obchází tím, že nastavení změní. Bohužel, bude fungovat jen na Linuxu. O důvodech se můžeme pobavit na fóru.
Druhý jej řeší tím, že nepoužívá volání funkcí, ale simuluje jej pomocí seznamu. Technika je to obecná a dá se použít vždy, jen zdrojový kód není úplně dobře čitelný.
28-Z3-5 Ukotvení stromu (Zadání)
Pro začátek předpokládejme, že žádné dva body nemají stejnou x-ovou ani y-ovou souřadnici.
Nejprve body seřadíme podle x-ové souřadnice.
Pokud jsou všechny body středově souměrné, musí být bod nejvíce vlevo souměrný s tím nejvíce vpravo. Tím pádem podle těchto dvou bodů jednoznačně určíme střed S – bude přesně v polovině mezi nimi.
Zbývá ověřit, že všechny ostatní body jsou podle S souměrné. Druhý musí být souměrný s předposledním, třetí se třetím od konce a tak dál pro všechny body. Pokud má být souměrný bod A s bodem B podle středu S, musí platit Sx-Ax = Bx-Sx a zároveň Sy-Ay = By-Sy.
Pokud se jediná podmínka poruší, odpovíme, že nejsou souměrné. Když žádný test neselže, odevzdáme střed S.
Algoritmus funguje i pokud mají nějaké body stejnou x-ovou souřadnici. V takovém případě je potřeba při řazení porovnávat primárně podle x-ové a sekundárně podle y-ové souřadnice.
Proč to funguje? Protože přesně takové pořadí bychom dostali, kdybychom celou rovinu nepatrně pootočili, aby se žádné x-ové souřadnice neshodovaly.
Zbývá dořešit časovou složitost. Body, který je N, umíme seřadit v čase O(N log N) třeba MergeSortem. Pokud je uchováváme v poli, bude každý z N testů trvat konstantní čas. Celková časová složitost je tedy O(N log N).
28-Z3-6 Šíření drbů (Zadání)
Dobrým prvním krokem může být zkusit správný počet potřebných přestávek odhadnout. Proto se pokusme spočítat správné výsledky pro malý počet kamarádek.
Máme-li jen jednu kamarádku, ta zná svůj drb hned (tedy nepotřebuje ani jednu přestávku). Dvě kamarádky potřebují jednu přestávku na to, aby si vyměnily své drby. Čtyři kamarádky (jak máme v zadání) potřebují dvě přestávky. S trochou trpělivosti můžeme zkoušením zjistit, že pro osm kamarádek jsou potřeba tři přestávky.
Z toho (a s nápovědou v zadání, že máme uvažovat pouze N, která jsou mocniny dvojky) můžeme odhadnout, že potřebujeme log2 N přestávek. Jinak řečeno, pokud je 2k kamarádek, klepy si vymění během k přestávek.
Pojďme se tedy podívat, jestli se nám podaří najít takové přiřazení kamarádek, aby se klepy šířili tak rychle. Začněme u malého počtu kamarádek. Když máme pouze dvě kamarádky, tak stačí když se potkají během jediné přestávky. Řešení pro čtyři kamarádky máme rovnou v zadání (nejprve se potkají A–B a C–D, poté A–C a B–D).
Jak můžeme přistupovat k tomu, když je ve třídě kamarádek osm? Rozdělme si je na dvě skupiny po čtyřech a nechme nejprve rozšířit drby v rámci jednotlivých skupinek. Jak jsme ukázaly výše, aby každá kamarádka znala všechny skupinové drby, stačí nám dvě přestávky.
Všimněte si, že na rozšíření drbů mezi skupinkami nám pak stačí už jen jedna přestávka – první kamarádka z první skupinky se podělí o drby s první kamarádkou z druhé skupiny, druhá s druhou a tak dále. Každá kamarádka pak bude vědět všechny drby ze své skupiny (ty znala i před touto poslední přestávkou) a tím, že se potkala s někým z druhé skupiny, tak se dozvěděla i všechny drby z druhé skupiny.
Stejný trik můžeme použít i pro šestnáct kamarádek – stačí je rozdělit na dvě skupiny. Každá skupinka během tří přestávek rozšíří drby v rámci své skupiny (tak jak bylo ukázáno v předchozím odstavci). Během následující přestávky si pak každá kamarádka popovídá s příslušnou kamarádkou z druhé skupiny, čímž se dozví všechny drby.
Ve skutečnosti takto můžeme postupovat pro libovolný počet kamarádek. Kamarádky rozdělíme na dvě skupiny a zamyslíme se nad tím, jak rozšířit drby v rámci skupin. Potom během jedné přestávky už rozšíříme drby napříč skupinami.
Tímto způsobem spotřebujeme za každé zdvojnásobení počtu kamarádek jen o jednu přestávku více. Dostali jsme se tedy přesně na náš vytyčený cíl v počtu přestávek.
Tato technika rozdělování problémů na několik menších, které se řeší vlastně stejnou technikou, je v informatice poměrně populární a nazývá se Rozděl a panuj. Pokud tě zaujala a chceš se o ní dozvědět více, tak další informace najdeš v naší kuchařce.
Na závěr si pojďme ještě ukázat, že rychleji to skutečně nejde. Představme si na chvíli, že už proběhlo několik přestávek. Označme si d počet drbů, které zná nejpopulárnější kamarádka (tedy ta, která zná ze všech kamarádek nejvíce klepů). Druhá nejpopulárnější tudíž zná nejvýše také d drbů. Když se tyto dvě kamarádky během další přestávky potkají, obě budou znát nejvýše 2d drbů.
Všimněme si, že (jelikož se jednalo o nejpopulárnější kamarádky) nikdo nebude po další přestávce znát více jak 2d drbů. Také si uvědomme, že toto platí pro každou přestávku. Takže, bude-li p značit počet drbů, které zná nejpopulárnější kamarádka, p se nám každou přestávku nejvýše zdvojnásobí.
Toto už nám (s tím, že na začátku je p jedna), dává právě naší formulku, že po k přestávkách bude p nejvýše 2k. Tedy při 2k kamarádkách potřebuje i nejpopulárnější kamarádka alespoň k přestávek.