Druhá série šestnáctého ročníku KSP

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

Řešení úloh

• 16-2-1: Král Eeek
• 16-2-2: Král Ovopole
• 16-2-3: Král Potvorník
• 16-2-4: Křížový král
• 16-2-5: Král Popleta

16-2-1 Král Eeek (Zadání)

Jednociferný základ vyřešíme zvlášť: jestliže všechny cifry jsou menší než základ, máme jednu jedinou možnost, jinak nemáme žádnou.

Nechť n je počet cifer na vstupu, s[i] jsou vstupní cifry.

Řešení v čase O(n³) je jednoduché: V poli p[i] si budeme udržovat počet možností, které by existovaly, kdyby na vstupu chybělo prvních i čísel. Pro všechny délky základu z provedeme následující výpočet:

• p[n-z-1]=1, protože jednociferné číslo je určité menší než alespoň 2-ciferný základ (tohle platí samozřejmě pouze tehdy, nezačíná-li základ cifrou nula).
• Nechť máme všechna p[i+1], p[i+2], … a chceme spočítat p[i]. Zjistíme, kolikaciferné číslo může být na této pozici (dle konkrétních cifer to může být z nebo z-1, nebo pouze 1-ciferné, pokud ta cifra je 0; toto řeší funkce kolik_cifer), a počet možností pro p[i] bude p[i+1] (použijeme jednociferné číslo) + p[i+2] (nebo dvouciferné) + p[i+3] (nebo trojciferné) +…+p[i+z-1] (a možná + p[i+z]).

Pokud základ nezačínal nulou (viz. dříve), můžeme k celkovému řešení přičíst p[0]. Na každé cifře provedeme z kroků, cifer je n-z, všech základů je n, čili algoritmus pracuje v čase O(n³).

Časovou složitost lze vylepšit:

1. potřebujeme rychle zjišťovat, jestli na daném místě smí být z nebo z-1 cifer
2. potřebujeme počítat součet p[i+1] + p[i+2] + …+ p[i+z-1] nějak inteligentně (tj. v konstantním čase)
   1. jde vyřešit vyhledávacím automatem, ale to je tak trochu kanón na vrabce. Lepší je jít s délkou základu postupně od dvojky nahoru a pamatovat si, jestli číslo bylo v minulém kroku dlouhé z nebo z-1. Jestliže nejlevější cifra zkoumaného čísla je menší než nejlevější číslice základu, není co řešit a zkoumané číslo určitě může být plné délky. Jestliže nejlevější cifra je větší, také není co řešit – číslo musí být kratší. Jestliže se nejlevější cifry shodují, stačí se podívat, jak to dopadlo v minulém kroku; v tomto kroce dopadne porovnání stejně.
   2. zavedeme pomocné pole c[i], přičemž bude platit, že c[i] = ∑

      n-z-1

      j = i

      p[j]. Když budeme potřebovat zjistit součet p[a] + …+ p[b], spočítáme ho jako c[a] - c[b+1].

Tímto algoritmus urychlíme na O(n²), paměťová složitost zůstane O(n).

Program

Pavel Šanda

16-2-2 Král Ovopole (Zadání)

Většina řešitelů této úlohy nevýslovně zkoušela královu trpělivost, když jejich řešení vyžadovala více pokusů, než bylo nezbytně nutné. Své počáteční rozhodnutí, že všichni švindlíři budou setnuti nebo přinejmenším vsazeni do věže musel Ovopole brzy poněkud pozměnit pro nedostatek popravčích mistrů a věží. I bombardování pukavci krále brzy přestalo bavit, a tak většina špatných řešitelů byla potrestána jen nízkým bodovým ohodnocením. Abychom ale nebyli jednostranní, je třeba uvést, že se našlo i několik pěkných řešení, z nichž jedno dokonce předčilo očekávání organizátorů. Na snad všechna špatná řešení fungoval následující protipříklad (proto ho uvádím zde a neopisoval jsem ho do každého špatného řešení): Mějme dvě vejce a 28 pater. Pro tuto konfiguraci je správné (viz algoritmus níže) hodit nejdříve vejce ze šestého patra (patra číslujeme od nuly), pokud se nerozbije, tak ze dvanáctého, pokud se nerozbije, tak ze sedmnáctého, pak z dvacátého prvního, dvacátého čtvrtého, dvacátého šestého a nakonec z dvacátého sedmého patra (předpokládáme, že v nějakém patře se vejce rozbít musí – diskuse tohoto předpokladu je též uvedena níže). Pokud se vejce při některém pokusu rozbije, tak prostě budeme procházet patra od posledního, kde se vejce nerozbilo, směrem vzhůru, až najdeme hledané patro. V nejhorších případech potřebuje tento algoritmus pouze 7 pokusů na nalezení hledaného patra.

