Čtvrtá série osmnáctého ročníku KSP

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

Řešení úloh

18-4-1 HP (Zadání)

Až na drobné výjimky všechna došlá řešení fungovala. Svůj podíl na tom má to, že úloha patřila k těm nejjednodušším ze série. Někteří řešitelé si však přesto počínali poněkud neohrabaně a zbytečně složitě, za což je pochopitelně neminula záplava komentářů v jejich řešení.

Jak tedy na věc? Nejprve si z jednotlivých dvojkových cifer zadaných na vstupu vyrobíme číslo, v paměti počítače reprezentované uvnitř integeru. V prvním kroku načteme do proměnné cislo první cifru. V druhém kroku vynásobíme cislo dvojkou a přičteme druhou cifru. V třetím kroku opět vynásobíme cislo dvojkou a přičteme třetí cifru, a tak dále. Nyní si stačí uvědomit, že to, co na závěr zbylo v proměnné cislo je skutečně správně načtené číslo ze vstupu. Tomuto jednoduchému algoritmu se také říká Hornerovo schéma. A nepotřebovali jsme k němu žádná pomocná pole plná předpočítaných mocnin, jak se snažili tvrdit někteří řešitelé.

Nyní zbývá zjistit počet nul na konci v desítkovém zápisu. To lze udělat například tak, že budeme cislo neustále dělit desíti tak dlouho, dokud končí na 0 (což zjistíme pomocí operace modulo 10), a za každé vydělení si zapamatujeme jedničku. Jak dlouho to celé poběží? Použijeme při tom, v tomto případě poněkud umělý, předpoklad, že všechny základní operace s integery probíhají v konstantním čase. Zjevně potřebujeme O(N) kroků na načtení a zpracování N bitů ze vstupu a stejně tak O(N) kroků na postupné dělení desíti, protože číslo může mít nejvýše tolik desítkových cifer kolik je jich dvojkových. Dle zadání se číslo vždy vejde do integeru, paměťová spotřeba tudíž bude konstantní. Pokud bychom však chtěli být naprosto přesní, museli bychom veškerou paměťovou složitost udávat v počtu použitých bitů, a stejně tak do času započítat dobu trvání elementárních operací (sčítání, násobení) nad několikabitovými čísly. Tak se to řeší ve formální teorii složitosti. My si tím však v této úloze nebudeme lámat hlavu.

Zdálo by se, že už můžeme skončit. Lépe než O(N) zjevně algoritmus nenavrhneme, vstupní bity musíme alespoň načíst. Konečně, taková řešení jsem bral jako naprosto správná. To bychom však nebyli my, abychom nepředvedli nějakou vychytávku. Ukážeme si řešení, které by pracovalo rychleji, pokud bychom číslo již měli načtené (a samozřejmě za předpokladu jednotkové ceny za elementární aritmetické operace).

Nejprve budeme postupně mocnit na druhou číslo 10 tak dlouho, dokud ještě bude dělit cislo, tedy najdeme maximální 102i, které dělí cislo. Správný počet nul na konci tedy bude ležet někde mezi 2i a 2i+1. K přesnému číslu se nyní dobereme upravenou metodou půlení intervalů. Zapamatujeme si 102i do m. Zkusíme, je-li cislo dělitelné m·102i-1. Pokud ano, nastavíme m na m·102i-1. A testujeme znovu, tentokrát je-li cislo dělitelné m·102i-2. To celé opakujeme, dokud i není 0.

První fáze bude trvat O(log N) kroků, neboť, jak už jsme si řekli, desítkových cifer je nejvýše tolik, kolik je dvojkových, a postupné mocnění na druhou tedy bude trvat maximálně logaritmický čas. Druhá fáze bude opět trvat logaritmicky vzhledem k počtu bitů, protože číslo i opět může nabýt maximálně hodnoty logaritmu z N. Výsledný výpis výsledku nás opět nezdrží, protože číslo udávající počet nul může mít samo maximálně O(log N) cifer. Celkem tedy čas O(log N). A pokud si budeme počínat šikovně, vystačíme si pouze s konstantní pomocnou pamětí. Konečně, pro detaily viz vzorový program.

Program

Tomáš Valla

