8. Escargot vzorové riešenie

6 4
.#..
...#
#@#.
##..
#...
.@..

5
@ N
@ E
# S
@ E
@ E

4 4
##..
@...
#@.#
..##

-1

Keďže tvar žiadnej z dvoch množín sa nemení ani neotáča, vždy vieme stav mriežky popísať jedinou dvojicou celých čísel, ktorá označuje, ako sú obe množiny voči sebe posunuté (vzhľadom ku pôvodnemu stavu \(0,0\)). Konkrétne označme dvojicou parametrov \(S[i,j]\) taký stav plochy, ktorý dostaneme, keď z počiatočného rozloženia množinu @ posunieme o \(i\) políčok dole a \(j\) políčok doprava (ignorujúc možné kolízie, či už počas presunu, alebo vo finálnom umiestnení). Uvedomme si, že ťahy, ktoré v úlohe vykonávame, sú v takejto reprezentácií vlastne vždy len zmenou jedného z dvoch parametrov o \(1\), keďže buď posunieme o políčko množinu @, alebo množinu #, čo je to isté, ako posunúť množinu @ v opačnom smere. Našou úlohou je teda, keď si všetky tieto stavy predstavíme ako nekonečnú mriežku, z počiatočného stavu \(S[0,0]\) nájsť cestu po susedných stavoch takú, že množiny oddelíme, teda dosiahneme stav \(S[i,j]\), kde buď \(|i| \geq m\) alebo \(|j| \geq n\) (všetky takéto stavy nazývajme vonkajšie, a zvyšných \((2m-1)(2n-1)\) stavov nazývajme vnútorné). Problémom je, že niektoré z týchto stavov môžu byť nepriechodné, pokiaľ by daný posun množín spôsobil kolíziu na nejakom políčku (nikdy nie stav \(S[0,0]\), označujúci počiatočnú pozíciu, ani žiaden z vonkajších stavov). Pokiaľ by sme teda pre všetky vnútorné stavy vypočítali, či sú priechodné, alebo nie, potom nám už stačí jednoducho akýmkoľvek prehľadávacím algoritmom nájsť cestu z \(S[0,0]\) do akéhokoľvek vonkajšieho stavu, čo sa stihne v rozumnom čase \(O(mn)\). Zároveň máme aj garantované, že ak takáto cesta existuje, očividne nebude dlhšia než celkový počet vnútorných stavov, čo sa určite zmestí do limitu v zadaní \(10^7\). Až túto cestu nájdeme, skonvertujeme ju do požadovaného formátu jednoducho tak, že každý pohyb bude posun množinou @, a potom každý pohyb medzi stavmi v nejakom smere zodpovedá posunu tejto množiny v tom istom smere.

Teraz sa črtá hlavný problém riešenia: ako pre všetky vnútorné stavy určiť, či sú priechodné alebo nie?

Najjednoduchšie riešenie je zostrojiť pôvodne všade priechodnú mriežku, a potom pre každú dvojicu políčok na vstupe, kde jedno je @ a druhé #, vypočítať, pre aký posun sa dostanú na tú istú pozíciu, a zaznačiť, že zodpovedajúce políčko v mriežke je nepriechodné (keď # je v \(i_a\)-tom riadku a \(j_a\)-tom stlpci, a @ je v \(i_b\)-tom riadku a \(j_b\)-tom stĺpci, potom vzniká kolízia medzi nimi v stave \(S[i_a-i_b,j_a-j_b]\)). Tento postup ale môže trvať až \(O(m^2n^2)\), čo nie je dosť rýchle…