A nyní již jak má vypadat správné řešení: Protože v zadání nebylo zcela jasně řečeno, jestli se vejce musí rozbít při pádu z nejvyššího patra a jestli se nerozbije při pádu z nejnižšího patra, budeme předpokládat, že oba tyto případy mohou nastat. Abychom je nemuseli speciálně ošetřovat, přidáme si nad poslední patro ještě jedno s tím, že při pádu z tohoto patra se vejce zaručeně rozbije. Nyní už můžeme začít hledat nejnižší patro, při pádu z nějž se vejce rozbije, protože víme, že takové patro zaručeně existuje.

kde n!=n·(n-1)·(n-2)·  ...  ·2·1.

Dále se nám bude hodit, že z P(k,l) umíme rychle spočítat:

Pozn.: Jak zajistíme, že máme vždy po ruce spočítané potřebné kombinační číslo, si můžete nalézt v programu.

Matematickou přípravu již máme za sebou a nyní je čas ukázat, jak to vše využijeme v našem algoritmu. Nejdříve musíme nalézt nejmenší l takové, že P(k,l)≥ n+1 (n je počet pater, máme jedno patro přidané nahoře). To snadno uděláme tak, že budeme zkoušet l od 0 a průběžně počítat P(k,l) – využíváme, že umíme spočítat P(k,l+1) z P(k,l). Když toto nejmenší l nalezneme, začnou skutečné pokusy. V proměnné nejmensi si budeme uchovávat nejnižší číslo patra, ze kterého se vejce může rozbít (na počátku nejmensi=0). Vejce vždy pustíme z patra nejmensi+P(k-1,l-1)-1. Pokud se vejce rozbilo, tak snížíme k i l o jedna, přepočítáme P a pokračujeme dalším pokusem. Pokud se vejce nerozbilo, zvýšíme nejmensi o P(k-1,l-1), snížíme l o jedna, přepočítáme P (na přepočítávání P používáme rovnosti uvedené výše) a opět pokračujeme dalším pokusem. Z definice P takto zjevně po l krocích nalezneme hledané patro a počet kroků byl nejmenší možný.

Paměťová složitost algoritmu je O(1), časová O(l), kde l je nejmenší možný počet pokusů potřebný k nalezení patra.

Program

Honza Kára

Pro zájemce: proč je P(k,k)=2^k? Tento zápis znamená, že na k pokusů umíme najít hledané patro, jen pokud ho hledáme nanejvýš mezi 2^k patry (víme, že jedno z nich je ono hledané). Pokud použijeme půlení intervalu, opravdu tohoto výsledku dosáhneme (při každém pokusu se můžeme zbavit poloviny pater). Ale nejde to lépe?

Jeden pokus skončí jednou ze dvou různých možností (vajíčko se rozbije/nerozbije). Dva pokusy skončí jednou ze čtyř různých možností (první vajíčko se rozbije/nerozbije a druhé se rozbije/nerozbije). Obecně k pokusů skončí jednou z 2^k možností. Hledané patro určíme podle toho, jakou možností našich k provedených pokusů skončilo. Jedné takové možnosti (posloupnosti výsledků) může odpovídat nanejvýš jedno patro, protože jinak bychom po provedení k pokusů stále nebyli rozhodnuti, které patro je to hledané. Protože ale možností je 2^k, není možno najít hledané patro mezi více než 2^k patry.

Milan Straka

16-2-3 Král Potvorník (Zadání)