18-4-2 Elektronické hrátky (Zadání)

Malý Martínek vám děkuje za došlá řešení. Moc mu pomohla. Jen byl nejprve trochu zmaten odlišným přístupem řešitelů. Někteří z vás se do problému pustili zepředu a výpočet prováděli od vstupních bitů průchodem grafu do šířky. Ostatní na to šli od lesa (tedy odzadu) a procházeli graf do hloubky od výstupních bitů. Avšak který postup je lepší? Trochu se nad oběma postupy zamysleme. Hradlová síť je zadána tak, že reference vedou směrem „zpátky“ (tedy ke vstupním bitům). Procházení od posledních (výstupních) bitů nám tedy nebude činit žádné potíže, ale opačný přístup si vyžádá předzpracování, při kterém "otočíme" reference (nebudeme si pamatovat kam jsou zapojeny vstupy jednotlivých hradel, ale zapamatujeme si, kam je zapojen výstup). Procházení odzadu je tedy výhodnější, protože nevyžaduje žádné předzpracování (byť bychom jej prováděli při načítání sítě). Procházení do hloubky od výstupu bude mít navíc tu výhodu, že spočítáme opravdu jen ta hradla, která budeme potřebovat, zatímco při procházení do šířky spočítáme úplně všechno a pak se nám může stát, že hodnoty výstupů některých hradel nebudeme vůbec potřebovat.

Náš algoritmus bude obsahovat funkci, která se zavolá na určité hradlo a spočítá jeho výsledek tak, že se rekurzivně zavolá na obě „předchozí“ hradla (to jsou hradla, na jejichž výstup jsou zapojeny moje dva vstupy) a z jejich výsledků spočítá operací NAND vlastní výsledek. Ano Ondro, vidím, že se hlásíš a chceš nám říci, že tenhle algoritmus by měl exponenciální časovou složitost. Inu ono to nebude tak docela pravda, ale každopádně nebude příliš efektivní, protože bude počítat výstupy některých hradel vícekrát. Tento problém vyřešíme jednoduše tak, že si budeme hodnoty již spočtených hradel pamatovat. Naši rekurzivní funkci pak zavoláme pro každé hradlo, jehož výstup je zapojen na výstupní bit celé sítě.

Jakou to bude mít časovou složitost? Náš algoritmus je v podstatě speciální variantou procházení grafu do hloubky (DFS), tudíž jeho složitost je O(M + N), kde N je počet vrcholů (v našem případě hradel) a M je počet hran. Naštěstí víme, že každé hradlo má právě 2 vstupy, tudíž počet hran bude roven dvojnásobku počtu vrcholů. Složitost pro jeden dotaz je tedy O(2N + N), což je totéž jako O(N). Graf budeme procházet pro každý dotaz úplně znovu, takže toto je časová složitost jednoho dotazu. Předzpracování si nevyžádá žádný čas a paměti spotřebujeme také pouze lineárně mnoho.

Ještě dvě poznámky ke vzorovému programu:

Program

Martin 'Bobřík' Kruliš

18-4-3 Běh městem (Zadání)

Tajemník by byl určitě zklamaný, neboť prakticky všechna došlá řešení byla málo Kocourkovská a fungovala správně. Bohužel ne vždy bylo z řešení zřejmé, proč by tomu tak mělo být.

Město si můžeme představit jako souvislý graf, jehož vrcholy jsou křižovatky a ulice jsou hranami. Řešením pak je graf vzniklý z původního zorientováním jeho hran. Co takový graf musí splňovat?

  1. Z každého vrcholu musí existovat alespoň jedna cesta vedoucí do cíle
  2. V grafu nesmí být kružnice, aby se závodník nemohl zacyklit
A jak vypadá algoritmus, který vyhovující řešení najde? Nejjednodušší je graf projít do šířky nebo do hloubky směrem od cíle a u každého vrcholu si zapamatovat, v kolikátém kroku jsme ho navštívili. Nakonec projdeme všechny hrany a zorientuje je tak, aby vedly vždy z vrcholu s vyšším pořadovým číslem do vrcholu s číslem nižším. Podmínka (i) je tak splněna, neboť každá cesta je posloupnost vrcholů s klesajícím pořadím a platí, že libovolný vrchol kromě cíle má souseda s nižším číslem. To je zřejmé z toho, jak jsme grafem procházeli. Cíl je vrchol s nejnižším pořadovým číslem, a proto v něm všechny cesty musí končit. Podmínka (ii) je rovněž splněna, neboť každá cesta obsahuje vrcholy v klesajícím pořadí a taková cesta nemůže být uzavřená.

