První série začátečnické kategorie třicátého čtvrtého ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

Řešení úloh

• 34-Z1-1: Letopočty
• 34-Z1-2: Čísla domů
• 34-Z1-3: Hádání čísel
• 34-Z1-4: Šíření zpráv

34-Z1-1 Letopočty (Zadání)

Zřejmé řešení by bylo postupně pro každý rok, který Kevin na planetě stráví, spočítat počet dní, a nakonec všechna tato čísla sečíst. Pro přestupný rok se stačí dívat, jestli je číslo dělitelné 3 a zároveň není dělitelné 48. Tím získáme řešení, které je lineární v počtu dní, které Kevin na planetě stráví. Takto šly získat až 4 body, ale pak už rozdíl mezi počátečním a koncovým rokem byl příliš veliký na to, aby šel tento postup aplikovat.

Určitě nás napadne, že to půjde zlepšit. Přeci když přesně známe, kolikátý každý rok je přestupný (a kdy jsou výjimky), tak se nemusíme dívat na každý rok zvlášť.

Nejdříve si spočítáme, kolik dní by Kevin na planetě strávil, kdyby měl každý rok 42 dní. Konkrétně by to bylo 42 ·(y-x+1) dní. Dále musíme započítat všechny přestupné roky, tedy přičíst den za každý násobek trojky v rocích, ve kterých se Kevin na planetě nachází. Tím jsme ale započetli až moc přestupných let – protože 48 je násobkem 3, tak jsme započítávali mezi přestupné roky i ty, které ve skutečnosti byly nepřestupné. Za každý násobek 48 tedy musíme jeden den odečíst. Tento postup už vede do cíle, jen musíme zjistit, kolik přesně je kterých násobků.

Číslo prvního přestupného roku zjistíme jako x_p = 3·⌈x / 3 ⌉. Výraz ⌈x / 3 ⌉ značí horní celou část z x/3, tedy nejmenší celé číslo větší nebo rovno x/3. Celý výraz pak značí nejmenší celé číslo větší nebo rovno x, které je násobkem trojky. Například pro x=100 bychom dostali 102. V programovacích jazycích je pro celou část často dostupná funkce ceil.

Obdobným způsobem zjistíme číslo posledního přestupného roku, tentokráte jako y_p = 3·⌊y / 3 ⌋. Zde používáme dolní celou část neboli floor.

Teď už můžeme spočítat celkový počet přestupných roků jako (y_p - x_p) / 3 + 1. Zkuste si rozmyslet, že tento postup bude fungovat i tehdy, pokud během Kevinova pobytu žádný přestupný rok nenastane.

Počet výjimek (čísel dělitelných 48, tedy roků nepřestupných) spočítáme úplně stejně, jen 3 nahradíme za 48.

Zbývá z výsledků spočítat odpověď. Celkový počet dní je tedy 42 ·(y-x+1) + počet přestupných dní - počet výjimečných dní.

Jaká je časová složitost vylepšeného řešení? Počet kroků algoritmu vůbec nezáleží na číslech roků na vstupu. Je tedy časová složitost konstantní? Pokud předpokládáme, že jsou čísla roků rozumně velká na to, abychom s nimi dokázali počítat, pak ano. Jinak bychom museli násobení a dělení zpracovávat ručně, pak by byla složitost lineární v počtu cifer.

Program (Python 3)

34-Z1-2 Čísla domů (Zadání)

Domy si můžeme představit jako uspořádané dvojice pozice a času dostavby. Pozicí máme na mysli informaci o kolikátý dům v řadě se jedná.

Když si tyto uspořádané dvojice setřídíme podle data, tak snadno můžeme zrekonstruovat celou stavbu a domům přiřadit čísla.

Domy totiž byly postaveny v pořadí, v jakém jsou v tomto setříděném poli, stačí jim tedy jen postupně přidělit čísla.

Chceme ale odpovídat v původním pořadí, připravíme si tedy pole odpovědí a to postupně naplníme. Projdeme setříděné dvojice a do pole odpovědí na index pozice domu napíšeme jeho číslo. Nakonec už jen stačí pole odpovědí vytisknout.

Jak ale jednoduše třídit data a časy? Povšimneme si nádherné vlastnosti formátu, ve kterém je zadaný vstup – stačí ho totiž třídit jako řetězce. Díky tomu, že všechny části mají jasně danou délku a jsou uspořádány dle jejich důležitosti, tak vše funguje.

Časová složitost tohoto algoritmu je O(N log N). Paměťová je O(N).

Program (Python 3)

Program (C++)

34-Z1-3 Hádání čísel (Zadání)

Nejpřímočařejším řešením by bylo ptát se postupně na čísla od jedné, dokud neuhodneme to správné. V nejhorším případě ale může hledané číslo být až R, takže by to mělo lineární časovou složitost O(R).

Čísla ale nemusíme zkoušet po jednom. Když se zeptáme na nějaké číslo a není to to správné, dozvíme se také, kterým směrem máme hledat dál. Například když se na začátku zeptáme na číslo x a dostaneme odpověď Uber, čísla x až R už nemusíme řešit a stačí dále prohledávat jenom čísla 1 až x - 1. Když si číslo x budeme volit strategicky, v každém kroku si umíme prohledávaný úsek výrazně zmenšit.