Idea algoritmu je jednoduchá. Vezmeme body, setřídíme je dle X, vezmeme provázek, přivážeme ho k nejlevějšímu bodu a budeme jím naší množinu sloupů obtahovat po směru hodinových ručiček. Konvexní obal tedy bude po celou dobu „zatáčet“ doprava. Nyní nechť máme zpracované body 1..N zleva a známe jejich konvexní obal. Chceme přidat další bod. Připojíme ho tedy k seznamu konvexního obalu a „zatáhneme“ za provázek. Ten se vzdálí ode všech sloupů u nichž „zatáčel vlevo“. Za povšimnutí stojí, že tyto sloupy tvoří v konvexním obalu souvislý úsek, který končí před právě přidaným bodem (úsek může být i prázdný). Takže v programu se stačí kouknout na 3 poslední body nynějšího obalu a dokud tam obal „zatáčí“ vlevo (čili je nekonvexní), předposlední bod vyhazovat. Protože každý bod můžeme vložit, resp. vyhodit nejvýše jednou, N kroků trvá O(N).

Pokud započítáme i třídění, složitost celého algoritmu je O(N log N). Ale má to drobný háček. Takhle bychom dopadli jako v jistém večerníčku, protože bychom vytvořili jen horní část konvexního obalu. Nicméně není těžké si rozmyslet, že stejně lze zkonstruovat i dolní polovinu (nebo k „vstupní“ posloupnosti bodů připojit na konec posloupnost stejných bodů, které budou setříděné obráceně, a pustit výše popsaný algoritmus na tuto prodlouženou posloupnost. Zřejmě pak bude provázek stále „zatáčet doprava“, ale jelikož jsme se „otočili“ o 180 stupňů, vytvoří i dolní část obalu).

Program je jen implementací výše uvedeného, časová náročnost je O(N log N) a paměťová O(N).

Na závěr bych přidal jednu poznámku k došlým řešením. Relativně hodně jich běhalo v čase O(N log N), ale používalo při tom funkce typu ArcTan apod… Proč? Tyto funkce nepatří, přiznejme si, zrovna k nejrychlejším a program lze napsat bez nich stejně jednoduše. Ideální je použít vektorový součin.

Vektorový součin třísložkových vektorů A a B je takový třísložkový vektor C, pro který platí:

1. Velikost C je rovna ploše rovnoběžníku definovaného vektory A a B.

   Matematicky: |C| = |A| ·|B| ·sin(φ), kde φ je úhel, který svírají vektory A a B.

2. Vektor C je kolmý na vektory A a B (zřejmě je-li B násobkem vektoru A, vektor C nemůže být určen jednoznačně (vektorů kolmých na A a B je mnoho). V tomto případě je naštěstí – dle bodu 1 – vektor C nulový).
3. Vektor C má (není-li nulový) směr, který odpovídá směru palce pravé ruky,pokud jí přiložíme k vektoru A a prsty „stočíme“ po menším úhlu k vektoru B. Tato podmínka vlastně pouze určuje znaménko vektoru C.

Tohle stačí k tomu, abychom výsledný vektor jednoznačně definovali. Jak se tedy vektorový součin třísložkových vektorů A a B počítá?

My použijeme vektorový součin takto: pro tři body A,B,C, které leží v tomto pořadí na obvodu zahrady, nám vektorový součet řekne, zda |∠ABC| < 180°, měřeno od polopřímky BA po směru hodinových ručiček. Vlastně nám poví, zda bude provázek v bodě B „zatáčet“ doleva (|∠ABC| > 180°) či doprava (|∠ABC| < 180°), tedy zda bod B patří nebo nepatří do konvexního obalu.

Výpočet provedeme takto: vektor U bude vektor od bodu B k bodu A, vektor V bude vektor od bodu B k bodu C. Spočteme z-ovou souřadnici součinu U×V (všimněte si, že při tomto výpočtu nepotřebujeme z-ové složky vektorů U a V, takže tyto vektory mohou být pouze dvousložkové – to ale chceme, neboť zadané body leží v rovině a tedy mají pouze dvě souřadnice). Bude-li z-ová souřadnice součinu kladná, |∠ABC| < 180°, bude-li záporná, |∠ABC| > 180° (rozmyslete si, jak to plyne z bodu 3).

