5. Éra vyhýbania vzorové riešenie

3 5
01101
10101
00011

11000

1 6
011011

100100

V tejto úlohe sme dostali \(n\) binárnych reťazcov dĺžky \(k\) a mali sme nájsť taký binárny reťazec dĺžky \(k\), ktorý bude mať čo najväčšiu minimálnu vzdialenosť od každého z \(n\) reťazcov. Vzdialenosť 2 reťazcov sme definovali ako počet pozícií, na ktorých sa tieto dva reťazce líšia.

Pozorovania

Vždy predtým, ako začneme riešiť nejakú úlohu je dobrý nápad pozrieť sa na obmedzenia vstupov. V tejto úlohe bolo \(n \leq 100\,000\), no \(k\) bolo iba do \(20\). Keď vidíme toto obmedzenie pre \(k\), hneď by nám malo napadnúť, že si môžeme dovoliť riešenie, ktoré má vo svojej zložitosti aj člen \(2^k\), alebo podobný.

Keďže si to môžeme dovoliť, tak pravdepodobne budeme chcieť vygenerovať všetky možné rozvrhy, ktorých je \(2^k\), pretože na každej z \(k\) pozícií môžu byť 2 rôzne hodnoty.

Keď už vieme, že asi budeme chcieť generovať všetky rozvrhy, tak ľahko vyriešime aj to, aby sme našli lexikograficky najmenší. Stačí, aby sme ich generovali v lexikografickom poradí a zobrali prvý vyhovujúci, ktorý nájdeme. O takomto generovaní rozvrhov sa dočítate v nasledujúcej sekcii.

Implementačné rady

Ak viete dobre používať bitové operácie, túto sekciu kľudne preskočte, nič nové sa v nej asi nedozviete.

Máme najviac 20-bitové rozvrhy. Môžeme sa na ne pozerať ako na binárne zápisy čísiel. Každý rozvrh si teda vieme pamätať ako jedno číslo. Nemusíme si rozvrhy pamätať ako stringy.

Teraz niečo ku generovaniu rozvrhov v lexikografickom poradí. Stačí si uvedomiť, ako funguje dvojková (a aj každá iná) sústava. Totiž, väčšie čísla sú lexikograficky väčšie, ako menšie čísla. Ak teda budeme prechádzať, čísla od \(0\) po \(2^k - 1\), tak vlastne prejdeme rozvrhy v lexikografickom poradí. Stačí sa vždy pozrieť na bitovú reprezentáciu aktuálneho čísla.

Ďalej sa pozrime na to, ako zistiť vzdialenosť 2 rozvrhov. Keď ich už máme ako 2 čísla, tak stačí spraviť \(xor\) týchto 2 čísiel a zrátať počet jednokových bitov vo výsledku. Rozmyslite si, prečo to funguje, je to veľmi jednoduché.

Niekde počas riešenia, či vypisovania výstupu sa nám asi bude hodiť vedieť zistiť, aký je \(i\)-ty bit nejakého čísla. Na to sa vo väčšine jazykov dajú pohodlne využiť bitové operácie. Aby sme zistili, aký

je \(i\)-ty bit čísla \(x\), môžeme spraviť (x & (1 << i)) > 0. Taktiež budeme možno chcieť vedieť zapnúť \(i\)-ty bit čísla \(x\). To spravíme ako x |= (1 << i) Ak neviete, prečo to funguje, nájdite si niečo o bitových operáciách a skúste si to rozmyslieť, nemal by to byť problém pochopiť.

Riešenie hrubou silou

Toto bude celkom priamočiare. Vygenerujeme si každý možný rozvrh. Pre každý z nich prejdeme cez všetkých \(n\) rozvrhov zo vstupu a zrátame ich vzdialenosť. Z týchto vzdialeností pre aktuálny rozvrh si zapamätáme minimum, pretože to je tá minimálna vzdialenosť od \(n\) rozvrhov zo vstupu. Každý vygenerovaný rozvrh nám dá nejaké takéto minimum. Z týchto miním chceme zobrať maximum. Rozvrh s touto maximálnou vzdialenosťou je náš hľadaný rozvrh.

Pre každý zgenerovaný rozvrh prejdeme všetkých \(n\) rozvrhov, takže časová zložitosť bude \(O(n2^k)\). Pamätáme si iba vstup, takže pamäť bude \(O(n)\).

Vzorové riešenie

V riešení hrubou silou sme pre každý vygenerovaný rozvrh odznova prechádzali všetkých \(n\) rozvrhov zo vstupu. To by sme chceli zrýchliť. Skúsme sa na vzdialenosť 2 rozvrhov pozerať skutočne ako na vzdialenosť. Pozerajme sa na ňu tak, že je to počet operácií zmeny bitu, ktoré musíme na jednom rozvrhu vykonať, aby sme sa dostali do druhého rozvrhu. Na vzdialenosť 1 od rozvrhu 01101 teda budú tie rozvrhy, ktoré z neho vieme dostať 1 zmenou, čo sú 11101, 00101, 01001, 01111 a 01100.

Všetky rozvrhy si teraz vieme predstaviť ako graf. Každý vrchol má stupeň (počet susedov) \(k\), pretože na ňom vieme spraviť \(k\) rôznych zmien. Z každého rozvrhu pôjdu hrany do rozvrhov, ktoré vieme z aktuálneho dostať na 1 zmenu. Takýto graf sa niekedy zvykne nazývať binárna kocka.

Koľko hrán má takýto graf? Z každého vrchola ide \(k\) hrán a vrcholov je \(2^k\), takže celkový počet hrán bude \(O(k2^k)\). To je pre naše obmedzenie na \(k\) stále tak málo, že si môžeme dovoliť tento graf prehľadať.

Čo v tomto grafe hľadáme? Zaujímajú nás vrcholy, ktoré sú čo najďalej od všetkých \(n\) vrcholov zo vstupu. Ak teda pustíme BFS zo všetkých vrcholov zo vstupu naraz a zrátame si tak najkratšie vzdialenosti do každého vrchola, stačí nám potom pozrieť sa na vzdialenosť každého vrchola (opäť v lexikografickom poradí) a zobrať ten s najväčšou vzdialenosťou.

Časová a pamäťová zložitosť

Časová zložitosť takéhoto BFS bude \(O(k2^k)\). Graf si nemusíme explicitne pamätať, pretože vždy vieme povedať, aké hrany idú z aktuálneho vrchola. Pamäť preto bude \(O(2^k)\).