Takové kódování dostaneme například takto: napíšeme si všechny kódy daného náhrdelníku a z nich si vybereme lexikograficky nejmenší. Zbývá tedy vymyslet, jak tento kód co nejrychleji nalézt. Vyřešme nejprve úlohu bez zrcadlení — tj. náhrdelník smíme pouze rotovat. Hledáme tedy pro zadaný řetězec R jeho lexikograficky nejmenší rotaci, označme si ji Rmin. Délku R si označíme r.
Budeme si postupně konstruovat množiny Sl (pro l mezi 0 a r) podřetězců R zadaných jejich počátečním prvkem a délkou. Pokud se na prvky Sl odkazujeme jako na úseky, máme na mysli tato jejich umístění v R, pokud se na ně odkazujeme jako na řetězce, máme na mysli hodnotu podřetězce R na dané pozici. Všechny úseky uvažujeme cyklicky podél R, tj. za posledním písmenem R následuje opět jeho první písmeno a naopak. Sl budou splňovat následující podmínky:
Na začátku položíme S0 rovnu množině všech úseků délky 0 (tj. bude v ní pro každou pozici v R jeden úsek délky 0) a všechny je prohlásíme za aktivní. Tím zřejmě splníme požadované vlastnosti.
Máme-li Sl, zkonstruujeme následující množinu tímto postupem:
Nechť aktivní úsek v X odpovídá řetězci s. Pak každý neaktivní úsek je prefixem s (z druhé podmínky pro X), a tedy je-li w=ss...sn aktivní řetězec v Sk, je libovolný jiný řetězec w'=ss...sn' jeho prefixem, neboť n' je prefix s a pokud w i w' obsahují stejný počet úseků s, n musí být alespoň tak dlouhé jako n' a n' je tedy prefix n.
Prefix Rmin délky k musí být w, neboť R nemá podřetězec délky (l+1) menší než s ani podřetězec délky |n| menší než n díky druhé podmínce pro X. Jakýkoliv řetězec w' v Sk kratší než k se na po něm následující pozici odlišuje od w, neboť jinak by n' muselo být alespoň o tuto jednu pozici delší. Každý úsek R odpovídající w je v S'k, neboť všechny jeho podúseky odpovídající s i n musely být v X díky druhé podmínce.
Tedy i druhá podmínka je splněna, což končí naši konstrukci.
Tento postup opakujeme, dokud v jeho třetím kroku neskončíme. To se nutně stane, neboť každým opakováním konstrukce prodloužíme aktivní řetězce alespoň o jeden znak.
Správnost algoritmu byla ukázána v popisu. Časová složitost je O(r). To nahlédneme následovně:
Paměťová složitost je také O(r), neboť v lineárním čase nestihneme víc paměti použít.
Zbývá ošetřit zrcadlení. To je ovšem snadné — nalezneme minimální rotaci pro obě zrcadlově symetrické varianty a z nich vezmeme tu menší. Tím zachováme lineární časovou složitost.
program Collector;
const MaxN = 100;
function ReverseString (var s : string) : string; { obrátí řetězec }
var i, n : integer;
rev : string;
begin
n := length (s);
rev := '';
for i := n downto 1 do
rev := rev + s[i];
ReverseString := rev;
end;
function RotateString (var s : string; k : integer) : string; { zrotuje řetězec }
var i, n : integer;
rot : string;
begin
n := length (s);
rot := '';
for i := k to n do
rot := rot + s[i];
for i := 1 to k - 1 do
rot := rot + s[i];
RotateString := rot;
end;
{ převede index v cyklickém řetězci do intervalu 1 .. total }
function RotIndex (idx, total : integer) : integer;
begin
while idx < 1 do
idx := idx + total;
while idx > total do
idx := idx - total;
RotIndex := idx;
end;
var activePositions : array [1 .. MaxN] of integer; { seznam aktivních pozic }
nActivePositions : integer; { počet aktivních pozic }
activeLength : integer; { délka aktivních řetězců }
segmentLength : array [1 .. MaxN ] of integer; { délka úseku začínajícího na dané pozici }
procedure ExtendByLetter (var s : string); { rozšíří aktivní úseky o písmeno }
var i, tActivePositions, position : integer;
ch, minCh : char;
begin
minCh := s[RotIndex (activePositions[1] + activeLength, length (s))];
for i := 2 to nActivePositions do
begin
ch := s[RotIndex (activePositions[i] + activeLength, length (s))];
if ch < minCh then
minCh := ch;
end;
tActivePositions := 0;
for i := 1 to nActivePositions do
begin
position := activePositions[i];
if s[RotIndex (position + activeLength, length (s))] = minCh then
begin
inc (tActivePositions);
activePositions[tActivePositions] := position;
inc (segmentLength[position]);
end;
end;
nActivePositions := tActivePositions;
inc (activeLength);
end;
{ zkontroluje, zda dva úseky na sebe navazují }
function ConsecutiveSegments (u1, u2, len : integer) : boolean;
var pos1, pos2, e1 : integer;
begin
pos1 := activePositions[u1];
e1 := RotIndex (pos1 + segmentLength[pos1], len);
pos2 := activePositions[u2];
ConsecutiveSegments := e1 = pos2;
end;
{ spojí po sobě následující úseky }
procedure MergeSegments (len : integer);
var i, j, tActivePositions, position, endPosition, tActiveLength: integer;
pActivePositions : array [1 .. MaxN] of integer;
begin
tActivePositions := 0;
tActiveLength := activeLength;
for i := 1 to nActivePositions do
begin
if ConsecutiveSegments (rotIndex (i - 1, nActivePositions), i, len) then
continue;
position := activePositions[i];
j := i;
while ConsecutiveSegments (j, rotIndex (j + 1, nActivePositions), len) do
begin
j := rotIndex (j + 1, nActivePositions);
inc (segmentLength[position], activeLength);
end;
endPosition := rotIndex (activePositions[j] + activeLength, len);
inc (segmentLength[position], segmentLength[endPosition]);
if segmentLength[position] > tActiveLength then
tActiveLength := segmentLength[position];
inc (tActivePositions);
pActivePositions[tActivePositions] := position;
end;
nActivePositions := 0;
for i := 1 to tActivePositions do
begin
position := pActivePositions[i];
if segmentLength[position] = tActiveLength then
begin
inc (nActivePositions);
activePositions[nActivePositions] := position;
end;
end;
activeLength := tActiveLength;
end;
{ nalezne lexikograficky nejmenší rotaci řetězce }
function MinimalRotation (var s : string) : string;
var i, l : integer;
begin
l := length (s);
nActivePositions := l;
activeLength := 0;
for i := 1 to nActivePositions do
begin
activePositions[i] := i;
segmentLength[i] := 0;
end;
while true do
begin
ExtendByLetter (s);
if nActivePositions * activeLength = l then
break;
MergeSegments (l);
end;
MinimalRotation := RotateString (s, activePositions[1]);
end;
{ nalezne lexikograficky nejmenší kód náhrdelníku }
function MinimalPosition (var s : string) : string;
var rev, minS, minRev : string;
begin
rev := ReverseString (s);
minS := MinimalRotation (s);
minRev := MinimalRotation (rev);
if minS < minRev then
MinimalPosition := minS
else
MinimalPosition := minRev;
end;
var n, i : integer;
code : string;
begin
readln (n);
for i := 1 to n do
begin
readln (code);
code := MinimalPosition (code);
if UzMam (code) then
writeln ('Podvod')
else
begin
writeln ('Kup to');
Pridej (code);
end;
end;
end.
Předvedeme si řešení s časovou složitostí O(NM), kde N a M jsou rozměry mapy areálu MO. Řešení si nejprve popíšeme obecně a teprve v druhé části se zaměříme na to, jak dosáhnout časové složitosti O(NM).
V mapě si nejdříve určíme jednotlivé budovy, které se v areálu MO nacházejí. Budovy si očíslujeme a každý čtvereček x nahradíme číslem budovy, které náleží. Poté uvážíme budovu číslo 1 a podíváme se na délky mostů, které lze z této budovy vést. Povšimněte si, že pokud si zvolíme políčko na okraji budovy a směr, pak je délka mostu (i budova, do které by vedl) již jednoznačně určena. Ze všech těchto mostů vezmeme nejkratší a ten do mapy přidáme. Tím spojíme budovu číslo 1 s budovou číslo i. Nyní se podívejme na všechny možné mosty, které bychom mohli vést z budovy číslo 1 nebo z budovy číslo i do ostatních budov, a nejkratší z nich přidejme do mapy. Obecně, když B je množina budov, které jsme již vzájemně propojili pomocí mostů, přidáme nejkratší možný most z budov v množině B do ostatních budov. Pokud je takových mostů více, přidáme libovolný z nich. Algoritmus skončí, pokud jsme již všechny budovy vzájemně propojili, anebo žádnou budovu nelze mostem k již propojeným budovám připojit (v takovém případě vypíšeme vhodnou zprávu). [Pro znalce dodáváme, že je není nic jiného než Jarníkův algoritmus na hledání minimální kostry grafu.]
Dále si rozmyslíme, že pokud se nám podaří propojit všechny budovy, pak je námi nalezené řešení optimální. Nechť M={m1,...,mk} je množina mostů, které obsahuje námi nalezené řešení, a předpokládejme, že most mi byl přidán jako i-tý most do řešení. Pro spor nyní předpokládejme, že existuje řešení M', jehož součet délek mostů je menší než součet délek mostů z množiny M. Navíc zvolme jako M' optimální řešení, které obsahuje jako podmnožinu co největší počáteční podposloupnost m1,...,ml, tj. {m1,...,ml} ⊆ M' a l je maximální možné. Protože M ≠ M', musí platit l<k. Nechť B je množina budov, které jsou vzájemně propojeny mosty m1,...,ml, a nechť j je číslo budovy, do které vede z množiny B most ml+1. Protože mosty z množiny M' propojují všechny budovy, existuje cesta z množiny budov B do budovy číslo j používající mosty z M'. Uvažme nejkratší takovou cestu m'1,...,m'l'. Z volby mostu ml+1 plyne, že most m'1 není kratší než most ml+1. Nahraďme nyní v M' most ml+1 mostem m'1. Součet délek mostů se tímto krokem nezvýšil. Navíc všechny budovy jsou stále propojeny: místo mostu m'1 lze použít objížďku tvořenou mosty ml+1,m'l',...,m'2. To je ale spor s volbou množiny M' jako optimálního řešení, které obsahuje co největší počáteční podposloupnost m1,...,ml. Námi nalezené řešení M je tedy optimální. Zaměřme se ještě na to, jak právě popsaný algoritmus implementovat, abychom dosáhli časové složitosti O(NM). Rozpoznání jednotlivých budov snadno zvládneme v čase O(NM) - mapu postupně procházíme a v okamžiku, kdy narazíme na políčko x, prohledáme (do hloubky nebo do šířky) v mapě oblast tvořenou touto budovou a všechny políčka x nahradíme číslem nově nalezené budovy. Tento krok zřejmě vyžaduje čas O(NM), neboť každé políčko mapy navštívíme nejvýše dvakrát (jednou při průchodu mapou a podruhé při označování budovy). Nyní spustíme druhou fázi algoritmu, ve které budeme budovy mezi sebou propojovat mosty. Označme K celkový počet budov. Abychom mohli rychle rozpoznat, které budovy jsme již vzájemně propojili, budeme používat pomocné pole velikosti K, kde si pro každou budovu uložíme, zda je již s budovou číslo 1 spojena či není. Z každého okrajového políčka budovy číslo 1 vyšleme současně paprsky (nahoru a dolů): v prvním kroku se paprsky nacházejí na políčkách sousedících přímo s budovou číslo 1 (viz obrázek), v druhém kroku jsou ve vzdálenosti 2, atd. Pokud paprsek narazí na budovu s číslem 1 či opustí mapu, již ho nadále neprodlužujeme. Takto postupujeme, dokud první paprsek nenarazí na jinou budovu. Řekněme, že tato budova má číslo i. Zřejmě dráha, kterou paprsek urazil, odpovídá nejkratšímu možnému mostu z budovy číslo 1 do jiné budovy. Tento most přidáme do mapy a budovy vzájemně propojíme.
...... ...... ...... ...^^. ...... ...... ...... .ii... .ii... .ii^^. .ii||. .ii... .ii... .ii... ...... ...^^. ...||. ...||. ...... .^^... .|.... ...xx. ...xx. ...xx. ...xx. .^^xx. .||xx. .|.xx. ....x. ...vx. ...^x. .^^.x. .||.x. .||.x. .|..x. ....x. ...^x. .^^vx. .||.x. .||.x. .||.x. .|..x. ...xx. .^^xx. .||xx. .||xx. .||xx. .||xx. .|.xx. .xxx.. .xxxv. .xxx.. .xxx.. .xxx.. .xxx.. .xxx..
Paprsky putující v mapě — zobrazení po jednotlivých krocích}
Poté vyšleme paprsky z budovy číslo i a budeme je prodlužovat, dokud nenarazíme na jinou budovu nebo jejich délka nebude stejná jako délka paprsků vyslaných z budovy číslo 1. V okamžiku, kdy délka paprsků vyslaných z budovy číslo i dosáhne délky paprsků vyslaných z budovy číslo 1, začneme prodlužovat současně jak paprsky vyslané z budovy číslo 1, tak i ty vyslané z budovy číslo i. Pokud však dříve narazíme na jinou budovu, řekněme s číslem i', připojíme ji mostem k budově číslo i. Z budovy číslo i' vyšleme paprsky, dokud nenarazíme na jinou budovu nebo jejich délka nedosáhne délky paprsků vyslaných z budovy číslo i. V prvním případě vyšleme paprsky z nově připojené budovy, v druhém případě začneme společně prodlužovat paprsky z budov číslo i a i', dokud nedosáhnou délky paprsků vyslaných z budovy číslo 1 (nebo nenarazíme na nepřipojenou budovu). Obecně, když narazíme na novou budovu, přerušíme prodlužování současných paprsků a vyšleme paprsky z nové budovy. Prodlužování paprsků obnovíme v okamžiku, kdy délka paprsků z nové budovy bude stejná jako délka paprsků, jejichž prodlužování jsme přerušili. Všimněte si, že v jednom okamžiku může být přerušeno prodlužování až K různých množin paprsků.
Je zřejmé, že výše popsaným postupem, připojujeme mostem vždy budovu, kterou lze spojit s již propojenými budovami nejkratším mostem. Protože každé políčko na mapě navštíví každý paprsek nejvýše dvakrát (jednou paprsek „letící” směrem nahoru a jednou směrem dolů), spotřebuje druhá fáze našeho algoritmu čas pouze O(NM). Samotné paprsky si budeme udržovat v poli délky 2NM setříděné dle jejich délky sestupně a vždy budeme prodlužovat první nejkratší paprsek, který se v poli nachází (abychom udrželi paprsky setříděné sestupně). Abychom se vyhnuli zbytečnému procházení tohoto pomocného pole, budeme si navíc udržovat odkazy na pozici paprsků, jejichž prodlužování jsme přerušili. Seznam paprsků bychom též mohli udržovat ve spojovém seznamu. Paměťová složitost právě popsaného řešení je, stejně jako jeho časová složitost, O(NM).
program mosty;
const MAX=100;
var mapa:array[1..MAX,1..MAX] of longint; { mapa areálu MO:
0 = volné prostranství, -1 = budova, -2 = most
1, 2, ... = čísla budov }
delka:longint; { součet délek mostů v řešení }
N,M:longint; { rozměry mapy }
procedure nacti;
var i, j: longint;
s: string[MAX];
begin
readln(M,N);
for i:=1 to N do
begin
readln(s);
for j:=1 to M do
if s[j]='.' then mapa[i][j]:=0 else mapa[i][j]:=-1
end;
end;
procedure urci_na_mape(cislo: longint; x: longint; y: longint);
{ určí na mapě budovu, jež obsahuje souřadnice x a y a
změní všechny -1 patřící této budově na cislo }
var fronta: array[1..MAX*MAX] of record x,y: longint end;
hlava, ocas: longint;
begin
mapa[x][y]:=cislo;
fronta[1].x:=x;
fronta[1].y:=y;
hlava:=0;
ocas:=1;
while hlava<ocas do
begin
inc(hlava);
x:=fronta[hlava].x;
y:=fronta[hlava].y;
if x>0 then
if mapa[x-1][y]=-1 then
begin
mapa[x-1][y]:=cislo;
inc(ocas);
fronta[ocas].x:=x-1;
fronta[ocas].y:=y;
end;
if y>0 then
if mapa[x][y-1]=-1 then
begin
mapa[x][y-1]:=cislo;
inc(ocas);
fronta[ocas].x:=x;
fronta[ocas].y:=y-1;
end;
if x<N then
if mapa[x+1][y]=-1 then
begin
mapa[x+1][y]:=cislo;
inc(ocas);
fronta[ocas].x:=x+1;
fronta[ocas].y:=y;
end;
if y<M then
if mapa[x][y+1]=-1 then
begin
mapa[x][y+1]:=cislo;
inc(ocas);
fronta[ocas].x:=x;
fronta[ocas].y:=y+1;
end;
end;
end;
procedure pridej_most(x, y, delka, smer: longint);
begin
while delka>0 do
begin
x:=x+smer;
mapa[x][y]:=-2;
dec(delka);
end;
end;
function propoj:boolean;
var paprsky:array[1..2*MAX*MAX] of
record
x, y: longint; { aktuální pozice paprsku }
smer: longint; { směr pohybu paprsku, -1 nahoru, +1 dolů }
delka: longint; { délka paprsku }
end;
paprsku:longint;
procedure pridej(x, y: longint);
var fronta: array[1..MAX*MAX] of record x,y: longint end;
hlava, ocas: longint;
cislo: longint;
begin
cislo:=mapa[x][y];
mapa[x][y]:=0;
fronta[1].x:=x;
fronta[1].y:=y;
hlava:=0;
ocas:=1;
while hlava<ocas do
begin
inc(hlava);
x:=fronta[hlava].x;
y:=fronta[hlava].y;
inc(paprsku);
paprsky[paprsku].x:=x;
paprsky[paprsku].y:=y;
paprsky[paprsku].smer:=+1;
paprsky[paprsku].delka:=0;
inc(paprsku);
paprsky[paprsku].x:=x;
paprsky[paprsku].y:=y;
paprsky[paprsku].smer:=-1;
paprsky[paprsku].delka:=0;
if x>0 then
if mapa[x-1][y]=cislo then
begin
mapa[x-1][y]:=0;
inc(ocas);
fronta[ocas].x:=x-1;
fronta[ocas].y:=y;
end;
if y>0 then
if mapa[x][y-1]=cislo then
begin
mapa[x][y-1]:=0;
inc(ocas);
fronta[ocas].x:=x;
fronta[ocas].y:=y-1;
end;
if x<N then
if mapa[x+1][y]=cislo then
begin
mapa[x+1][y]:=0;
inc(ocas);
fronta[ocas].x:=x+1;
fronta[ocas].y:=y;
end;
if y<M then
if mapa[x][y+1]=cislo then
begin
mapa[x][y+1]:=0;
inc(ocas);
fronta[ocas].x:=x;
fronta[ocas].y:=y+1;
end;
end;
while ocas>0 do
begin
mapa[fronta[ocas].x][fronta[ocas].y]:=cislo;
dec(ocas)
end
end;
var budov:longint;
napojeno:array[1..MAX] of boolean;
i,j:longint;
pozice:array[0..MAX] of
record
kde: longint; { pozice v poli paprsky, odkud se zpracovává paprsek }
kam: longint; { pozice v poli paprsky, kam se ukládá prodloužený paprsek }
end;
pozic:longint;
begin
{ nejdříve nalezneme budovy }
budov:=0;
paprsku:=0;
for i:=1 to N do
for j:=1 to M do
if mapa[i][j]=-1 then
begin
inc(budov);
urci_na_mape(budov,i,j);
if budov=1 then
begin
pridej(i,j);
end;
end;
{ nyní si nainicializujeme zbylé datové struktury }
delka:=0;
napojeno[1]:=true;
for i:=2 to budov do napojeno[i]:=false;
pozic:=0;
pozice[0].kde:=1;
pozice[0].kam:=1;
{ sledujeme paprsky a přidáváme mosty }
while paprsku>0 do
begin
if pozic=0 then
begin
pozice[1].kde:=1;
pozice[1].kam:=1;
pozic:=1;
end;
if paprsky[pozice[pozic-1].kde].delka > paprsky[pozice[pozic].kde].delka+1 then
begin
pozice[pozic+1].kde:=pozice[pozic].kde;
pozice[pozic+1].kam:=pozice[pozic].kam;
pozice[pozic].kde:=pozice[pozic].kam;
inc(pozic);
end;
while pozice[pozic].kde<=paprsku do
begin
if (paprsky[pozice[pozic].kde].x+paprsky[pozice[pozic].kde].smer<1) or
(paprsky[pozice[pozic].kde].x+paprsky[pozice[pozic].kde].smer>N) then
begin
inc(pozice[pozic].kde);
continue;
end;
paprsky[pozice[pozic].kam].x:=paprsky[pozice[pozic].kde].x+paprsky[pozice[pozic].kde].smer;
paprsky[pozice[pozic].kam].y:=paprsky[pozice[pozic].kde].y;
paprsky[pozice[pozic].kam].smer:=paprsky[pozice[pozic].kde].smer;
paprsky[pozice[pozic].kam].delka:=paprsky[pozice[pozic].kde].delka+1;
inc(pozice[pozic].kde);
if mapa[paprsky[pozice[pozic].kam].x][paprsky[pozice[pozic].kam].y]>0 then
if napojeno[mapa[paprsky[pozice[pozic].kam].x][paprsky[pozice[pozic].kam].y]] then
continue
else
begin
i:=paprsky[pozice[pozic].kam].x;
j:=paprsky[pozice[pozic].kam].y;
dec(paprsky[pozice[pozic].kam].delka);
delka:=delka+paprsky[pozice[pozic].kam].delka;
pridej_most(i,j,paprsky[pozice[pozic].kam].delka,-paprsky[pozice[pozic].kam].smer);
if paprsky[pozice[pozic].kam].delka>1 then
begin
inc(pozic);
pozice[pozic].kam:=paprsku+1;
pozice[pozic].kde:=paprsku+1;
end;
napojeno[mapa[i][j]]:=true;
pridej(i,j);
break;
end
else
inc(pozice[pozic].kam);
end;
if pozice[pozic].kde>paprsku then
begin
paprsku:=pozice[pozic].kam-1;
dec(pozic);
end;
end;
{ zkontrolujeme, že jsme propojili všechny budovy }
propoj:=true;
for i:=1 to budov do
if not napojeno[i] then
propoj:=false
end;
procedure vypis;
var i, j: longint;
begin
writeln('Celková délka mostů v optimálním řešení je ',delka,'.');
for i:=1 to N do
begin
for j:=1 to M do
case mapa[i][j] of
0: write('.');
-2: write('|');
else write('x');
end;
writeln
end
end;
begin
nacti;
if propoj then
vypis
else
writeln('Všechny budovy nelze propojit mosty.');
end.
Nejprve předvedeme řešení v konstantním čase s kvadraticky velkými registry. Jeho ingrediencemi budou triky použité v příkladech v zadání a ve vzorových řešeních minulých kol. Hodit se nám bude zejména násobení pro vytvoření mnoha kopií daného bloku bitů současně, zbytek po dělení, který naopak dokáže mnoho kopií posčítat do jednoho bloku, a operace typu x and (x-1) pro nalezení nejnižšího jedničkového bitu.
My bychom ovšem potřebovali najít bit nejvyšší, a tak si číslo nejprve obrátíme (na to nám konstantní čas a kvadratický prostor stačí, viz řešení krajského kola), pak nalezneme nejnižší jedničku (této funkci budeme říkat Lowl) a odečteme od velikosti vstupu.
Funkci Lowl naprogramujeme následovně: vypočteme (x or (x-1)) + x, čímž se nám objeví jedničky právě na místě nul vpravo od poslední jedničky a zbytek čísla bude nulový. Hledaná hodnota je tedy počet těchto jedniček. Ten zjistíme tak, že násobením vhodnou konstantou vytvoříme N kopií čísla, v každé kopii andem vynulujeme všechny bity kromě jednoho (v nulté kopii nultého, v první prvního atd.), vzniklé číslo pomyslně přerozdělíme na bloky velikosti o 1 větší, čili všechny nevynulované bity budou nejnižšími bity bloku, a ty můžeme operací modulo 1N+1 snadno sečíst. To jsme už také jednou použili v řešení krajského kola, ale pro osvěžení si nakresleme, jak to bude vypadat:
|x3x2x1x0|x3x2x1x0|x3x2x1x0|x3x2x1x0| (N kopií bloku velikosti N) |x30 0 0 |0 x20 0 |0 0 x10 |0 0 0 x0| (bity, které chceme sečíst) |x3|0 0 0 0 x2|0 0 0 0 x1|0 0 0 0 x0| (bloky velikosti N+1)Program bude velice jednoduchý:
x =0i 1 α a := MirrorN(x) a =β 1 0i (zrcadlení N-bitového čísla) y := a or (a-1) y =β 1 1i y := y + x y =0N-i 1i y := y * (0N-11)N y =(0N-i 1i)N y := y and (10N-1)(010N-2)...(0N-210)(0N-11) y =(0N)...(0N)(0N-i10i-1)...(0N-11) = (0N+1)N-i(0N1)i y := y mod 1N+1 y =i=Lowl(a) y := N-1-y y =Log(x)
My se ovšem s kvadratickou pamětí nespokojíme a zredukujeme ji na lineární. Uděláme to tak, že si vstup rozdělíme na řádově Sqrt(N) bloků velikosti řádově Sqrt(N), každý blok zkomprimujeme do jednoho bitu (který bude jedničkový, pokud se uvnitř bloku vyskytuje alespoň jedna jednička) a spočítáme logaritmus vzniklého čísla použitím předchozího algoritmu (naše číslo má jen Sqrt(N) bitů, vzhledem k čemuž máme v N-bitovém registru k dispozici kvadraticky velký prostor). Logaritmus nám řekne, ve kterém bloku se nachází nejlevější jednička a pro tento blok spustíme předchozí algoritmus znovu, čímž dopočítáme, kde přesně jednička je.
Zbývá vyřešit, jak přesně kompresi provést a jak se vyrovnat s těmi N, která nejsou druhými mocninami. Za velikost bloku zvolíme b=HorniCelaCast(Sqrt(N)) + 1 a vstup rozdělíme na b-1 bloků (jelikož b.(b-1)≥ Sqrt(N+1).Sqrt(N) > N, musíme ještě přidat pár nul na začátek, které nám neovlivní výsledek). Použijeme pracovní registry o b2=O(N) bitech.
Pokud nastavíme nejvyšší bit každého bloku na 1 a od každého bloku odečteme jedničku, změní se nejvyšší bity na 0 právě v blocích, které byly (až na nejvyšší bit) celé nulové, jinde 1 zůstane. Pak přiorujeme původní nejvyšší bity, takže pro každý blok nyní máme 1 nebo 0 podle toho, zda obsahoval jedničku či nikoliv. Tyto bity už stačí jen přesunout k sobě, k čemuž použijeme opět pomyslné přerozdělení bloků a modulo. Obrázek popisuje situaci pro 3 bloky o čtyřech bitech:
Program bude vypadat takto:
x =βb-2...β0 (b-1 bloků o b bitech) z := x or (10b-1)b-1 z =(1...)...(1...) z := ((z-(0b-11)b-1) or x) and (1b-10)b-1 z =(zb-20b-1)...(z00b-1) (zkomprimované bloky) z := z shr b-1 z =(0b-1zb-2)...(0b-1z0) z := z mod 1b-1 z =zb-2... z0 i := Log(z) i =<číslo bloku s nejvyšší jedničkou> r := (x shr (b*i)) and 1b r =<blok s nejvyšší jedničkou> j := Log(r) j =<pozice nejvyšší jedničky uvnitř bloku> y := b*i + j y =<pozice jedničky uvnitř původního čísla>
Tento program počítá dvojkový logaritmus stále v konstantním čase a stačí mu lineárně velké pracovní registry.
Poznámka: Doplňování čísla na délku zrovna b.(b-1) nebo převod úlohy na úlohu zrcadlovou vám mohou právem připadat jako zběsilé triky, které takřka nelze v omezeném čase soutěže vymyslet. Úloha je ale docela snadno řešitelná i bez nich, ovšem za cenu delšího programu a ošetřování různých okrajových případů, čemuž jsme se chtěli vyhnout.