Pátá série dvacátého prvního ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 21-5-1: Polomáčené mrakodrapy
- 21-5-2: Banky
- 21-5-3: Krávy
- 21-5-4: Zákony
- 21-5-5: Cestovní šavle
- 21-5-6: Kržnc
21-5-1 Polomáčené mrakodrapy (Zadání)
Očekávali jsme více správných řešení – na rozdíl od minulé úlohy si tato úloha žádala spíše selský rozum než algebraické triky.
Z úlohy bylo patrné, že všechna maxima byla příliš velká na to, aby mělo triviální kvadratické řešení jakoukoli šanci. Stejně tak rozsah velikostí věžáků a rozsah dnů, na které mohl být položen dotaz, byl příliš velký, než aby s ním šlo dělat cokoli rozumného.
Nicméně si lze všimnout, že zde pracujeme jen s tisícinou položek z celého rozsahu. Zkusíme si tu množinu tedy předzpracovat, aby se nám s ní lépe pracovalo.
Způsob, který si popíšeme, využívá zajímavého panelákového pozorování: jediné budovy, které zvyšují nebo snižují počet ostrůvků ve městě, jsou ty, které jsou „lokálními extrémy“ – jinak řečeno, jsou to takové budovy, jejichž oba sousedé jsou buď zároveň větší nebo menší než ona sama. Když totiž uvážíme posloupnost rostoucích (nebo klesajících) paneláků, voda je postupně zaplavuje jeden po druhém a počet ostrovů se nezmění. Navíc si všimneme, že „vršek“ po zatopení od počtu ostrůvků odečte sám sebe (právě se zatopil), zatímco „údolí“ po zatopení oddělí svou levou a pravou část, a tedy jeden ostrůvek přibude.
Výška budovy přesně určuje den, kdy se pričte nebo odečte jednička z výsledku. Zjistit o každém domě, zda je „vrškem“ či „údolím“, zvládneme jedním průchodem vstupními daty. Při tomto průchodu si tedy rovnou budeme ukládat neuspořádaně dvojice (Den, Změna), kde Den bude výška domu, který procházíme a Změna bude +1 nebo -1, podle toho, jakého typu byl onen dům.
Nyní začneme ze vstupu načítat (velice příhodně setříděné) dny a budeme podle +1 a -1 upravovat aktuální hodnotu. Abychom toto mohli dělat rychle, stačí si naše pomocná data setřídit podle hodnoty Den vzestupně (postačí i rychlý kvadratický algoritmus jako Quicksort) a pak obě pole procházet naráz.
Paměti nám stačilo lineárně mnoho, dokonce jsme využili jen jedno pole celých čísel (+1 bit, ale ten bychom dovedli zakódovat i dovnitř) o velikosti N. Pokud jsme nepoužili žádné „nefér“ praktiky jako přihrádkové třídění, pak nám celý algoritmus seběhl v čase O(N log N), respektive O(N2) (s rychlým kvadratickým tříděním).
Na závěr doporučujeme všem řešitelům praktických úloh, pokud používáte libovolný jazyk vyjma Pascalu, pak tento jazyk obsahuje zabudovanou třídící knihovnu, která pro velkou většinu vstupů bude alespoň tak rychlá jako libovolný algoritmus, který napíšete. Když ji budete používat (v praktických úlohách), tak nic nezkazíte a navíc si ušetříte spoustu písmenek a potenciálních chyb.
21-5-2 Banky (Zadání)
Z došlých řešení je zřejmé, že vetšina řešitelů nemá ráda chamtivé bankéře. Značná část z vás se je pokoušela zmást nesprávnými výsledky. Někteří pravděpodobně měli v plánu zopakovat Chuliův trik, a tak bance nabídli velmi líné programy, aby měli dostatek času na přípravu a provedení svých plánů. A jen pár jedinců překonalo svou nevoli vůči finančníkům a předvedli nejen funkční, ale i rozumně rychlé algoritmy. A jak že vůbec našel díru v systému Chulio? Podívejte se sami:
Systém převodů měn je vlastně orientovaný ohodnocený graf. Jednotlivé měny jsou vrcholy a pokud mezi dvěmi měnami existuje převodní kurz c, tak mezi odpovídajícími vrcholy existuje orientovaná hrana s ohodnocením c. Posloupnost převodů, která je pro banku prodělečná, odpovídá v grafu orientovanému cyklu s hranami e1, e2, …, ek, ve kterém je součin ohodnocení těchto hran větší než jedna, tedy
Zadaná úloha se dost podobá úloze hledání cyklu, který má součet ohodnocení hran záporný, pro kterou je známý rychlý algoritmus. Na ni naši úlohu převedeme tak, že výše uvedenou nerovnici zlogaritmujeme a vynásobíme -1:
Každou hranu e tedy místo c(e), což je převodní kurz mezi odpovídajícími měnami, ohodnotíme - log c(e). Toto nové ohodnocení budeme pro zjednodušení následujícího textu nazývat délkou hrany a délka sledu pak bude součet délek jeho jednotlivých hran. (Sled je posloupnost vrcholů taková, že mezi sousedními vrcholy sledu vede v grafu hrana ve správném směru. Na rozdíl od cesty se v něm mohou opakovat jak vrcholy, tak hrany.)
V upraveném grafu zjišťujeme, jestli tam existuje cyklus (sled, který má první a poslední vrchol stejný) záporné délky. Jak na to? Použijeme Bellman-Fordův algoritmus, který hledá nejkratší sledy z nějakého vrcholu u do všech ostatních. Funguje tak, že si pro každý vrchol pamatuje délku zatím nejkratšího nalezeného sledu z u do něj. V každém kroku pro každou hranu vw určí, jestli není součet délky zatím nejkratšího nalezeného sledu z u do v a délky hrany vw menší, než zatím nejkratší nalezený sled z u do w. Pokud ano, tak ji na tuto délku sníží. Na začátku nastavíme vzdálenost u na nulu a všech ostatních vrcholů na ∞.
Po provedení i-tého kroku budeme znát pro každý vrchol délku nejkratšího sledu obsahujícího nejvýše i hran z u do tohoto vrcholu. Pokud z vrcholu u není dosažitelný žádný cyklus záporné délky, tak nejpozději po n-1 krocích (n je počet vrcholů grafu) najde algoritmus pro každý vrchol nejkratší sled z u (každý z těchto sledů bude cesta) a pokud provedeme ještě n-tý krok, tak proběhne „naprázdno“, tj. nenajde žádný nový kratší sled. Pokud graf obsahuje cyklus záporné délky dosažitelný z u, tak v každém kroku (a tedy i v n-tém) najde nějaký nový kratší sled.
Zbývá ještě vymyslet, který vrchol zvolíme za počáteční vrchol u. Vzhledem k tomu, že nemusí existovat žádný vrchol, ze kterého by byly dosažitelné všechny ostatní, bude u nový vrchol, ze kterého povedou hrany do všech ostatních, jejich délku zvolíme třeba nulovou. Protože do nového vrcholu nevedou žádné hrany, nepřidali jsme do grafu žádný cyklus a výsledek jsme tedy nezměnili. Kromě prvního kroku můžu hrany vedoucí z u a tedy i samotný vrchol u, ignorovat, protože určitě nezpůsobí změnu vzdálenosti žádného vrcholu. Naopak v prvním kroku stačí počítat jen s hranami vedoucími z u. Protože po prvním kroku budou mít všechny vrcholy vzdálenost nulovou, nemusím v programu ani vrchol u ani hrany z něj vedoucí nijak reprezentovat a stačí jen nastavit vzdálenost všech vrcholů na nulu.
Nakonec si uvědomíme, že převod kurzů na délky, který jsme provedli na začátku, je vlastně zbytečný a můžeme tedy počítat přímo s kurzy. Pro každý vrchol si budeme pamatovat prozatím nejlepší (maximální) kurzový součin na sledu z u a kurzový součin ve vrcholu w budeme upravovat, pokud je menší než součin kurzového součinu vrcholu v a kurzu hrany vw. Kurz na hranách z u můžeme nastavit třeba na jedničku (a ve zkrácené podobě prvního kroku teda nastavit všem vrcholům kurzový součin na jedničku).
V prvním kroku jen nastavíme hodnotu kurzového součinu všem vrcholům. V každém dalším kroku projdeme všechny hrany a pro každou provedeme O(1) operací. Celková časová složitost tedy je O(n+nm) = O(nm), kde n je počet vrcholů a m je počet hran v grafu. V paměti máme informace o každé hraně a vzdálenost každého vrcholu, takže paměťová složitost je O(n+m).
21-5-3 Krávy (Zadání)
Naším úkolem je přehradit všechny krávy v kravíně Z závorami, aby součet jejich délek byl minimální. Na tento problém se dá koukat dvěma způsoby.
První způsob: Na začátek si představme, že před každou krávou je jedna závora o délce jeden telemetr. Pokud je počet použitých závor rovný nebo menší zadanému číslu Z, jsme s problémem hotovi. Pokud jsme ale použili víc závor, než můžeme, musíme některé sousední závory „spojit“, čímž se nám sníží počet použitých závor o jedna. Protože součet délek závor má být minimální, spojujeme vždy co nejkratší úsek mezi kravami, až bude počet použitých závor rovný Z. Proč tento způsob funguje? V první řadě si musíme uvědomit, že každá kráva musí být ohrazena. Takže pokud jsme měli dostatek závor, je naše začáteční rozmístění určitě minimální. Pokud ale dostatek závor nemáme, musíme nutně jednou závorou přehradit více krav. No a jedné závory se zbavíme tak, že spojíme dvě sousední závory, čímž ale přehradíme taky mezeru mezi nimi. Proto je nejvýhodnější v každém kroku spojit závory s co nejkratší mezerou mezi sebou (mezera mezi sousedícími závorami má délku 0).
Druhý způsob: Na problém se ale můžeme dívat i z jiného hlediska. Mějme na začátku jednu dlouhou závoru přes celý kravín. Na začátek ořežeme kus před první a po poslední krávě. Pak už jen zbývá najít Z-1 nejdelších mezer mezi kravami, a když je „vyřežeme“, zbyde nám Z závor, a jejich celková délka je určitě minimální. Proč i tento způsob funguje? Začáteční ohrazení je určitě korektní. Taky ořezání kusu před první a za poslední krávou řešení nepokazí. Takže máme všechny krávy ohrazené, ale je možné, že nám zbyly nějaké závory. No a z jedné závory udělám dvě tak, že z ní „vyřežu“ nějaký kus ze středu. A aby byl součet délek nových dvou závor minimální, musím vyřezat co největší kus. Tento kus ale nesmí obsahovat žádnou krávu, protože by už nebyla ohrazena. Takže se snažím najít co největší kus, který neobsahuje žádnou krávu, což je přesně to, že se snažím najít co největší mezeru mezi kravami, která ještě nebyla vyřezaná. No a protože mám Z závor, tak si můžu dovolit vyřezat až Z-1 kusů, no a tyto kusy musí být co největší.
Nechť vstup vypadá následovně: Na začátek jsou mezerami oddělená čísla N K Z, a pak následuje K čísel, které značí pozice krav v kravíně. Pro jednoduchost ať jsou pozice seřazeny vzestupně. Takže teď nám jenom zbývá najít K-Z nejkratších, případně Z-1 nejdelších mezer mezi kravami. Rozeberme třeba hledání Z-1 největších. To můžeme udělat několika způsoby:
1. Všechny mezery setřídit podle velikosti a vybrat Z-1 největších. Tento způsob má při použití třídícího algoritmu QuickSort časovou složitost O(K log K) a paměťovou O(K). Více informací o QuickSortu naleznete v Kuchařce 21-2 Rozděl a panuj.
2. Postupně načítat pozice krav, vždy spočíst mezeru a za použití struktury halda vybrat Z-1 největších. Halda je binární strom, kde pro každý prvek platí, že je menší než jeho následníci. Pro více podrobností viz Kuchařka 20-4 Halda, heapsort a Dijsktrův algoritmus. Stručně se algoritmus dá popsat následovně: Na začátek zatřídíme prvních Z-1 mezer do haldy. Pak vždy když načteme nový neobydlený úsek, porovnáme jeho délku s minimem na vrcholu haldy. Když je délka menší nebo rovna, úsek zahodíme, protože ostatní délky úseků v haldě jsou zjevně taky větší nebo rovny. Když je ale současný úsek delší než minimum v haldě, tohle minimum vyhodíme, a zařadíme nový prvek do struktury. Na konci nám zůstane halda, ve které máme Z-1 největších úseků mezi kravami. Tento algoritmus běží v časové složitosti O(K log Z) a paměťové O(Z).
3. Nejrychlejší způsob - použijeme algoritmus na hledání K-tého nejmenšího prvku z Kuchařky 21-2 Rozděl a panuj. V našem případě jenom otočíme nerovnosti a budeme hledat (Z-1)-ní největší prvek. Tenhle algoritmus nám během počítání generuje rovnou všechny větší prvky, které sice nejsou vzájemně setříděné, ale to nám nijak nevadí. Tento algoritmus má časovou i paměťovou složitost O(K).
21-5-4 Zákony (Zadání)
Ze spleti zákonů a soudních pří by se ti z vás, co se o to pokusili, nakonec vymotali, leč většinou by Chosému nechali dostatek času na složení šavle a museli by k ujasnění sporu o farmu (a Ochechulínu) využít jiných prostředků.
Při řešení úlohy si nejdříve můžeme všimnout, že ji lze přeformulovat ještě tak, že z lesa chceme dostat libovolně (nekonečně) malou kouli (tedy vlastně bod), ale mezi dvojice zákonů, které jsou si blíže než 2R, postavíme zeď. Máme tedy zadány vrcholy grafu, jen potřebujeme zjistit, mezi kterými vedou hrany, a nakonec se podívat, zda je naše výchozí pozice uvnitř nějakého cyklu.
Pokud bychom se spokojili s kvadratickým časem, stačí pro nalezení hran jednoduše vyzkoušet všechny dvojice vrcholů. Nepříjemné je, že rychleji to ani nejde, neboť až kvadratický může být počet hran, které chceme najít; pročež nezbývá než si graf trochu upravit.
Pro jednoduchost budeme dále předpokládat, že počáteční pozice je v bodě (0,0) a zadaný poloměr roven 2 (jinými slovy, přepočítáme souřadnice tak, aby to platilo). Rozdělíme si celou rovinu na čtverce se stranou 2 tak, aby počátek ležel v rohu nějakého z nich. Body uvnitř každého z těchto bloků jsou pak vždy všechny spojené hranou (tvoří úplný podgraf) a můžeme je sloučit do jednoho se souřadnicemi středu čtverce. Musíme si jen dát pozor, když takto slučujeme hrany, které procházejí kolem počátku z různých stran (přesněji to můžou být ty, které protínají kladnou poloosu y, a ty ostatní); v takovém případě zřejmě z lesa zákonů uniknou nemůžeme. Nicméně to vyřešíme později a prozatím předpokládejme, že k tomu nedojde.
Nový graf má až N vrcholů (s celočíselnými lichými souřadnicemi; bloky ale podle nich indexovat nemůžeme, neboť kombinací souřadnic může být až kvadraticky, proto je podle souřadnic budeme mít jen lexikograficky uspořádané a v případě potřeby binárním půlením v logaritmickém čase najdeme blok pro dané souřadnice, nebo zjistíme, že tam žádný není; to bude potřeba jen konstantně-krát pro každý blok), ale každý vrchol může mít nejvýše 24 sousedů, takže počet hran je již nejvýše lineární, jen jejich nalezení bude o něco složitější. Hrana mezi dvěma bloky vede právě, když z nich lze vybrat dva vrcholy (každý z jednoho), mezi nimiž je vzdálenost menší než 4.
Máme tedy vždy dvě množiny bodů (A a B) oddělené nějakou přímkou (bez újmy na obecnosti to budiž osa y) a chceme najít dva body takové, že jejich vzdálenost je nejmenší možná. Všimněme si, že podíváme-li se na průsečík jejich spojnice a osy y, musí mu být oba body blíž než libovolný jiný z jejich skupiny. Pro každý bod na ose y si tedy určíme, který bod z A a který z B je mu nejblíže. To uděláme tak, že si body ve skupině setřídíme podle y-ové souřadnice a v tomto pořadí je budeme přidávat a hledané údaje postupně upravovat: na začátku máme jeden bod, který je nejblíže všem bodům osy y; kdykoli přidáme další, podíváme se, kterým bodům osy y bude blíže než bod předchozí (třeba tak, že najdeme průsečík osy jejich spojnice s osou y) a pokud na ten už žádné nezbudou, odstraníme jej a porovnáme nový bod s jeho dalším předchůdcem atd., jinak pokračujeme přidáváním. Po setřídění nám na toto stačí lineární čas, neboť každý bod jednou přidáme a porovnáváme s předchůdcem bez odstraňování a nejvýše jednou odstraníme. Pak už zbývá jen projít osu y a pro každý bod porovnáme dvojici bodů, které jsou mu z každé ze skupin nejblíže (přesněji, projdeme ji po úsecích, kde se tato dvojice nemění). Pokud najdeme nějakou dvojici, která je blíže než 2R, zapamatujeme si navíc, jestli protíná kladnou poloosu y.
Spojení bloků (-1,-1) s (1,1) a (-1,1) s (1,-1) – to jsou jediná, která mohou sdružovat hrany vedoucí z různých stran kolem počátku – vyřešíme speciálně: budeme chtít vědět nejen, jestli jsou spojeny, ale také z jaké strany (případně že z obou) to spojení vede. Opět máme dvě množiny A a B a body v nich setříděné podle nějaké ze souřadnic. Pokud je některá prázdná nebo obě jednoprvkové, je řešení triviální, jinak si vybereme nějaký bod m a rozdělíme obě množiny na body, které (když si je představíme jako vektory) mají směrnici menší než m (množiny A1 a B1) a ty zbylé (A2 a B2). Zřejmě dvojice A1–B2 může být spojená jen jedním typem hran, obdobně A2–B2; kterým a jestli spojené jsou, můžeme zjistit výše popsaným způsobem v lineárním čase. Nalezení spojení mezi A1–B1 a A2–B2 je pak původní problém na menších množinách. Aby se nám rekurze zastavila brzy, konkrétně po O(log N) iteracích, potřebujeme dané množiny rozdělovat rovnoměrně, nejlépe půlit, k tomu je potřeba, aby m byl mediánem některé z nich v uspořádání podle směrnic; ten můžeme nalézt v lineárním čase (jak na to se lze dočíst v letošní kuchařce ze druhé série), takže celý postup zabere čas O(N log N).
Nakonec už jen zbývá projít celý vytvořený graf a podívat se, zda je počátek uvnitř nějakého cyklu v něm. Zjistit, zda je nějaký bod vnitřním bodem polygonu, lze třeba tak, že pošleme „paprsek“ z tohoto bodu libovolným směrem a spočítáme, kolik hran tuto polopřímku protne – pokud jich bude lichý počet, je bod uvnitř, jinak vně. Tím paprskem bude kladná poloosa y, průsečíky s níž už máme předpočítané. Začneme v libovolném vrcholu (bloku), graf budeme procházet do hloubky a přitom si počítat, kolikrát jsme paprsek protli, jakmile narazíme na vrchol, který jsme už viděli (tedy cyklus), jednoduchým rozdílem těchto hodnot z této a předchozí návštěvy zjistíme, zda se počátek nachází uvnitř mnohoúhelníku z hran cyklu. Nemusíme si ani pamatovat počty průsečíků s paprskem, neboť nás zajímá jen parita.
Nalezení hran grafu bloků včetně potřebného třídění zvládneme v čase O(N log N) a na jeho prohledání stačí čas lineární a lineární je i velikost spotřebované paměti.
21-5-5 Cestovní šavle (Zadání)
Taková cestovní šavle je pěkně zapeklitá záležitost, při skládání si totiž nemůžeme být jisti, jestli zrovna tento dílek už máme složit, anebo ho ještě nechat narovnaný.
Mějme pouzdro délky L a do něj bychom chtěli složit šavli z N dílů. Řešení, které asi napadne každého, je vždy zkusit obě možnosti. Dílek nejdříve zkusíme složit a přesuneme se na zbylé dílky. Když se nám je žádným způsobem nepovede složit do pouzdra, tak se vrátíme, původní dílek zkusíme nechat narovnaný a opět stejný postup použijeme na zbylé dílky. Pokud ani tato cesta nevede k cíli, pak šavli nejde složit. Algoritmus má ovšem exponenciální časovou složitost O(2N).
Naivní algoritmus je exponenciální, protože se v něm spousta kroků opakuje. To z této úlohy dělá problém typický pro řešení pomocí dynamického programování. Pusťme se tedy do něj. Téměř vše, co budeme potřebovat, je pole délky L+1. To bude po k-té fázi obsahovat značky právě tam, kde všude může prvních k dílků končit.
Fází výpočtu tak bude celkem N. V každé budeme zpracovávat jeden dílek. Projdeme celé pole a od místa, kde by mohl končit dílek předchozí (tzn. v poli na indexu i máme značku) zkusíme přidat dílek nový. Na počátku máme značku ve všech prvcích pole, protože umístění začátku prvního dílku není ničím omezeno. Konec nově přidaného dílku pak může být na indexech i-d a i+d, kde d je jeho délka. Samozřejmě, že nový konec musí být v mezích pole. Povede-li se nám najít alespoň jeden možný konec pro všechny dílky, tak víme, že šavli složit jde.
Pokud bychom používali pouze jedno pole, budou se nám plést nově přidané značky se značkami z minulé fáze. Je tedy nutné mít pole dvě. Z jednoho budeme číst a do druhého si budeme připravovat značky pro další fázi. Po každé fázi pole navzájem vyměníme. Dobrý nápad je také mít pro každou fázi jinou značku(např. číslo fáze), díky tomu nebudeme muset před každou fází druhé pole nulovat.
Pro každý dílek projdeme celé pole, takže zjištění, jestli šavle složit jde, bude mít časovou složitost O(N ·L) a paměťová složitost bude O(L).
21-5-6 Kržnc (Zadání)
Způsobů, jak tuto úlohu vyřešit v dostatečně těsném prostoru, je vícero. Například bychom mohli použít obyčejné prohledávání do hloubky a jeho zásobník šikovně zkomprimovat – tak se můžeme snadno dostat až na dva bity na vrchol. My si ale předvedeme trochu jiné, technicky daleko jednodušší řešení.
Definujeme navigační posloupnost, což bude posloupnost n čísel a1,… ,an (kde n je počet vrcholů grafu) v rozsahu 0 až 3. Každé navigační posloupnosti odpovídá nějaká „procházka po grafu“ (v grafové terminologii sled délky n): začneme v nultém vrcholu grafu, z něj se vydáme a1-tou z jeho čtyř hran, z dalšího vrcholu pak a2-tou hranou a tak dále.
Všimněme si, že pokud v grafu existuje nějaká kružnice, na které leží všechny vrcholy, pak je určitě popsána alespoň jednou navigační posloupností. Budeme tedy postupně generovat všechny navigační posloupnosti a pro každou z nich ověřovat, jestli popisuje hledanou kružnici.
Posloupnosti budeme přímočaře kódovat čísly. Na každé ai nám stačí dva bity, takže do jednoho 32-bitového čísla schováme hned 16 prvků posloupnosti. Libovolné ai pak dokážeme pomocí konstantního počtu aritmetických a bitových operací z tohoto kódu přečíst. Navíc se na celý kód můžeme dívat jako na jedno dlouhé 2n-bitové číslo a jeho postupným zvyšováním o jedničku snadno vygenerovat všechny posloupnosti.
Když už umíme z posloupnosti číst, můžeme také snadno simulovat procházení po grafu a odpovídat na otázky typu „jaký je i-tý vrchol, který potkáme?“ nebo „potkáme cestou vrchol v?“. Obojí sice stojí čas O(n), ale o ten nám vůbec nejde. Hlavní je, že si vystačíme s konstantním množstvím pracovní paměti.
Teď už stačí umět poznat posloupnost, která popisuje hledanou kružnici. To je také snadné: pro každý vrchol grafu vyzkoušíme, zda jím posloupnost projde, a pak ještě zkontrolujeme, že se na konci vrátíme zpět do vrcholu 0.
Toto řešení spotřebuje ⌊n/16⌋+ O(1) buněk paměti a má časovou složitost O(4n·n2). Existuje totiž 4n kódů posloupností, pro každý z nich O(n)-krát hledáme vrchol, což pokaždé stojí O(n).
Grafy stupně 3: Pokud z každého vrcholu vedou pouze 3 hrany, není potřeba na prvek posloupnosti obětovat celé 2 bity. Nabízí se použít trojkovou soustavu, ale pak bychom neuměli bez dodatečné paměti z posloupnosti číst. Použijeme místo toho „křížence“ mezi dvojkovou a trojkovou soustavou: nadále budeme kód dělit na 32-bitová slova a do každého uložíme trojkově co nejvíce prvků. Vejde se jich až ⌊ log3 232⌋, čili 20. Spotřeba paměti tedy klesne na ⌊n/20⌋+ O(1).
Ještě šetrnější způsob: Bystří řešitelé si všimli, že i tento docela hustý popis procházek pomocí posloupností je stále dost marnotratný. Když přijdeme do vrcholu se čtyřmi hranami, nechceme se přeci vracet po hraně, po níž jsme právě přišli, takže máme na výběr pouze ze tří možností. Předchozí trik s trojkovou soustavou tedy můžeme použít i pro původní verzi úlohy. V grafech stupně 3 si dokonce vystačíme se dvěma možnostmi, což nám dává jediný bit na stav, a tedy ⌊n/32⌋+ O(1) buněk paměti. Strýček Skrblík by měl radost a pan Cowmess jistě také.