Čtvrtá série dvacátého třetího ročníku KSP

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

Řešení úloh

23-4-1 Studenti a profesoři (Zadání)

Všichni, kdo se odvážili odevzdat řešení, argumentovali převoditelností na problém maximálního toku – kuchařka v tomhle směru napovídala dost jasně. Nikdo pod devět bodů nedostal (vždyť také nikdo celé řešení pouhým poukazem do mého textu neodbyl), ve zbývajícím rozsahu jsem tak hodnotil úvahy o časové složitosti a nuance.

Je docela jasné, že si budeme uzpůsobovat první ze dvou zmíněných aplikací, která mluví o tom, jak pomocí toku najít maximální párování. Postavíme si ze zadání bipartitní graf, zorientujeme v něm hrany k profesorům, vrcholy studentů a profesorů pak napojíme na studentský zdroj a profesorský stok.

Protože chceme, aby měl student právě K profesorů, nastavíme váhu každé z hran ze studentského zdroje na K – to samé uděláme hranám do profesorského stoku, to aby měl každý profesor právě K studentů. Hranám uvnitř někdejšího bipartitního grafu nastavíme jedničky.

Povšimněme si tu, že kdyby zadání nezakazovalo, aby si některý student vybral profesora pro několik svých prací, vyrovnali bychom se s tím jednoduše – hraně, která by mezi příslušnými vrcholy vedla, bychom nastavili kapacitu na povolenou maximální násobnost.

Samozřejmě by ani nebyl problém mít rozdílný počet profesorů a studentů, či dokonce zavést individuální požadavky na počet vedených prací. Zadání bylo tak jednoduché předně proto, aby neděsilo.

Vraťme se k původní úloze. Na popsaný graf pustíme tokový algoritmus zachovávající celočíselnost a získáme z něj výsledek. Pokud není nalezený tok velký právě NK, řešení, které by každého plně uspokojilo, není. Pokud ano, vypíšeme páry profesor-student, jejichž hrana má jednotkový tok.

Důvod, že postup funguje, můžeme načrtnout třeba skrze fakt, že tok větší než NK v grafu existovat nemůže. Svědčí o tom řez na hranách mezi studentským zdrojem a studentskými vrcholy, kde je N hran, každá o kapacitě K.

Z toho vidíme, že pokud nám algoritmus vrátí takto velký tok, musí vést z každého studentského vrcholu k profesorům K jednotkových hran (a podobně ze strany profesorů), tedy jde o skutečné řešení našeho původního problému.

Zároveň se nemůže stát, aby postup řešení (maximální tok) nenašel a ono by existovalo – vždyť z každého řešení sestavíme tok o maximální velikosti.

Co časová složitost? Smířit se s tím, že má Edmondsův-Karpův algoritmus složitost O(M2 N), je přístup lenivý. Nicméně si můžeme všimnout, že zlepší-li každá cesta výsledek alespoň o jednotku, nenajdeme takových cest víc než KN.

Z toho plyne složitost O(KMN), což je lepší, protože pro K > N úloha zřejmě není zajímavá.

Vysloveně akční přístup je začít se poohlížet po nekuchařkovém algoritmu. (To ale k získání maximálního počtu bodů potřeba nebylo.) Můžeme buď přemýšlet o tom, jestli není možné vzít Dinice či Goldberga a vzhledem k jisté speciálnosti našeho grafu vylepšit odhady časové složitosti, nebo zkusit najít specializovaný postup.

Vtip tkví v tom, že při zkoumání druhé možnosti nejspíše narazíme na Hopcroftův-Karpův algoritmus pro nalezení maximálního párování v bipartitním grafu běžící v čase O(M√N), který je však jen dobře odhadnutý a přeříkaný Dinic.

My tu sice nechceme bipartitní párování, leč každé naše řešení (K-regulární bipartitní podgraf) se skládá z K takových disjunktních množin hran (1-regulárních bipartitních podgrafů). To není úplně vidět, ale je to hezká a užitečná pravda.