A jak vypadá implementace? Ve skutečnosti si nemusíme žádná čísla pamatovat, stačí, když pro dva vrcholy dokážeme určit, který z nich má menší pořadové číslo. Když jsme dospěli do nějakého vrcholu a procházíme všechny hrany z něj vedoucí, pak vrchol na druhém konci buď již navštíven byl a má tak pořadové číslo jistě nižší, nebo ještě navštíven nebyl. Potom bude jeho pořadové číslo zákonitě vyšší.

Je tedy možné hrany orientovat již během prvního průchodu a dokonce jejich orientaci ihned vypisovat tak, že vypisujeme pouze nově zorientované hrany. Přičemž nově zorientované hrany vždy směřují do zpracovávaného vrcholu. Hrany z něj vycházející totiž byly zorientovány již před jeho zpracováním. A to je celé.

Časová i paměťová složitost algoritmu je zřejmě O(N+M), kde N je počet křižovatek a M je počet ulic. Program implementuje prohledávání do šířky a pro zpestření jsou seznamy následníků vrcholu reprezentovány spojovými seznamy, aby paměťová složitost byla opravdu O(N+M).

Program

Zbyněk Falt

18-4-4 Metro pro krtky (Zadání)

Ukončete nástup, dveře se zavírají.

Vítejte v krtčím metru. Naši krtečci byli velmi potěšeni, protože všichni poslali funkční řešení. Bohužel u velké části z vás by krtečci už pro několik desítek tisíc krtin (což je při třiceticentimetrových krtincích těsně vedle sebe krtčí Stonehenge o průměru pouhopouhý kilometřík) značně zešedivěli. I přesto vaše řešení v O(N2) získala až 6 bodů, protože krtčí správa v městečku Jablonec nad Krysou s nimi byla spokojena. Ovšem naše cíle jsou vyšší. Ano, míříme až do krtkopolis Krtečkov. A tady se s ničím menším (větším) než O(N log N) nespokojí.

Ale jak jen docílit této mety nejvyšší (nejnižší)? Představme si tunely jako intervaly omezené úhlem krtin. Abychom si situaci ulehčili, budeme za levý okraj považovat menší z obou hodnot. Díky tomu si můžeme kružnici v nule přestřihnout, aniž bychom tak rozdělili nějaký interval na dva (to si rozmyslete!), a nahradit ji úsečkou od 0° do 360°. Úlohu jsme si tím změnili na nalezení počtu průniku intervalů na úsečce.

Vezměme si interval s nejmenším levým okrajem. V tomto intervalu mohou ostatní tunely začínat nebo začínat a končit, ale hlavně v něm nemohou pouze končit. Proč? Kdyby v něm nějaký interval pouze končil, tak by musel mít počáteční krtinu ještě před tímto intervalem, ale to je spor, protože ten byl vybrán právě proto, že je jeho levý okraj nejmenší.

Našim cílem je tedy spočítat, kolik tunelů v tomto intervalu začíná a zároveň nekončí. To je možné třeba tak, že spočteme, kolik jich tam začíná, a od tohoto počtu odečteme, kolik jich tam končí. To vede na pěkné kvadratické řešení. Nebo ne?

Setřiďme si krtiny podle úhlu od nejmenší. Nyní v takto setříděném poli prohlašme krtinec tunelu s menším úhlem za počáteční, naopak s větším úhlem za koncový. Pokud si počátky označíme 1 a konce -1 tak si povšimněte, že součtem čísel na určitém úseku získám, o kolik je v daném úseku více nebo méně počátků než konců. Například pokud zde začne 9 tunelů a jen 5 skončí je součet čísel na daném úseku 4. Doplňme si počet krtin na nejbližší mocninu dvojky (nulami, tím nic nezkazím) a vystavme nad nimi binární strom a to tak, že v každém uzlu bude součet jeho levého a pravého syna. Jen tak mimochodem si uvědomte, že v kořeni tohoto stromu musí být 0. Navíc si pro každý začátek tunelu pamatujme, kde je umístěn jeho konec. V takovémto stromu je jednoduché jedním průchodem z listu, ve kterém je umístěn konec tunelu, do kořenu najít součet prvků nalevo nebo napravo od něj.