Program

Pavel Čížek

16-2-4 Křížový král (Zadání)

Hojnost neoptimálních řešení, která jsme dostali, zdá se nasvědčovat tomu, že drak je v posledních letech výjimečně sytý a dobře naladěný, či že mu možná posledních pár set let nejde počítání pokusů tak bystře, jako ve starých dobrých časech udatných a hlavně křupavých těch, no, rytířů. Zde budeme ctěnému publiku demonstrovati zaručeně spolehlivý návod, kterak draka důmyslem svým přechytračiti (čili tzv. návod na draka).

Abychom si zjednodušili práci, předpokládejme bez újmy na obecnosti, že nehádáme čísla od 1 do N, nýbrž od 0 do N-1 a že N je mocnina dvojky (kdyby nebylo, stačí N zvýšit, čímž si, jak uvidíme, pohoršíme jen nepatrně).

Kdyby drak nelhal (což je podobně pravděpodobné, jako kdyby peklo zamrzlo a turecký med byl zadarmo… ale potěšme se tou představou aspoň chviličku), bylo by všechno jednodušší: stačilo by se postupně vyptat na hodnoty jednotlivých bitů čísla, tj. v i-tém kroku hry nabídnout drakovi ta čísla, jejichž i-tý bit je jedničkový. Takto bychom číslo uhodli po  log N krocích ( log bude vždy značit dvojkový logaritmus). Podobnost s půlením intervalů není nikterak náhodná. Také si všimněte, že naše strategie nijak nespoléhá na to, že hádáme číslo z intervalu – kdybychom volili mezi nějakými obecnými možnostmi a₀,… ,a_N, postupovali bychom úplně stejně, až na to, že bychom se nerozhodovali podle bitů čísel a_i, nýbrž podle bitů jejich indexů i.

Jenže drak samozřejmě lže (a peklo není studené a turecký med je nekřesťansky drahý…), takže když se zeptáme stejně jako předtím, nedostaneme jednoznačný výsledek, nýbrž více možností: jednak tu dřívější, odpovídající tomu, že drak nelhal, a dále log N dalších, odpovídajících všem možným otázkám, na které drak mohl odpovědět lživě. Ale jaképak s tím ciráty, použijeme ještě jednou stejnou strategii, tentokráte ovšem pouze na zbylých log N+1 možností (zde použijeme trik s indexy). Na to budeme potřebovat ⌈ log(1+ log N)⌉ otázek.

Leč drak nám také mohl lhát během této druhé fáze, proto mezi první a druhou fázi přidáme ještě jeden dotaz, kterým si ověříme, zda výsledek první fáze byl správný a pokud byl, druhou fázi ani nespustíme.

Nyní si rozmysleme, jak by nám drak mohl lhát: Pokud lže v první fázi, ověření neprojde a druhá fáze (určitě bez lži) najde správný výsledek. Pokud lže v ověření, jsou všechny ostatní odpovědi správně a druhá fáze opět vydá správný výsledek. Kdyby se vyskytovala lež v druhé fázi, znamenalo by to, že odpovědi jak v první fázi, tak během ověření byly pravdivé, což by ovšem znamenalo, že jsme se do druhé fáze ani nedostali.

Celkem jsme potřebovali (včetně zaokrouhlení na mocninu dvojky) ⌈ log N⌉+ ⌈ log(1 + ⌈ log N⌉)⌉+ 1 otázek, což pro N=1 000 000 opravdu dá kýžených 26. Otázky a odpovědi zvládneme zpracovat jednoduchým programem s časovou složitostí O(N· log N) a paměťovou O(N).

Pozor, matematika! Pro odolnější povahy připojíme navíc důkaz (skoro)optimality našeho řešení. Představme si, že máme program hádající číslo pomocí binárních otázek, přičemž každá otázka je jednoznačně určena odpověďmi na předcházející otázky. Předpokládejme navíc, že program pokaždé použije stejný počet r otázek (pokud nepoužije, můžeme vždy na konec doplnit zbytečné otázky, které nijak neovlivní výsledek). Přiřaďme každému číslu x posloupnost p₁(x), … , p_r(x) odpovědí (kódovaných 0=ne, 1=ano), které vedou k tomuto číslu bez lhaní, a dále posloupnosti p

