Přestože se hra může vyvíjet mnoha různými způsoby, celkový počet různých pozic je nejvýše RS + 1. Jedna pozice je snězená čokoláda. Jinak po každém kroku zbude z čokolády obdélník s levým horním rohem v políčku (1, 1). Proto každé políčko reprezentuje pozici, ve kterém je ono nejpravějším a nejspodnějším políčkem dosud zbylého kusu čokolády.
Prázdná čokoláda a ty pozice, ze kterých neexistuje žádný povolený tah, jsou ze zadání prohrávajícími. Pro každou další pozici rozhodneme, zda je vyhrávající pro hráče na tahu, tak, že se podíváme, do kterých pozic se z ní lze jedním tahem dostat. Existuje-li z aktuální pozice tah do prohrávající pozice, je tato pozice vyhrávající. V opačném případě je prohrávající.
Zbývá pouze rozhodnout o tom, které tahy jsou povolené. Mějme pozici reprezentovanou políčkem (i, j). Řádek můžeme ulomit tehdy, je-li počet oříšků v i-tém řádku sudý. Analogická situace je pro sloupce. Přímočaré řešení tedy může postupně procházet políčka po řádcích a pro každé rozhodnout, v čase Ο(R + S), které tahy jsou z něj povolené. Následně vyhodnotí, zda je aktuální pozice vyhrávající, a pokračuje dále. Celková časová složitost uvedeného algoritmu je Ο(RS · (R + S)) a paměťová je optimální Ο(RS).
Pokusme se algoritmus vylepšit. Nebudeme v každém kroku zjišťovat, zda je součet čísel v řádku sudý, ale předpočítáme si tyto informace již na začátku. Podívejme se na čokoládu v pozici odpovídající políčku (i, j), kde j je alespoň 2, a pokusme se rozhodnout, zda je možné odlomit poslední řádek. Součet čísel v posledním řádku této čokolády je o Bi, j větší než součet čísel v posledním řádku čokolády odpovídající pozici (i, j - 1). Můžeme si tedy součty v posledních řádcích pamatovat a znovu je využívat. Pro všechny pozice tak můžeme spočítat součet v posledním řádku a analogicky také v posledním sloupci v čase Ο(RS). Společně s předchozím algoritmem dostáváme celkově optimální algoritmus s časovou i paměťovou složitostí Ο(RS).
K řešení použijeme metodu dělení intervalu. Řekněme, že chceme vypsat chybějící pakety s čísly v intervalu <a, b> a v souboru S máme uložena čísla všech došlých paketů v tomto intervalu. Rozdělme si interval <a, b> na několik podintervalů I1 = <a, m1>, I2 = < m1+1, m2>, …, It = < mt-1+1, b> zhruba stejné velikosti. Pro tyto podintervaly si pořídíme pomocné soubory S1, …, St a každé číslo ze souboru S patřící do intervalu I_i (pro nějaké i z množiny {1,…,t}) si překopírujeme do souboru Si.
Zároveň si počítáme počet čísel ni v tomto souboru. Zjevně pokud ni je rovno velikosti intervalu Ii, pak v intervalu Ii nechybí žádný paket, a tyto intervaly proto můžeme ignorovat. Na ostatní intervaly se zavoláme rekurzivně. Pokud v rekurzi dospějeme k intervalu, který neobsahuje žádná čísla došlých paketů, pak všechna čísla v tomto intervalu chybí a vypíšeme je na výstup.
Na kolik podintervalů bychom měli interval dělit? Kdybychom zvolili t=2 a interval půlili, může se nám v nejhorším případě stát, že nejprve budeme zpracovávat 1 interval velikosti n, na další úrovni rekurze 2 intervaly velikosti n/2, …, až na (log2 k)-té úrovni rekurze budeme zpracovávat k intervalů velikosti n/k. Na každé další úrovni již budeme zpracovávat k intervalů velikosti vždy poloviční než na předchozí úrovni, a tedy celkový počet zpracovaných čísel na každé další úrovni se vždy zmenší alespoň na polovinu. Celková délka zpracovávaných intervalů, která odpovídá počtu čísel čtených ze souborů, tedy bude 1· n+2·n / 2+4·n / 4+…+k·n / k+n/2+n/4+… ≤ n log2 k+n. Vzhledem k tomu, že každé čtené číslo kromě těch ve vstupním souboru také zapíšeme, může počet čísel zapsaných a čtených ze souborů být dohromady až 2nlog2 k, což pro zadaná omezení na n a k může přesáhnout povolené omezení na počet operací se soubory.
Nicméně, s omezeními ze zadání můžeme interval dělit na t=max(2,k) dílů. V tomto případě budeme pro každé chybějící číslo uvažovat postupně intervaly délky n, n/k, n/k2, …, které ho obsahují. První interval <1,n> je navíc pro všechna chybějící čísla stejný, a proto ho počítáme pouze jednou (stejné pozorování platí i pro kratší intervaly, které obsahují více než jedno chybějící číslo; žádné takové intervaly ale nemusí existovat, proto tuto redundanci v odhadu počtu operací se soubory ignorujeme). Celkový počet čtení je tedy nejvýše n+k(n/k+n/k2+…) ≤ 3n, a počet zápisů je nejvýše 2n. Počet operací se soubory tedy nejvýše 5n, což odpovídá omezení ze zadání.
Časová složitost algoritmu je tak zjevně Ο(n). Naivní rekurzivní implementace popsaného algoritmu by měla paměťovou složitost Ο(klog n); povšimněme si ale, že si místo rekurze můžeme jednoduše udržovat seznam nejvýše k ještě nezpracovaných intervalů (z nichž každý obsahuje alespoň jedno číslo chybějícího paketu) a postupně ho procházet. Tím se paměťová složitost sníží na Ο(k).
Úkol 1: Řešením je například síť
Úkol 2: Tuto úlohu vyřešíme obdobně jako příklad 3 ze studijního textu. Připomeňme, že maj je funkce se třemi vstupy, která vrací ten vstup, který se vyskytuje nejčastěji. Nechť (a1,b1,c1), (a2,b2,c2) a (a_3,b_3,c_3) jsou tři trojice vstupů, které splňují omezení CH. Pak alespoň jedna z hodnot a1 a b1 je rovna 1, a tedy a1+b1 ≥ 1. Obdobně a_2+b_2 ≥ 1 a a_3+b_3 ≥ 1.
Dostáváme tedy 3 ≤ (a1+b1)+(a2+b2)+(a3+b3)=(a1+a2+a3)+(b1+b2+b3). Proto buď alespoň dvě z hodnot a1, a2 a a3 jsou rovny 1, nebo alespoň dvě z hodnot b1, b2 a b3 jsou rovny 1. Ekvivalentně, alespoň jedna z hodnot maj(a1,a2,a3) a maj(b1,b2,b3) je rovna 1. Obdobně, alespoň jedna z hodnot maj(b1,b2,b3) a maj(c1,c2,c3) je rovna 0. Proto hodnoty (maj(a1,a2,a3), maj(b1,b2,b3), maj(c1,c2,c3)) splňují omezení CH.
Nechť S(x,y,z) je libovolná síť sestavená pouze z omezení CH. Dle předchozího odstavce pro libovolná tři přiřazení P1, P2 a P3 hodnot proměnným, která splňují všechna omezení v síti S, přiřazení vzniklé z P1, P2 a P3 zkombinováním funkcí maj také splňuje všechna omezení v síti S. Speciálně, jestliže síť S přijímá trojice vstupů (x1,y1,z1), (x2,y2,z2) a (x3,y3,z3), pak také přijímá trojici (maj(x1,x2,x3), maj(y1,y2,y3), maj(z1,z2,z3)). Ovšem omezení ONE-IN-THREE je splněno trojicemi hodnot (1,0,0), (0,1,0), (0,0,1), ale není splněno jejich kombinací pomocí funkce maj, která je rovná (0,0,0). Proto žádná síť sestavená pouze z omezení CH nesimuluje ONE-IN-THREE.
Úkol 3: Připomeňme, že omezení Sh1h2… hn ze studijního textu zakazuje právě jednu kombinaci hodnot svých n vstupů, a to konkrétně kombinaci (h1, h2,…, hn). Nechť Q je síť s proměnnými x1, …, xn skládající se právě z omezení Sh1h2… hn(x1,…, xn) takových, že omezení O není splněno pro vstup (h1, …, hn). Tato síť Q simuluje omezení O. Proto stačí ukázat, že s použitím omezení ONE-IN-THREE lze simulovat libovolné omezení Sh1h2… hn.
Nechť i1, i2, …, ik jsou indexy takové, že hi1=hi2=…=hik=0, a všechny ostatní hodnoty z h1, …, hn jsou rovny 1. Uvažme síť
Stačí tedy ukázat, že s použitím omezení ONE-IN-THREE lze simulovat omezení S11… 1(x1,…, xn) pro každé přirozené číslo n. Pro n=1 je omezení S1(x1) simulováno sítí ONE-IN-THREE(x1,x1,j), vynucující že x1=0. Pro n=2 je S11(x1,x2) simulováno sítí ONE-IN-THREE(x1,x2,z). Pro n=3 je S111(x1,x2,x3) simulováno sítí S11(x1,x1'), S11(x2,x2'), S11(x3,x3'), ONE-IN-THREE(x'1,x'2,x'3): díky omezení ONE-IN-THREE(x'1,x'2,x'3) je x'i=1 pro nějaké i ∈ {1,2,3}, a proto xi=0.
Nechť n ≥ 4, a předpokládejme, že už jsme zkonstruovali síť simulující omezení S11… 1(x1,…, xn-1) s n-1 vstupy. Uvažme síť
Tato síť tedy vynucuje, že alespoň jedna z proměnných x1, …, xn je rovna 0, a proto simuluje omezení S11… 1(x1,…, xn). Takto můžeme postupně sestrojit všechna požadovaná omezení.