Když bude x blízko jednoho okraje, je sice možné, že tím vyřadíme velký úsek najednou, ale v nejhorším případě bude vždy hledané číslo na špatné straně a vyřadíme jenom malý kousek. Zato když si zvolíme x uprostřed, budou úseky na obou stranách stejně dlouhé a vždy tedy vyřadíme alespoň polovinu čísel.

Jelikož po každém kroku je rozsah minimálně o polovinu menší (a když dojdeme na rozsah 1, tak se zastavíme), tak když se na to podíváme v opačném pořadí (v každém kroku zpět se velikost rozsahu alespoň zdvojnásobí), tak původní velikost rozsahu (R), musela být nejméně dva na počet kroků. Z toho vyplývá, že kroků mohlo být maximálně log₂ R. Protože každý krok trvá konstantní čas a má jeden dotaz, časová složitost i počet dotazů budou O(log R). Paměť je konstantní – používáme jen dvě proměnné.

Tomuto postupu se říká binární vyhledávání a obecně se používá, když potřebujeme najít pozici konkrétního prvku v seřazeném poli pomocí porovnávání.

Program (Python 3)

34-Z1-4 Šíření zpráv (Zadání)

Zamysleme se nejprve, jak bychom úlohu řešili ručně – nejspíše bychom procházeli log zpráv podle času, zkontrolovali, jestli odesílatel už o úspěchu věděl a pokud ano, poznamenali si uvědomělost i u příjemce. Pak už stačí jen ve správném pořadí vypsat ID všech informovaných lidí.

Výhoda této myšlenky je, že zaručeně funguje. Nepřevedli jsme si úlohu na žádný jiný problém, děláme prostě přesně to, co po nás chce zadání. Bohužel ale k plnohodnotnému algoritmu chybí vyjasnit několik detailů. Pojďme je doplnit.

Jak si pamatovat, kdo už o úspěchu ví? Pořiďme si pole a nově informované prostě vložme nakonec. Hledání obnáší celé pole projít a podívat se, jestli se v něm hledaná osoba nachází. Takové řešení je ale dost pomalé – každé z M hledání trvá až O(N) kroků, tedy celkově O(MN). Navíc musíme na konci ještě seznam ID seřadit. Paměti pak spotřebujeme O(M).

Když je N malé

Co kdyby N bylo rozumně velké? To nám zadání neslibuje, ale je zajímavé (i z hlediska zisku bodů) se nad touto variantou zamyslet. O ID máme slíbeno, že to je celé čislo od 1 do N. Mohli bychom si tedy pořídit pole délky N a na i-té pozici (nebo i-1, číslujeme-li od nuly) si uchovávat stav informovanosti člověka s ID i. Jak rychlé to je teď? Potřebujeme čas O(N) na pořízení pole, O(1) na každé z M vyhledávání, tedy celkově jsme se dostali na čas O(N + M). Paměti naše pole zabírá O(N).

Tato složitost zní hezky – vždyť je lineární, ale má to háček. N totiž není omezené velikostí vstupu. Mohlo by se stát, že v logu máme jen 2 různé uživatele, kteří mají ID 1 a 10⁹. Pak je vstup maličký, ale náš program spotřebuje řádově gigabajty paměti a přípravou pole stráví zbytečně mnoho času.

Zrychlení přečíslováním ID

Jak to opravit? Můžeme před zpracováním logů nejprve přečíslovat ID. Průchodem logu si uložíme do pole jednotlivá ID odesílatele i adresáta, která jsou na jednotlivých řádcích. Pak toto pole seřadíme. Seřazení pole vyřešíme v čase O(M log M) – v poli máme přesně 2M záznamů.

Máme nyní v ruce seřazené pole, které obsahuje všechna možná ID. Můžeme tedy každé ID přečíslovat na pozici jeho prvního výskytu v tomto poli. Jelikož je pole seřazená, můžeme tuto pozici najít binárním vyhledáváním. Přečíslování ID u jednoho řádku logu tedy zabere O(log M) času. Tím změníme N na 2M a můžeme použít řešení pro rozumně velké N, které bude potřebovat O(M) času i prostoru.

Chceme-li získat původní nepozměněné ID, stačí se podívat v poli na číslo na pozici přečíslovaného ID. Celý algoritmus s přečíslováním tudíž potrvá čas O(M log M) a spotřebuje paměť O(M).

Zrychlení množinou

Můžeme se dostat čas O(M log M) i tak, že pole v kvadratickém řešení nahradíme množinou. Ta umí rychle ukládat prvky a odpovídat, zda je prvek uložen. Zde budou prvky množiny jednotlivá ID. Pak místo hledání v poli se zeptáme, zda je ID v množině a místo přidávání ID na konec jej do množiny uložíme. Na konci pak z množiny vytáhneme (a seřadíme, pokud už nejsou seřazeny) všechny klíče.

Způsob, jak vytvořit množinu, je mnohem pokročilejší a zde jej uvádět nebudeme. Můžete si jej však přečíst v kuchařkách o binárních vyhledávacích stromech nebo hešování.