i

1

(x), … , p

i

r

(x) pro i=1,… ,r popisující odpovědi v případě, že drak zalhal při i-té otázce.

Snadno nahlédneme, že všech r+1 posloupností odpovídajících témuž číslu musí být navzájem různých (dvěma různými lžemi není možné dojít k témuž výsledku) a že libovolná posloupnost pro číslo x musí být různá od libovolné posloupnosti pro každé jiné číslo y (protože jinak bychom nebyli schopni z posloupnosti odpovědí jednoznačně zrekonstruovat drakovo číslo).

Existuje tedy N ·(r+1) různých posloupností odpovědí, ty se ovšem musí vejít do množiny všech možných binárních posloupností délky r, kterých je 2^r, a proto musí platit N ·(r+1) ≤ 2^r, čili N ≤ 2^r / (r+1), což nám pro každý počet dotazů r říká, kolik nejvýše čísel jsme schopni rozlišit. Pokud zkusíme nerovnost „obrátit“, vyjde nám opravdu přibližně r≥ log N + log log N, čili náš algoritmus je velice blízko k optimu.

Pro ty, jimž by nedalo spát, že jsme jim nabídli řešení jenom skoro optimální, přidáváme konstrukci fungující pro libovolné r=2^z-1, která opravdu dosáhne maximálního možného N, které nám z naši nerovnosti vyšlo, tedy N=2^r/(r+1)=2^r-z. Nejdříve si sestrojíme binární kód se vzdáleností 3, čili množinu N dvojkových posloupností délky r (těm budeme říkat slova) takových, že každé dvě slova se liší v alespoň třech prvcích. K tomu stačí vzít všechny možné (r-z)-bitové posloupnosti (těch je N) a za každou z nich přidat z kontrolních bitů, abychom dosáhli požadované vzdálenosti. Původním bitům budeme říkat datové a oindexujeme si je z-cifernými dvojkovými čísly, přičemž vynecháme nulu a všechna čísla obsahující právě jednu jedničku (takže nám zbude 2^z-z-1=r-z indexů, jak potřebujeme). Kontrolní bity pak spočítáme takto: i-tý kontrolní bit bude určovat paritu datových bitů, jejichž index má i-tý bit jedničkový (parita je 0, pokud je mezi vybranými datovými bity sudý počet jedniček, jinak je 1). Příklad pro N=11 a z=4 následuje:

Každá dvě sestrojená slova se budou lišit alespoň jedním bitem v datové části. Pokud se liší právě jedním, budou se lišit i alespoň dvěma kontrolními bity (protože v indexu změněného datového bitu jsou alespoň dvě jedničky). Kdyby se datové části lišily dvěma bity, musí mít jejich indexy alespoň jeden bit rozdílný, takže alespoň jeden kontrolní bit se také liší. Čili každá dvě slova se liší v alespoň třech bitech, jak jsme slíbili.

Naši množinu slov lze použít jako samoopravný kód na opravu jedné chyby: pokud nám někdo pošle libovolné ze slov a při přenosu nastane nejvýše jedna chyba, jsme schopni jednoznačně určit, které slovo bylo vysláno. (Pokud by se slovo x změněné v jednom bitu shodovalo se slovem y změněným rovněž nejvýše v jednom bitu, znamenalo by to, že slova x a y se liší v max. dvou bitech, což víme, že není možné.)

Stejným způsobem ovšem můžeme komunikovat s drakem: číslům 0 až N-1 přiřadíme našich N slov a v i-tém kole se draka zeptáme na i-tý bit slova (vyjmenujeme čísla, jejichž slova mají tento bit jedničkový), čímž dostaneme hledané slovo s maximálně jedním bitem změněným a ten je možno opravit. Máme tedy strategii, která je optimální pro vybraná r (zkuste nahlédnout, že funguje a je optimální i pro ostatní r), je ji možno naprogramovat v čase O(N· log N) a paměti O(N) a dokonce nám i spolehlivě odhalí, zda drak zalhal. Náš program se nicméně bude držet mnohem jednoduššího prvního řešení, které je vždy o nejvýše 2 dotazy horší než optimální.

