Naivný postup

Keďže hľadáme lexikograficky najmenší výraz danej minimálnej dĺžky, prirodzene napadne prehľadávanie do hĺbky (DFS) s iteratívnym prehlbovaním (IDDFS): najskôr skúšame všetky výrazy dĺžky 1, potom dĺžky 3, 5, atď., a pri každej dĺžke prechádzame všetky trasy v lexikografickom poradí. Akonáhle nájdeme prvý výraz požadovanej hodnoty, vrátime ho.

Problém je, že počet trás rastie exponenciálne — z každého políčka vedú až 4 smery, no každý druhý krok je číslica a každý druhý znamienko, takže faktor vetvenia je najviac 4. Pri trase dĺžky $N$ je počet trás rádovo $4^{N/2}$. Pre veľké cieľové čísla môže byť potrebná dlhá trasa, a vtedy je tento prístup príliš pomalý.

Navyše väčší problém je, že nevieme, či vôbec musí existovať cesta ohraničenej dĺžky pre každé dotazované číslo. O tomto brute-force tak nevieme povedať, či je konečný, skúsiť ho sa však ukazuje postačujúce na vyriešenie prvej sady.

$N$ — dĺžka cesty (počet znakov výrazu)\ $W$ — šírka mriežky

Časová zložitosť: $O(4^{N/2})$\ Pamäťová zložitosť: $O(N)$ (zásobník rekurzie)

Dĺžka optimálnej trasy je ohraničená

Ukážeme, že pre každé dotazované číslo $q$ existuje výraz hodnoty $q$ s dĺžkou $O(S)$, kde $S$ je maximálne dotazované číslo. To nám dá hornú hranicu pre BFS.

Nastavenie. Nech $g = \gcd$ všetkých číslic na mriežke. Aby riešenie pre $q$ existovalo, musí byť $q$ násobkom $g$. Po vydelení všetkého číslom $g$ môžeme predpokladať $g = 1$.

Číslicu $a$ nazveme pozitívna (skr. poz), ak susedí aspoň s jedným znamienkom +, a negatívna (neg), ak susedí aspoň s jedným znamienkom -. Pretože $g=1$, existujú dve číslice $a, b$ také, že $\gcd(a,b)=1$.

Podľa toho, či sú $a,b$ poz alebo neg, rozlišujeme dva prípady.

Prípad 1: $a$ je poz a $b$ je neg (alebo naopak)

Nech $P$ je ľubovoľná najkratšia cesta z políčka s číslom $a$ do políčka s číslom $b$ (prechádza cez nejaké znamienko). Označme $q’$ hodnotu tejto trasy; musí platiť $|q’| \leq 200$.

Položme $t = q - q’$. Chceme vyjadriť $t$ ako $ax - by$ pre nezáporné celé čísla $x, y$.

Keďže $\gcd(a,b)=1$, spomedzi čísel $t, t+b, t+2b, \ldots, t+(a-1)b$ je práve jedno násobkom $a$. Nech je to $k$-te číslo v uvedenej postupnosti indexovanej od $0$. Potom zjavne stačí položiť $y = k$ a $x = (t + kb) / a$ a $ax - by = a(t + kb) / a - kb = t + kb - kb = t$ Teda existujú nezáporné $x, y$ s $y < a$ také, že $ax - by = t$. Dôležité je, že $y \leq a$ a $x \leq (t + ab) / a = t / a + b \leq 2q / a + b$ (lebo $k$ môže byť najviac $a$).

Výsledná trasa: začneme na políčku $a$ a $x$-krát ho zopakujeme so znamienkom +, potom prejdeme trasou $P$ a na políčku $b$ ho $y$-krát zopakujeme so znamienkom -. Celková hodnota je $ax + q’ - by = t + q’ = q$.

Teda dĺžka trasy nebude vďaka ohraničeniam na $x$ a $y$ väčšia ako $2q/a + a + |P|$, kde $|P|$ označuje dĺžku pôvodnej najkratšej cesty medzi políčkami.

Prípad 2: obe číslice sú poz (alebo obe neg)

Ak sú $a$ a $b$ obe poz (obe neg je symetrické), musí existovať aspoň jedna neg číslica $c$.

• Podprípad 2a: $\gcd(a,c)=1$ alebo $\gcd(b,c)=1$. Potom použijeme Prípad 1 s dvojicou $(a,c)$ resp. $(b,c)$ a vieme dorovnať hodnotu, ktorá nám vznikne na najkratšej ceste z $a$ do $c$, resp. $c$ do $b$.