Můžeme tedy K-krát spustit Hopcrofta-Karpa a pokud nějaké řešení existuje, získáme ho v čase O(KM√N). Pořád tak netrumfneme škálu rozličných moderních algoritmů pro hledání maximálního toku na obecném grafu, jde však o celkem srozumitelné a snadno naprogramovatelné řešení.

Lukáš Lánský

23-4-2 Paralelní profesoři (Zadání)

Tuto úlohu se pokoušelo vyřešit jen 8 z vás a k mému zklamání jen jedno řešení bylo úplně správně. Gratulace patří Vojtěchu Hlávkovi.

Nejčastější chybou bylo, že jste úlohu vyřešili pro N=2k a zobecnili pro všechna N. Proč je tato úvaha špatná, je dobře vidět například pro N=3.

Jak to tedy mělo být? Pokud N=2k, tak v prvním kroku profesory rozdělíme do dvojic a tím získáme dvojice profesorů se stejnými informacemi. Ve druhém kroku k sobě posadíme různé dvojice profesorů a tím získáme čtveřice profesorů se stejnými informacemi atd.

Až se dostaneme k jedné skupince o velikosti 2k. Bude nám tedy stačit log2N sezení. Problém s dělením nikde nenastane, počet skupinek bude vždy sudý.

Pro jiné počty profesorů ale tento algoritmus aplikovat nemůžeme, protože v nějakém kroku dostaneme lichý počet skupinek a ten už neumíme jednoduše spárovat.

Úlohu vyřešíme zvlášť pro sudá a lichá čísla. U lichých čísel si můžeme všimnout, že při každém sezení bude alespoň jeden z profesorů lichý. Spočítáme si tedy, za kolik nejméně sezení se můžou všichni profesoři dozvědět informaci od toho, který byl lichý při prvním sezení.

Po prvním sezení ví onu informaci pouze on sám a po každém dalším sezení se množství profesorů se znalostí této informace může maximálně zdvojnásobit. Z toho vyplývá, že všichni profesoři můžou tuto informaci znát nejdřív po ⌈ log2N⌉+1 sezeních.

⌈x ⌉ je takzvaná horní celá část, nejmenší celé číslo větší nebo rovné x.

Nyní, když najdeme obecný algoritmus pro lichá čísla, který řeší úlohu v ⌈ log2N⌉+1 krocích, tak máme vyhráno. Každé číslo si můžeme napsat jako 2k + l, kde k a l jsou přirozená čísla a k je nejvyšší možné.

Pak při prvním sezení sprárujeme l profesorů s některými z 2k, těchto 2k už umíme vyřešit v k krocích a nakonec opět zbylých l profesorů spárujeme s některými z 2k.

Situaci se nám tedy povedlo vyřešit na

k+2=⌊ log2N⌋+ 2=⌈ log2N ⌉+ 1 kroků,

a to jsme chtěli.

Zbývají jen sudá čísla. Obdobně jako u lichých čísel ukážeme, že minimální nutný počet sezení je ⌈ log2N⌉.

Profesory očíslujeme 0, 1, … , N-1. První sezení spárujeme (0,1),(2,3),… ,(N-2,N-1), tím každý zná dvě informace.

Pro druhé sezení vytvoříme dvojice (0,3),(2,5),(4,7),… Tím všichni profesoři se sudým číslem s mají informace s … (s+3) mod N, po k-tém sezení mají analogicky informace s … (s+2k-1) mod N.

Lichá čísla jsou k sudým párována symetricky, takže až sudí budou znát vše, tak i liší. Celkem nám tedy bude stačit ⌈ log2N ⌉ sezení.

Obecně N je tedy optimální počet sezení

⌈ log2N ⌉+ (N mod 2).

Jedinou výjimku tvoří N=1, kde nepotřebujeme žádné sezení.

Karel Tesař