Program

Martin Mareš

16-2-5 Král Popleta (Zadání)

Nejprve si úlohu převedeme do řeči logických výrazů, čili výrazů nad proměnnými, které mohou nabývat pouze hodnot true a false. S těmito proměnnými můžeme provádět různé logické operace. Pro náš příklad budou důležité pouze dvě – negace, definovaná vztahy not false=true a not true=false, a disjunkce, definovaná vztahy false or false=false, false or true=true, true or false=true a true or true=true.

Pro každou provincii si zavedeme jednu proměnnou. Ta bude nabývat hodnoty true, pokud provincii získá Petr, a false, pokud ji získá Pavel.

Jak snadno nahlédneme, požadavky druhého a třetího typu jsou ve skutečnosti stejné – oba jsou splněny, pokud Petr (resp. Pavel) dostane alespoň jednu ze zmiňovaných provincií. Všechny požadavky tedy jdou vyjádřit jedním z těchto způsobů:

• Jestliže Petr požaduje provincii x, odpovídá tomu výraz (x).
• Jestliže Pavel požaduje provincii x, odpovídá tomu výraz (not x).
• Jestliže Petr požaduje provincii x nebo provincii y, odpovídá tomu výraz (x or y).
• Jestliže Pavel požaduje provincii x nebo provincii y, odpovídá tomu výraz (not x or not y).

Úkolem této úlohy je nalézt takové přiřazení hodnot true a false proměnným, aby co nejvíce z těchto výrazů mělo hodnotu true.

Protože každé tři požadavky lze splnit, platí:

• Pro žádnou proměnnou x se mezi požadavky nevyskytuje jak (x), tak (not x). Můžeme tedy bez újmy na obecnosti předpokládat, že všechny požadavky, které obsahují pouze jednu proměnnou, jsou ve tvaru (x) – pokud je požadavek ve tvaru (not x), ve všech požadavcích prohodíme x za not x a naopak. Tím zjevně nezměníme počet splnitelných požadavků – pokud by řešení nově vzniklé úlohy dávalo x hodnotu false, dáme mu v řešení původní úlohy hodnotu true a naopak.
• Nemůže se stát, že by (not x or not y), (x) a (y) byly požadavky. Tedy platí, že pro každý požadavek tvaru (not x or not y) se buď (x) nebo (y) nevyskytují jako požadavek.

Nyní se vraťme k řešení úlohy. Řešení, které se králi nelíbilo, bylo dát každé proměnné hodnotu true s pravděpodobností 1/2. Tím by splnil požadavky zmiňující dvě provincie s pravděpodobností 3/4, nicméně kazí mu to požadavky na jednotlivé provincie, které splní s pravděpodobností pouze 1/2. Zkusme tedy pomoci těmto požadavkům – dejme proměnné x, která se vyskytuje sama jako požadavek, hodnotu true s pravděpodobností p>1/2. Ostatní proměnné, které se nevyskytují jako samostatné požadavky, dále volme s pravděpodobností 1/2.

Požadavky typu (x) na jednotlivé provincie splníme s pravděpodobností p. Požadavky typu (not x or not y) splníme s pravděpodobností 1-p/2 pokud se právě jedno z x, y vyskytuje jako požadavek, nebo s pravděpodobností 3/4, pokud se tak nevyskytuje ani jedno z nich (3/4 je zřejmě větší než 1-p/2). Snadno si rozmyslíme, že ve všech ostatních případech bude pravděpodobnost splnění požadavku také alespoň 1-p/2. Dohromady tedy v průměru splníme alespoň min(p, 1-p/2) z požadavků. Toto číslo bude největší, pokud p=1-p/2, čili když p=2/3. V tomto případě jsme schopni splnit průměrně alespoň 2/3 požadavků.

