Matematická olympiáda – kategorie P

Řešení úloh ústředního kola (1. soutěžní den) 54. ročníku

P-III-1 Náhrdelníky

Pro vyřešení problému zřejmě stačí nalézt kódování náhrdelníků, které je nezávislé na rotacích a obracení. Pak dostaneme-li zadán původní kód, překódujeme si ho do nového kódování a na nový kód se zeptáme stroje. Bude nám tedy stačit pouze jeden dotaz pro každý náhrdelník.

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:

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-III-2 Mosty

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.

P-III-3 ALÍK

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:

xb-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.