• Podprípad 2b: $c$ je deliteľné každým prvočiniteľom $a$ aj každým prvočiniteľom $b$. Keďže $\gcd(a,b)=1$, majú $a$ a $b$ disjunktné množiny prvočiniteľov, takže $c$ musí byť deliteľné aspoň dvoma rôznymi prvočíslami.

Nenulové číslice 1–9 deliteľné aspoň dvoma rôznymi prvočíslami: - $6 = 2 \cdot 3$

Teda platí, že $c = 6$. Použijeme Chicken McNugget theorem - keďže $\gcd(a,b)=1$, každé dostatočne veľké celé číslo $t \geq (a-1)(b-1)$ vieme zapísať ako $t = ax + by$ pre nezáporné $x,y$. Nech $P$ je najkratšia trasa prechádzajúca cez $a$, $b$ a $c$, s hodnotou $q’$. Zvolíme nezáporné $z$ také, že $t + 6z \geq (a-1)(b-1)$, kde $t = q - q’$. Potom $t + 6z = ax + by$ pre nejaké nezáporné $x,y$.

Trasa: cesta $P$, potom $x$-krát $a$ so znamienkom +, $y$-krát $b$ so znamienkom + a $z$-krát $c$ so znamienkom -. Hodnota je $q’ + ax + by - 6z = q’ + t = q$. Opäť sa nám tak podarilo získať horné ohraničenie pre dĺžku cesty, keďže $z \leq q + ab$, $x \leq 2q / a$ a $y \leq 2q / b$

Záver: V každom prípade existuje trasa hodnoty $q$ s dĺžkou $O(S + W)$.

Optimálne riešenie: BFS so stavovým priestorom

Vytvoríme si graf, kde vrchol, resp. stavy budú trojice $(r, s, h)$. Trojica $(r, s, h)$ bude reprezentovať situáciu, kedy sme na políčku $(r, s)$ a prešli sme trasu, ktorej výraz má hodnotu $h$ (môže byť aj záporná).

Vďaka ohraničeniu dĺžky najkratších ciest vieme, že ak nás zaujímajú najkratšie cesty, ohraničenie na zaujímavé $h$ bude zhora aj zdola len nejakým konštantným násobkom ohraničenia na dĺžku cesty. Presnú hodnotu, ktorá $h$ ohraničí, už môžeme nájsť vyskúšaním rôznych. Či je postačujúca, uvidíme tak, že sa nám podarí nájsť riešenia pre všetky dotazy. Podstatné je, že vieme, že existuje a nebude príliš veľká. Domyslieť hrany, ktoré graf bude mať, už je jednoduchá záležitosť.

Pomocou multisource BFS v tomto grafe (kde zdroje budú všetky vrcholy zodpovedajúce políčkam s hodnotou ich číslice) vieme vypočítať najkratšiu cestu pre všetky dotazované hodnoty. Počet vrcholov je $W^2 \cdot O(S + W)$. Každý vrchol navštívime najviac raz, takže celková zložitosť prehľadávania je lineárna od počtu vrcholov.

Aby sme zaručili, že prvý nájdený stav s hodnotou $q$ zodpovedá lexikograficky najmenšiemu výrazu minimálnej dĺžky, BFS musí rozvinúť stavy v správnom poradí: pri rovnakej dĺžke prednostne tie s lexikograficky menším výrazom. Toho docielime tak, že v prípade, že si pamätáme stavy vo fronte v skupinách, kde v rámci skupiny platí, že do stavov v nej sme sa dostali lexikograficky rovnakým výrazom. Pri BFS tak do ďalšej úrovne pridáme do fronty primárne podľa poradia skupín a skupiny usporiadame lexikograficky podľa posledného znaku (resp. dvojice znakov znamienko, číslica), ktorým im cestu rozšírime. Na začiatku budú skupiny určené podľa počiatočnej číslice trasy.

Pre každý dotaz $q$ stačí nájsť ľubovoľný stav $(\cdot, \cdot, q)$ na políčku s číslicou a zrekonštruovať cestu spätným prechodom cez uložené predchodcové smerníky. Aby sme nemuseli pri každom dotaze spúšťať celé prehľadávanie, môžeme si zapamätať históriu prvého prehľadávania (ktoré spravíme kompletne, teda navštívime všetky stavy) a potom na základe toho už len v zložitosti od dĺžky trasy vypísať hľadanú trasu.

$W$ — šírka mriežky\ $S$ — maximálne dotazované číslo\ $Q$ — počet dotazov

Časová zložitosť: $O(W^2 \cdot (S + W) + Q(S + W))$\ Pamäťová zložitosť: $O(W^2 \cdot (S + W))$