Navíc se králi doneslo, že v sousedním království, kde měli podobný problém, si královští synové dokázali naklást takové požadavky, že z nich opravdu více než 2/3 splnit nešly. Tajná služba uvedla, že tyto požadavky byly natolik složitě formulované, že je není vhodné králi detailně prezentovat, a on se s tím spokojil – tedy i vy budete muset.

Zbývá vyřešit to, že ani k tomuto řešení král nehodlá propůjčit svou korunu. Chtěli bychom se tedy obejít bez generátoru náhodných čísel.

Nejprve si rozmysleme, jak přesně spočítáme, kolik požadavků v průměru splníme: Označme si p_x pravděpodobnost, že x bude true. Pak pravděpodobnost, že splníme požadavek

• (x) je p_x.
• (x or y) je 1-p_xp_y.
• (x or not y) je 1-p_x(1-p_y).
• (not x or y) je 1-(1-p_x)p_y.
• (not x or not y) je 1-(1-p_x)(1-p_y).

Když všechny tyto pravděpodobnosti sečteme, dostaneme hledaný průměrný počet splněných požadavků, označme si ho P.

Nyní řekněme, že bychom si napevno zvolili x jako true (tedy položili p_x=1) a ostatní proměnné volili stále náhodně se stejnými pravděpodobnostmi. Stejným postupem si spočítáme průměrný počet splněných požadavků v tomto případě a označíme si ho P_true. Analogicky, pokud si napevno zvolíme x jako false, v průměru splníme P_false. Nyní nahlédneme, že P = p_x·P_true + (1-p_x)·P_false. Řekněme, že volbu, které provincie dostane který syn, provádíme postupně počínajíce provincií x. S pravděpodobností p_x se rozhodneme dát provincii x Petrovi, v tom případě splníme průměrně P_true požadavků. S pravděpodobností (1-p_x) ji naopak dáme Pavlovi a splníme průměrně P_false požadavků. Dohromady tedy průměrně splníme p_x·P_true + (1-p_x)·P_false požadavků, což musí být rovno P.

P je tedy vážený průměr P_true a P_false, jedno z P_true a P_false tedy musí být alespoň tak velké jako P, protože kdyby byly obě menší než P, i jejich průměr by musel být menší než P. To nám říká, komu přidělit provincii x – pokud je P_true≥ P, dáme ji Petrovi, jinak Pavlovi. Nyní si za x do všech požadavků dosadíme zvolenou hodnotu a tento postup opakujeme s takto modifikovanými požadavky pro další proměnnou.

Algoritmus bude tedy pracovat takto: Na začátku nastavíme p_x pro všechny proměnné podle popsaného postupu (buď 1/2 nebo 2/3). Poté spočteme P (součet pravděpodobností splnění všech požadavků). Nyní vybereme jednu proměnnou x, které jsme ještě nedali žádnou hodnotu, a spočteme P_true a P_false. Tyto hodnoty se počítají jako P, jen jednou použijeme p_x=true a jednou p_x=false. Víme, že buď P_true nebo P_false je větší než P. Pokud tedy P_true > P_x, dáme proměnné x hodnotu true a p_x=1. Jinak položme x=false a p_x=0. Se změněnou hodnotou p_x přepočítáme  P, vybereme jinou proměnnou, které jsme ještě nedali hodnotu, a tu zpracujeme stejným způsobem. Algoritmus skončí, pokud jsme již všem proměnným přidělili nějaké hodnoty, čili jsme rozdělili všechny provincie.

V celém tomto postupu si nikde nepotřebujeme volit žádná náhodná čísla (pouze provádíme výpočty s pravděpodobnostmi), čímž jsme se vyhnuli nutnosti otloukat královskou korunu.

Časová složitost přímočaré implementace tohoto algoritmu je O(N²), kde N je počet požadavků, protože spočtení P nám trvá O(N) a počítáme ho třikrát pro každou proměnnou (kterých je nanejvýš dvakrát tolik, co požadavků). Ovšem pokud si všimneme toho, že při změně pouze jedné p_x se P „moc“ nezmění, a trochu se zamyslíme, můžeme časovou složitost snížit na O(N). Paměťovou složitost dokážeme také, při troše snahy, udržet na O(N).

Zdeněk Dvořák a Kráľ Dan