23-4-3 Zabugovaný program (Zadání)

Dva zlatokopové, neboli ve známější verzi loupežníci, zvolili hladový algoritmus. Předložený program setřídil vstupní hodnoty a potom je hladově rozdělil mezi zlatokopy.

Hladově, to znamená tak, že se podíval, který z nich má zrovna méně, a tomu nuget přidělil. Začínal od největšího, skončil nejmenším.

Rychle jste odhalili, že potřebujete najít false negative, tedy vstup, u kterého program nenalezne správné řešení, byť by existovalo. Když totiž program ohlásí řešení, je zjevně správně.

Nejmenší vstup, na kterém se program zachoval chybně, byl 3 3 2 2 2, kde bylo správným řešením dát jednomu ze zlatokopů 3 3 a druhému 2 2 2. Program si nicméně tvrdošíjně mlel svou a po rozdělení 3 2 2 a 3 2 prohlásil, že řešení neexistuje.

Vstup byl nejmenší co do počtu nugetů. Řešitelé, kteří to dokázali, získali body navíc.

Důkaz byl docela jednoduchý rozbor případů. Vstup s jedním nugetem nemá řešení. Vstup se dvěma nugety a1, a2 může mít řešení jen pro a1 = a2, což náš program najde. Vstup se třemi nugety a1 ≤ a2 ≤ a3 může mít řešení jedině pro a1 + a2 = a3, což náš program zase bez problému najde.

V případě čtyř nugetů na vstupu (a1 ≤ a2 ≤ a3 ≤ a4) bylo potřeba vyřešit několik možných případů. Program vždycky rozdělil nugety a1 a a2 na dvě různé hromádky. Kdyby platilo a1 = a2, muselo by také platit a3=a4, jinak by řešení neexistovalo (dokažte za domácí úkol). V takovém případě ale náš program funguje.

Tudíž a1 > a2, a tedy náš program dá a3 na hromádku k a2. Nakonec odloží a4 na menší z obou hromádek. Pokud platí a4 = |a1 - a2 - a3|, program vydá správné řešení; rozmyslete si, že to platí vždy.

Základem důkazu je na tomto místě úvaha, za jakých podmínek by ve všech správných řešeních musely být a1 a a2 nebo a1 a a3 na společných hromádkách, nebo a2 a a3 na různých.

Vstup byl i nejmenší co do celkové hodnoty. Za důkaz jsme taktéž udělovali bonusové body. Taktéž byl nejrozumnějším přístupem rozbor případů.

Někteří řešitelé si nevšimli, že program bral vstupní hodnoty sestupně. Pythoní kód to řešil metodou pop, která odebírá z konce seznamu, program v C třídil obráceně a procházel pole od začátku.

Za řešení s touto chybou jsme udělovali 2 body. Jeden za správnost, druhý za nápad, jak si úlohu výrazně zjednodušit (nejmenším protipříkladem by byl vstup 1 1 2).

Martin „Medvěd“ Mareš & Jan „Moskyto“ Matějka

23-4-4 Závorky v TeXu (Zadání)

Nejprve se podívejme na rozpoznávání správného uzávorkování. Řetězec se závorkami { a } budeme procházet zleva doprava a počítat si, kolik neuzavřených levých závorek nám zbývá (tento počet označme k). Mohou nastat pouze dva případy znamenající, že řetězec není správně uzávorkovaný:

Jak poznat, že lze řetězec změnit na správně uzávorkovaný pouhými změnami znaku? Je zřejmé, že pro lichý počet to učinit nelze a pro sudý naopak vždy lze, protože můžeme jednoduše změnit všechny znaky na řetězec {}{}{}{}…

Nyní přejděme k algoritmu, který řeší naši úlohu a zajišťuje minimální počet změn znaků. Stejně jako při rozpoznávání, jestli je uzávorkování správné, budeme procházet závorky zleva doprava a počítat si neuzavřené levé.