Tím jsme vyřešili první tunel, ale co ten druhý? Třetí? Chtělo by to první odebrat. Ale to je snadné, na umístění jeho krtin dáme nuly a strom opět, tentokrát dvěma průchody (za každou krtinu jeden) opravím. Obě tyto operace mají složitost O(log N). Tím se druhý tunel stane prvním a vše může pokračovat.

Teď ještě pár slov k těmto dvěma operacím. Začneme opravením. Nejprve změním daný list na nulu. Pak skočím do jeho otce a přiřadím mu součet jeho synů. Tím se opět změnila jeho hodnota a tak opět skočím o úroveň výš. To budu opakovat dokud nedojdu do kořene. Trochu složitější se mi zdá zjištění počtu počátečních a koncových krtin. Představte si nyní nějakou (pokud možno hodně klikatou) cestu z listu ke kořeni. To co my chceme získat, je součet všech listů nalevo od našeho. Teď se posuňme o úroveň výš. Mohly nastat dva případy

  1. do otce jsme přišli zleva. Tak nic neřešíme, protože pravý list obsahuje jistě součet (nějakých) listů napravo od našeho.
  2. do otce jsme přišli zprava. To je mnohem zajímavější, v tom případě navýšíme počítadlo o hodnotu levého syna, protože je to součet úseku vlevo od našeho listu. Pokud si navíc nakreslíte obrázek, tak krásně uvidíte, že tento postup skutečně pokryje celý interval vlevo od našeho vrcholu.
Výsledek v počitadle získáme v O(log N), protože v každém kroku skočíme o úroveň výš, ve stejném čase také opravíme strom. Protože tyto operace provedeme N/2-krát (tolik je počátečních krtin), je celková složitost O(N log N). Paměti potřebujeme na stromeček a umístění konců pouze lineárně mnoho, takže O(N). Samozřejmě časová složitost je vzhledem k použití QuickSortu jen průměrná, ale použitím jiného sortu bychom si ji zajistili.

Ukončete výstup, dveře se zavírají.

Program

Jan Bulánek

18-4-5 Datokopci (Zadání)

Nejprve bylo dobré povšimnout si, že protože každá zpráva bude doručena (to plyne přímo ze zadání – každý dopravník buď vede přímo do redakce nebo pokračuje pásem na sousedním políčku, který vede stejným směrem), stačí nám pamatovat si rozdíl počtu dobrých a špatných zpráv s tím, že znaménka množství doručených na severní okraj obrátíme. Také nám hodně pomůže fakt, že hranice mezi S-J a Z-V pásy bude lomená čára začínající v severozápadním (levém horním) rohu, vedoucí pouze na jih a východ a končící v jihovýchodním (pravém dolním) rohu. Jižně a západně od ní leží dopravníky ženoucí se na západ do redakce pohádek, na sever a západ ty vedoucí na sever do redakce zpravodajství. Proč nemůže mít i nějaký ten záhyb na sever či západ? Zprávy z něj by se už určitě nedostaly a to je zakázáno. Zkoušet všechny tyto dělící cesty není dobrý nápad, je jich totiž nn/n!, ačkoliv by to byla teoretická možnost.

My úlohu vyřešíme lépe a to dynamickým programováním. Jakkoli hrozně vám některým může tento pojem znít, jde vlastně jen o to, že si pro každý řádek pro všechna k=0… n postupně spočtu, jaký nejlepší výsledek mohu dostat, pokud v něm vede právě k dopravníků na západ a zbylé na sever. Pro první řádek to zjistíme snadno a pro j+1-ní to závisí pouze na optimech pro j-tý řádek – když potřebuji zjistit optimum pro situaci, kdy k dopravníků vede na západ, vyzkouším to zkombinovat se situacemi, kdy dělící cesta pokračuje o řádek výše v pozici 0,1,2,… ,k. Toto stihnu mnohem rychleji – kombinací kj+1 s možnými kj je O(n2), každý z přepočtů mi bude trvat O(n) a toto udělám pro O(m) řádků, celkem tedy O(n3m) nebo O(m3n) pokud bych se místo po řádcích rozhodl jít po sloupcích, což by byla stejná jen zrotovaná úvaha.