Pri zostrojení asymptoticky lepšieho riešenia nám pomôže algoritmus spomenutý v zadaní: fast fourier transform. Jedná sa o algoritmus, ktorý vynásobí dva polynómy dĺžky \(n\) v čase \(O(n \log n)\) (do detailov v tomto vzorovom riešení nepôjdeme). Toto možno s úlohou na prvý pohľad vôbec nesúvisí, v skutočnosti sa to ale dá na riešenie využiť. Aby sme pochopili ako, predstavme si prípad, že \(m=1\). V tomto prípade je vstupom jediný riadok. Interpretujme si tento riadok ako dvojicu vektorov boolov o dĺžke \(n\): platí, že \(a[i]\) značí, či je na \(i\)-tej pozícií znak #, a \(b[i]\) značí, či je na nej @. V tomto prípade platí, že \(S[0,i]\) je nepriechodný práve vtedy, keď existuje taká pozícia \(j\), že \(a[j] = 1\) aj \(b[j-i] = 1\) (pre indexy mimo poľa predpokladáme, že všetky sú nulové, pretože tam nie je žiadne políčko danej množiny). Už to vidíte? Nie? Upravme trochu vstup: zostrojme pole \(b'\) otočením poľa \(b\), aby so stúpajúcim \(i\) \(b'[i]\) označovalo pozície bližšie a bližšie k začiatku vstupu. Zároveň, keďže \(S\) má pozíciu \(S[0,0]\) v strede, a nie na začiatku, zadefinujme “poriadnejšie” pole \(S'\) tak, že pre \(0 \leq i \leq 2n-2\) \(S'[i] = S[0,i-n+1]\). Teraz si všimnime, že \(S'[i]\) je nepriechodný práve vtedy, keď existuje taká pozícia \(j\), že \(a[j] = 1\) aj \(b'[j-i] = 1\), teda inak povedané, existujú dve celé čísla \(j_1,j_2\), ktorých súčtom je \(i\), a na týchto pozíciach v poliach \(a\) a \(b'\) sú jednotky. To už sa nám určite podobá na násobenie polynómov - jednoducho si interpretujeme \(a\) a \(b'\) ako polynómy, kde každý koeficient je buď \(0\) alebo \(1\), a potom ich súčinom získame polynóm, ktorý má nenulový koeficient práve pri takom exponente \(i\), že existujú nenulové koeficienty v \(a\) a \(b\), ktoré sú pri exponentoch, ktoré sa sčítajú na \(i\). Tento výsledný súčin teda je žiadaným \(S'\).

Otázkou je teraz, ako tento postup rozšíriť na vstup pozostávajúci z viacerých riadkov. Chceli by sme zachovať vlastnosť, že dvojice indexov, ktoré majú rovnaký súčet, korešpondujú k vždy rovnako posunutým pozíciám na vstupe (keďže po vynásobení polynómov prispejú tieto dvojice k tomu istému posunu). Prvým očividným prístupom je jednoducho do polynómu \(a\) vložiť zaradom všetky pozície na vstupe - najprv prvý riadok, potom druhý, a tak ďalej, a do \(b'\) to isté, len reverznuté. Potom naozaj pre pozície, ktorých súčet indexov je \(i\), ak \(i < n\), platí, že sú všetky rovnako posunuté (prvá pozícia je v prvom riadku na mieste \(j_1\), druhá v poslednom na mieste \(n-1-j_2\), potom je vždy ich horizontálny rozdiel rovný \(n-1-j_2-j_1 = n-1-i\)). Len čo sa ale \(i\) rovná \(n\), nastane problém. Súčet indexov \(i\) totiž začnú mať aj políčka, ktoré sú v druhom a poslednom riadku (prvé políčko druhého riadku má index \(n\), posledné posledného má index \(0\)), ale aj políčka, ktoré sú stále len v okrajových riadkoch (posledné políčko prvého má index \(n-1\), predposledné posledného má \(1\)). A tieto očividne nemajú rovnaký rozdiel, líšia sa už vo vertikálnom rozdieli. Našim problémom teda je, že nejaký súčet indexov sa dá vyskladať z políčok v rôzne vzdialených riadkoch. Pomôže nám akoby si vytvoriť “nárazníkové zóny” medzi riadkami. Čo to znamená? Zostrojme \(a\) a \(b'\) trochu inak: Na pozíciach \(a[0]\) až \(a[n-1]\) je uložená informácia o prvom riadku vstupu, na \(a[2n-1]\) až \(a[3n-2]\) o druhom, a tak ďalej, vždy o \(i\)-tom riadku je informácia na pozíciách \(a[i(2n-1)]\) až \(a[i(2n-1)+n-1]\), štandardne zľava doprava. Podobne na pozíciach \(b'[0]\) až \(b'[n-1]\) je informácia o poslednom riadku, zprava doľava, a na \(b'[i(2n-1)]\) až \(b'[i(2n-1)+n-1]\) je informácia o \(i\)-tom riadku od konca. Dĺžka oboch týchto polí je \(2mn-m-n+1\). Zvyšok týchto polí nech je prázdny - teda akoby označovali políčka, ktoré sú voľné (v polynóme tam bude \(0\)). Čo teraz dostaneme vynásobením týchto polí ako polynómov? Označme ich súčin \(c\), toto pole bude veľkosti \(4mn-2m-2n+1 = (2m-1)(2n-1)\). Toto je rovnako veľa, ako je počet všetkých vnútorných stavov. Ukážeme, že toto nie je náhoda, a \(c\) presne popisuje priechodnosť všetkých vnútorných stavov, konkrétne \(c[y(2n-1)+x]\) je nenulový práve vtedy, keď je \(S[y-m+1,x-n+1]\) nepriechodný.