Když k klesne pod 0 na pozici i, musíme změnit nějakou uzavírací závorku na pozici menší nebo rovno i (na pozici větší než i už to nepomůže). Je celkem jedno kterou, jde nám jen o počet změn. Také nesmíme zapomenout aktualizovat počet neuzavřených závorek (z -1 na 1).

Po přečtení poslední závorky mohou nastat 3 případy:

Určitě nic nepokazíme, pokud budeme otevírací závorky měnit zprava. Počet změn je k/2 (každou změnou klesne počet neuzavřených levých závorek o 2).

Časová složitost je zjevně lineární a lépe to nejde (musíme se podívat na každou závorku). Část řešitelů prohlásila i paměťovou složitost za lineární, což kupodivu jde zlepšit. Kdo četl zadání pozorně, všiml si, že úkolem bylo najít pouze počet změn.

Stačilo tedy číst znaky ze vstupu (např. z obrovského souboru) a vůbec je neukládat, což dává konstantní paměťovou složitost. Kdo chtěl vracet správně uzávorkovaný řetězec, musel si pamatovat alespoň část řetězce od poslední změny znaku } na { nebo od posledního nulového počtu neuzavřených levých závorek, takže nejhůře celý řetězec.

Možná se zcela správně ptáte, proč náš algoritmus dává minimální počet změn. Je zřejmé, že pro správně uzávorkovaný řetězec vypíše 0. Pro špatně uzávorkovaný žádnou ze změn provedených při kontrole, jestli k nekleslo pod 0, nemůžeme vrátit. Na konci také musíme změnit nějakých k/2 otevíracích závorek.

Navíc nelze na žádné pozici provést změnu z { na } a potom zpět na { (tj. obě změny by byly zbytečné), protože by nám opět kleslo k na té pozici pod 0. Algoritmus tedy dává minimální počet změn.

Program (Python)

Pavel „Paulie“ Veselý

23-4-5 Palindromnásobky (Zadání)

Zkusme řešit jednoduše – projdeme všechna čísla délky D dělitelná K a započítáme ta z nich, která jsou palindromem. Časová složitost tohoto řešení je O(D·10D / K), protože čísel, která testujeme, je O(10D / K) a pro otestování, zda je číslo palindromem, musíme projít všech jeho D číslic.

Co takhle zkusit to naopak, procházet všechny palindromy a určit, které z nich jsou dělitelné K? Palindromy projdeme tak, že začneme nejmenším z nich (jeho první a poslední číslice jsou 1, všechny ostatní 0) a vezmeme první polovinu jeho číslic, začínajíce od největšího řádu a včetně prostřední číslice v případě lichého D.

Toto číslo zvětšíme o jedna a zrcadlíme zpět, abychom získali palindrom odpovídající délky. Tedy například 13931 → 139 → 140 → 14041. Stejný postup opakujeme, dokud se nedostaneme k číslu obsahujícímu samé devítky, čímž jsme u konce.

Abychom nemuseli v každém kroku palindrom půlit a pak zase zrcadlit zpátky, můžeme pracovat přímo s palindromem, jenom začneme uprostřed a případný přenos šíříme na obě strany. Takto dostaneme časovou složitost O(10D/2).

Exponenciální časové složitosti jsou ale hodně ošklivé. Copak tahle úloha nejde vyřešit v (pseudo-)polynomiálním čase? (Proč pseudo? Obvykle se složitost měří vzhledem k délce vstupu, pokud je ale složitost polynomiální vzhledem k hodnotě čísel na vstupu, říká se takovému algoritmu pseudopolynomiální.)

Jistěže jde, jenom je potřeba se trochu zamyslet. Každý palindrom můžeme jednoznačně rozložit na ⌈D / 2 ⌉ podpalindromů stejné délky jako celý palindrom tak, že i-tý podpalindrom má nenulové cifry pouze na i-té pozici od začátku a i-té pozici od konce. Tyto podpalindromy mohou mít, na rozdíl od běžných palindromů, nuly na začátku. Například 10301 rozložíme na 10001, 00000 a 00300.

Jak tohoto rozkladu využijeme? Vytvoříme tabulku zbytků – pro každou možnou hodnotu zbytku po dělelní číslem K (tedy pro čísla 0 až K-1) si budeme pamatovat, kolika různými způsoby umíme vytvořit palindrom s daným zbytkem.

V prvním kroku projdeme podpalindromy, které mají nenulovou číslici na prvním (a tedy i na posledním) místě. Pro každý z nich určíme jejich zbytek a tyto počty si poznamenáme.

Ve druhém (a obdobně v každém dalším) kroku postupujeme tak, že nejdříve vytvoříme novou tabulku zbytků zkopírováním té staré, protože všechny palindromy, které jsme uměli vytvořit v předchozím kroku, umíme vytvořit stále (rozklad takového palindromu by měl na odpovídajícím místě podpalindrom ze samých nul).

Dále projdeme podpalindromy, které mají nenulovou číslici na druhém (a tedy i na předposledním) místě. Pokud má podpalindrom zbytek r, přičteme do nové tabulky hodnoty ze staré, cyklicky posunuté o r míst. To proto, že pokud jsme v předchozím kroku uměli vytvořit n palindromů se zbytkem q, umíme s využitím aktuálního podpalindromu vytvořit n nových palindromů se zbytkem (q + r) mod K.

Po posledním kroku takto získáme v závěrečné tabulce zbytků na pozici 0 počet palindromů délky D, které mají zbytek po dělení číslem K rovný nule, což je přesně to, co jsme chtěli. Vzhledem k tomu, jak s palindromy a podpalindromy pracujeme (a s využitím předpočítaných zbytků mocnin desítky) si je dokonce ani nemusíme pamatovat celé, stačí vždy jejich zbytek po dělení K.

Celková časová složitost tohoto algoritmu je O(D ·10 ·K), protože pro každý podpalindrom, kterých je 10-1 v každé z ⌈D / 2 ⌉ skupin, přičítáme K hodnot do tabulky zbytků (kromě podpalindromů s první číslicí nenulovou, které jsou jednodušší).

Možná by vás mohlo zarazit použití konstanty 10 v časové složitosti. Pokud bychom chtěli stejnou úlohu řešit v jiné soustavě, než je desítková, nahradili bychom toto číslo základem dané soustavy. Pokud ale nad takovou možností neuvažujeme, můžeme časovou složitost zapsat jako O(D K).

Vzhledem k tomu, že používáme předpočítané zbytky mocnin desítky, a vzhledem k tomu, že v každém kroku nám stačí dvě tabulky zbytků (aktuální a z předešlého kroku), je paměťová složitost O(D + K).

A ještě jeden dodatek na konec – zadané limity byly takové, že výsledek mohl být tak velký, že se nevešel do 32-bitového integeru, takže pro získání plného počtu bodů bylo potřeba použít 64-bitový integer.

Program (C)

Petr Onderka

23-4-6 Knuthovy cesty po státech (Zadání)

Zkusme postupovat tak, že budeme následovat Knuthovu cestu a na každé křižovatce si pamatovat, kam až sahá nejdelší úsek cesty, který se nekříží a zároveň končí tam, kde zrovna jsme. Z takovýchto úseků pak vezmeme nejdelší a jsme hotovi.

Nyní předpokládejme, že známe nejdelší nekřížící se úsek končící i-tou křižovatkou (jeho začátek označme Z) a chceme najít takovou část cesty pro další křižovatku (nechť je to křižovatka K). Tam nám mohou nastat 2 případy:

  1. Křižovatku K jsme navštívili před Z (popř. jsme ji nenavštívili vůbec). Pak můžeme nejdelší nekřížící se úsek cesty prodloužit o křižovatku K.
  2. Křižovatku K jsme navštívili během nejdelší nekřížící se cesty pro i-tou křižovatku. Pak nastavíme nový začátek Z hned za minulou návštěvu křižovatky K a pokračujeme dál.

Zřejmě pokud bychom prodloužili aktuální cestu o jednu křižovatku zpět, dostali bychom se na nějakou podruhé, a tedy v každém kroku je nalezený úsek nejdelší nekřížící se.

Na to, aby výše uvedený postup fungoval efektivně, budeme potřebovat vědět, kdy jsme naposledy jakou křižovatku navštívili. To se udělá snadno pomocí pole o velikosti počtu křižovatek, kde si budeme příslušnou informaci udržovat.

Časová složitost je lineární a paměťová také.

Program (Pascal)

Pavel Čížek

23-4-7 Bratrstvo Seda a Grepa (Zadání)

Omluva na začátek. Formulace některých úkolů byly vágní a umožňovaly různé interpretace. Přesto jste je pochopili převážně tak, jak jsem je původně myslel.

Řešení úkolu 1 bylo správně u všech, kdo jej poslali.

s/[ \t\r]+$//

Jeden výtečník zapomněl na dolar a místo něj použil chybné \n, za což byl nepatrně ztrestán (sed čte vstup po řádcích, takže \n na vstupu defaultně nikdy není). Hezké bonusové řešení předvedl Vojta Hlávka:

s/[[:space:]]*$//

Druhý úkol byl potvorný. Jedním ze správných řešení bylo napsat regex

s/(([ ~][KkOoSsUuVvZzIiA])|([[:punct:]][[:space:]~]?a)) /\1~/g

a prohlásit, že jej spustíme dvakrát. Proč? Poprvé ovlnkuje liché, podruhé sudé výskyty. Vstup „…, a i s nimi“ se tedy nejprve změní na „..., a~i s~nimi“, aby po druhém průchodu přibyla i prostřední vlnka a vznikl kýžený výsledek „..., a~i~s~nimi“.

Druhá správná varianta se dala vymyslet s manuálem GNU sedu v ruce, kde jste se mohli dočíst o \b, což je předpoklad nulové délky s významem „hranice slova“.

Jinak řečeno, když sed přijde k \b, tak se podívá, jestli je na hranici slova. Pokud ano, pokračuje dál, jinak se vrátí a zkusí jinou variantu. Druhé možné řešení tedy bylo

s/((\b[KkOoSsUuVvZzIiA])|([[:punct:]][[:space:]~]?a)) /\1~/g

které už stačilo spustit jednou.

Většina řešitelů si nevšimla buďto problému s ovlnkováním řetězu předložek, nebo zapomněli na variantu se spojkou a a interpunkcí apod. Toleroval jsem neúplný výčet interpunkce i chybějící předložky v seznamu, nicméně v praktickém použití si na to dejte pozor.

Úkol 3 byl zadaný vágně. Nebyla totiž definována abeceda, nad kterou se problém řeší. Většina řešitelů předpokládala, že bude rozumná a nebude obsahovat speciální znaky. Za takových podmínek byl problém řešitelný.

Nabízí se řešení přímočaré, leč chybné:

egrep '^s(.).+\1.*\1g?$'

Vyhovuje mu totiž například i řetězec saaaaaa. Jak tomu předejít? Vykutálený trik některých řešitelů [^\1] nefunguje (\1 se totiž uvnitř hranatic interpretuje jako dvojice znaků \ a 1).

Nuže, přilepíme k prvnímu regexu filtr, který zahodí nevyhovující řetězce (obsahují moc oddělovačů).

| egrep -v '^s(.).*\1.*\1.*\1.*$'

To je sice hezké, ale tentokrát neprojde sgaggg. Musíme oddělit g. Zde je kompletní správné řešení.

egrep '^s(.).+\1.*\1g?$' |
egrep -v '^s(([^g]).*\1.*\1.*\1.*|g[^g]*g[^g]*g([^g]+|g.+))' |
egrep -v '^s\1\1.*'

První regex vytáhne kandidáty, druhý z nich vyháže ty, které mají nadbytečný počet oddělovačů (dobře si prohlédněte druhou větev, ve které se řeší g) a třetí ještě smaže ty, které mají prázdný regex k vyhledání, neboť ty také nejsou validní.

Ještě by se dalo připustit v abecedě zpětná lomítka. S tím se úspěšně porval jeden člověk.

Jakub Zíka se pustil do složitějšího rozboru případu, kdy uvažoval obecnější abecedu, která by mohla obsahovat speciální znaky. Právem mu náleží dva bonusové body.

Pokud by abeceda obsahovala kulaté závorky, nemůžeme ani zkontrolovat jejich správné vnoření, ani zkontrolovat validitu backreferencí a v tom případě je úkol zadanými prostředky neřešitelný.

Třešničkou na dortu pak byl úkol 4. Objevil se nápad počítat si po 1, dokud nedojdeme k menšímu ze zadaných čísel (a vypsat pak to druhé). Má to jeden háček – napsat sčítačku je možná o něco těžší než tento úkol samotný…

Autorské řešení spočívalo v porovnání řetězců nejprve podle délky, pak už bylo přímočaré.

s/([01]+) ([01]+)/\1#\2#\1#\2/
s/#[01]([01]*)#[01]([01]*)$/#\1#\2/
s/([01]+)#([01]+)##[01]+/\2/
s/([01]+)#([01]+)#[01]+#$/\1/
s/([01]+)1([01]*)#\1[0]([01]*)##$/\11\2/
s/([01]+)0([01]*)#\1[1]([01]*)##$/\11\3/

První řádek zamezí vícenásobnému startu (změna oddělovače) a připraví půdu pro porovnání podle délky – vytvoří kopie, ze kterých budeme usekávat číslice.

Druhý řádek usekne z kopie vstupu po číslici. Třetí a čtvrtý řádek ošetřují případ, kdy je jedno číslo kratší než druhé.

Na pátém a šestém řádku jsme zjistili, že jsou čísla stejně dlouhá, takže z nich vybereme to větší a vypíšeme.

Kdyby mohly být na začátku čísel nuly, stačilo by doplnit na vhodná místa 0*.

Ještě nabízím variantní řešení se sčítačkou.

s/^([01]+) ([01]+)$/\1-\2@0/
s/@([01]*)0$/#\11/
s/@([01]*)01(1*)$/:\110\2/
s/:([01]*0+)1(1*)$/:\10\2/
s/:([01]*0+)$/#\1/
s/^([01]+)-([01]+)#\1$/\2/
s/^([01]+)-([01]+)#\2$/\1/
s/#/@/

První řádek je vstupní, druhý řádek přičítá k sudému číslu, třetí až pátý k lichému. Významy oddělovačů jsou snad jasné. Pro ještě nezvýšené číslo používáme @, pro právě inkrementované číslo používáme : a pro hotové číslo k porovnání máme #.

Zde by se už hodila analýza časové složitosti. Předpokládejme, že vyhodnocení regexu trvá jednotkový čas. Reálný odhad to není a asi nikdy nebude, leč pro představu to stačí.

První řešení nejdřív postupně odsekává po číslici, což trvá N kroků (N číslic na vstupu). Porovnání stejně dlouhých čísel už proběhne v konstantním čase, takže složitost odsekávacího řešení je O(N) cyklů.

Druhé řešení počítá po jedné. Byť stráví sčítáním od 1 do K jen O(K) cyklů, je to pořád O(2N), neboť K může být s O(N) číslicemi na vstupu až exponenciálně veliké.

Není všechno zlato, co se třpytí, aneb přičítání jedničky vypadá lákavě, leč jeho rychlost není závratná. Naopak zdánlivě chlupaté řešení se sekáním číslic je výrazně rychlejší a efektivnější.

Jan „Moskyto“ Matějka