Zkusme to ale zlepšit. Toho, že toto spočteme pro O(m) řádků se nezbavíme, zrychlíme ale jednotlivé řádky. První zrychlení dosáhneme předpočítáním částečných součtů zleva na jednotlivých řádcích (při jeho rozdělení v jednotlivých místech by nám řádek vynesl ∑
k
i=1
di-∑
n
i=k+1
di= 2∑
k
i=1
di-∑
n
i=1
di=2sk-konst., konstantu nezávisející na místě rozdělení mohu ignorovat a počítat jen s 2sk a to klidně polovičním. Tímto si trochu zjednoduším počítání sk), když už si totiž vybereme konkrétní kj a kj+1, je nové optimum jen součtem tohoto částečného součtu skj+1 a optima na kj v minulém řádku. Tímto jsme dosáhli O(n2m) (předpočítat částečný součet umíme v čase O(n) na řádek).

Další a poslední zlepšení: při zkoušení optimálního pokračování dělící cesty o řádek výše vždy vybereme maximum z možných mezivýsledků. Toto nalezené maximum pro kj+1 si ale můžeme schovat pro kj+1+1 (další políčko na řádce) a jen ho třeba zlepšit na skj+1, pokud je větší. Tento malý trik nám zlepší složitost až na O(mn). Nejen, že už nezáleží na tom, zda jdeme po sloupcích či řádcích, navíc jsme určitě dosáhli optima – na každou hodnotu musíme v libovolném fungujícím algoritmu sáhnout alespoň jednou, mohlo by se tam ukrývat nějaké velmi velké množství pohádek, o které přece nechceme přijít…

Paměťová složitost je O(mn).

Program

Tomáš Gavenčiak

18-4-6 Komplikátorový fígl (Zadání)

Jedním z možných řešení této úlohy bylo použít algoritmus popsaný v řešení úlohy 18-3-6 a modifikovat ho pro práci nad SSA formou. Existuje ovšem přímočařejší řešení – vyjdeme z definice živého kódu.

Výraz je živý, pokud má nějaké vedlejší efekty, nebo pokud je jeho hodnota použita v živém výrazu. Představme si následující orientovaný graf: jeho vrcholy budou příkazy v programu. V grafu bude hrana z příkazu p1 do příkazu p2, pokud p1 používá hodnotu vypočtenou v příkazu p2, tedy pokud p2 je buď přiřazení x = expr, nebo x = phi(…), a příkaz p2 používá proměnnou x. Vrcholy odpovídající příkazům s vedlejšími efekty si označíme. Pak příkaz je živý právě tehdy, pokud do jemu odpovídajícímu vrcholu vede cesta z některého z označených vrcholů. Toto je ovšem dobře známá úloha na dosažitelnost v grafu, kterou můžeme vyřešit například procházením grafu do hloubky (viz třeba kuchařku z druhé série). Algoritmus tedy může vypadat zhruba takto:

pro každý příkaz p:
     if p má vedlejší efekty then
          označ p a ulož ho na zásobník

while zásobník není prázdný do
     odeber ze zásobníku příkaz (p)
     pro všechny proměnné x použité v p:
          buď q příkaz, který definuje x
          if q není označený then
               označ q a přidej ho do zásobníku

pro každý příkaz p:
     if p není označený then
          smaž p

V algoritmu využíváme toho, že x je definováno jen jedním příkazem, a tedy nemusíme zjišťovat, které z definic odpovídají danému použití. Pro každý příkaz v programu si musíme pamatovat značku a mít pro něj místo na zásobníku, tedy paměťová složitost je lineární. Každý příkaz se dostane do zásobníku nanejvýš jednou, proto je časová složitost také lineární.

Zdeněk Dvořák