Pozrime sa na ľubovoľnú dvojicu políčok, ktorá môže spôsobiť kolíziu. Konkrétne nech je v riadku \(y\) a stĺpci \(x\) vstupu znak #, a v riadku \(y'\) a stĺpci \(x'\) vstupu znak @. Potom je korešpondujúca hodnota \(1\) na pozíciach \(a[y(2n-1)+x]\) a \(b'[(m-1-y')(2n-1)+n-1-x']\). To znamená, že po vynásobení táto dvojica zaručí nenulovosť v koeficiente na indexe rovnom súčtu dvoch pôvodných: \(c[y(2n-1)+x + (m-1-y')(2n-1)+n-1-x'] = c[(m-1 + y-y')(2n-1) + (n-1 + x-x')]\). Vidíme, že každá dvojica symbolov kolidujúca pri posune \(S[\Delta_y , \Delta_x]\) spôsobuje nenulovosť hodnoty \(c[(m-1+\Delta_y)(2n-1) + (n-1+\Delta_x)]\), čo znamená, že sme skonštruovali presne rovnakú konštrukciu, ako v pomalom riešení, ale namiesto prechádzania každej dvojice manuálne sme museli iba vynásobiť dva veľké polynómy.

Vidíme, že vhodným transformovaním vstupu na dvojicu polynómov o veľkosti \(2mn-m-n+1\) a ich vynásobením sme dostali tabuľku veľkosti \((2m-1)\) krát \((2n-1)\) (pozor! Tu sa dá urobiť chyba - FFT vytvorí polynóm rovnakej veľkosti ako tie vstupné - teda najprv musíme vstupné polynómy predĺžiť na túto dvojnásobnú veľkosť a novopridanú polovicu vyplniť nulami), v ktorej nám stačí pre vyriešenie úlohy jednoducho nájsť cestu spájajúcu stred s okrajom, prípadne rozhodnúť, že neexistuje.

Toto sa stíha v čase \(O((2mn-m-n+1) \log (2mn-m-n+1) + (2m-1)(2n-1)) = O(mn\log(mn))\) (ale FFT má pomerne vysokú konštantu, takže v praxi to až tak rýchle nebude… no pre vstup veľkosti danej v zadaní je rozdiel už dosť podstatný). Pamäťová zložitosť je \(O(mn)\), pretože FFT stačí lineárny priestor, a potom si pamätáme tabuľku priechodnosti posunov, ktorú prehľadávať dokážeme bez potreby väčšieho priestoru.