Omówienie zadania Łazik marsjański (I etap XXXIII OI, tura zdalna)

Dana jest prostokątna plansza na torusie o $n$ wierszach i $m$ kolumnach ($2 \leq n, m \leq 10^6$). Na polu (0,0) znajduje się łazik. Chcemy znaleźć najkrótszy możliwy ciąg instrukcji GDPL (kodujących ruchy łazika: góra, dół, prawo, lewo), który, powtarzany w nieskończoność, pozwoli łazikowi odwiedzić wszystkie pola planszy.

Niech $W$ oznacza najkrótszy poprawny ciąg instrukcji dla planszy rozmiaru $n \times m$, a $w = |W|$ oznacza jego długość.

Przykłady i ograniczenie górne

Na początek spróbujmy pokazać jakieś poprawne ciągi instrukcji (niekoniecznie najkrótsze). Ciąg $\texttt{D}^{n-1}\texttt{P}\texttt{G}^{n-1}\texttt{P}$ (czyli $n-1$ razy w dół, raz w prawo, $n-1$ razy w górę, raz w prawo), odwiedza wszystkie pola w kolumnach 0, 1 i ustawia łazika na górnym polu kolumny 2. Tak więc powtórzenie tego ciągu $\lceil m/2 \rceil$ razy spowoduje odwiedzenie wszystkich pól planszy. Zatem $w \leq 2n$. Ciut mniej oczywiste jest, że ciąg $\texttt{D}^{n-1}\texttt{P}$ powtórzony $m$ razy również odwiedza wszystkie pola (i wraca na pole startowe). Zatem $w \leq n$.

Ograniczenie dolne

Gdyby ciąg $W$ składał się tylko z ruchów w górę i w dół, to łazik cały czas poruszałby się tylko w kolumnie 0. Jeśli ma odwiedzić jakieś inne kolumny, to ciąg $W$ musi zawierać ruch w poziomie. Symetryczny argument pokazuje, że musi zawierać jakiś ruch w pionie. Zatem $w \geq 2$.

Zaczynając z pola (0,0) i wykonując ruchy z $W$, łazik przesunie się na pewne pole $(r,c)$. Zatem, po $k$-krotnym wykonaniu ciągu instrukcji $W$, łazik znajdzie się na polu $(kr \bmod n, kc \bmod m)$. Jeśli więc $k$ jest podzielne zarówno przez $n$ jak i przez $m$, to dostajemy $kr \bmod n = 0$ oraz $kc \bmod m = 0$, więc łazik wraca na pole startowe. Jest tak w szczególności dla $k = \mathrm{lcm}(n, m) = \frac{nm}{\mathrm{nwd}(n,m)}$.

Ponieważ łazik wykonał pełne $k$ powtórzeń, następna instrukcja będzie pierwszą instrukcją z $W$, zatem jesteśmy w takiej samej sytuacji jak na samym początku. Łazik w każdym kolejnym ruchu będzie poruszał się po swoich śladach i nie odwiedzi już żadnego nowego pola.

Jeśli więc $W$ jest poprawnym ciągiem, który umożliwia odwiedzenie wszystkich $nm$ pól, a łazik wykonał $kw$ kroków, to musi być spełniona nierówność $kw \geq nm$. Po rozpisaniu dostajemy $\frac{nmw}{\mathrm{nwd}(n,m)} \geq nm$, czyli $w \geq \mathrm{nwd}(n,m)$.

Otrzymujemy więc, że $w \geq \max(2, \mathrm{nwd}(n, m))$. Spróbujemy uzyskać rozwiązanie o długości równej temu ograniczeniu dolnemu.

Konstrukcja dla $\mathrm{nwd}(n,m) \leq 2$

Zacznijmy od przypadku $\mathrm{nwd}(n,m) \leq 2$. Wtedy ograniczenie dolne to $w \geq 2$, a ponieważ $W$ musi zawierać jakiś ruch poziomy i pionowy, to rozważmy $W = \texttt{D}\texttt{P}$. Takim ciągiem instrukcji z pola (0,0) łazik przesuwa się na pole (1,1), więc po $k$ powtórzeniach znajdzie się na polu $(k \bmod n, k \bmod m)$.

W tej sytuacji $k=\mathrm{lcm}(n,m) = \frac{nm}{\mathrm{nwd}(n,m)}$ jest najmniejszą liczbą powtórzeń, po której wracamy na pole startowe. Zatem łazik każde powtórzenie ciągu $W$ będzie zaczynał na innym polu (w szczególności odwiedzi co najmniej $k$ różnych pól).

Jeśli zatem $\mathrm{nwd}(n,m)=1$, to mamy $k=nm$, czyli $W$ odwiedza wszystkie pola.

Dla $\mathrm{nwd}(n,m)=2$ podzielmy planszę na kwadraty rozmiaru $2\times 2$ i pomyślmy o planszy $n/2 \times m/2$ złożonej z $nm/4$ kwadratów. Kwadraty też możemy ponumerować, czyli mamy $n/2$ wierszy i $m/2$ kolumn.

Łazik, który zaczyna na polu (0,0) w kwadracie (0,0), po dwukrotnym wykonaniu $W$ przesuwa się na pole (2,2), czyli lewe-górne pole w kwadracie (1,1). Zatem po $2k$ powtórzeniach będzie na lewym-górnym polu w kwadracie $(k \bmod n/2, k \bmod m/2)$. Stosując rozumowanie jak powyżej, wróci na kwadrat (0,0) po $k=nm/4$ ruchach, odwiedzając lewe-górne pola wszystkich kwadratów.

Na poniższym rysunku jest przykład planszy $4\times 6$, dla której $g=2$ (kolorem wyróżniono lewe-górne pola wszystkich kwadratów):

Zauważmy, że łazik startując z lewego-górnego pola kwadratu $(r,c)$ i wykonując dwukrotnie $W$, odwiedzi lewe-dolne i prawe-dolne pole tego kwadratu, oraz prawe-górne pole kwadratu $((r+1) \bmod n/2, c)$. Zatem wszystkie pola oryginalnej planszy zostaną odwiedzone.

Konstrukcja prawie ogólna

Załóżmy zatem, że $\mathrm{nwd}(n,m) = g \geq 3$, więc ograniczenie dolne to $w \geq g$. Istotnie, ciąg $W=\texttt{D}\texttt{P}$ nie działa już dla planszy rozmiaru $3\times 3$.

Naturalnym pomysłem jest rozważenie ciągu, w którym wykonujemy kilka kroków w dół i kilka kroków w prawo. Załóżmy, że będziemy robić $a$ kroków w dół, więc $b = g-a$ kroków w prawo, a ciąg instrukcji to $W=\texttt{D}^{a}\texttt{P}^{b}$.

Teraz z pola (0,0) ciąg $W$ prowadzi łazika na pole $(a,b)$. Po $k$ powtórzeniach będzie to pole $(ka \bmod n, kb \bmod m)$. Jeśli więc $\mathrm{nwd}(a,n)=1$ oraz $\mathrm{nwd}(b,m)=1$ (nazwijmy to warunek pokrycia), to na pole początkowe wrócimy po $k=\mathrm{lcm}(n,m)=\frac{nm}{g}$ powtórzeniach.

Rozważmy przykład planszy $6\times 9$, dla której $g=3$, oraz $a=1$, $b=2$, które spełniają warunek pokrycia. Zobaczmy, że początkowe pola łazika układają się w przekątne:

Nie jest to przypadek, istotnie każde początkowe pole $(r,c)$ musi spełniać, że suma współrzędnych $r+c$ jest podzielna przez $g$. Dla dowodu zauważmy, że pole początkowe (0,0) to spełnia, a każde wykonanie ciągu $W$ też to zachowuje: z pola $(r,c)$ przechodzimy na $((r+a) \bmod n, (c+b) \bmod m)$. Mamy $(r+a) \bmod n = r+a+n'$, przy czym $n'=0$ (jeśli $r+a<n$) lub $n'=-n$ (gdy $r+a\geq n$). Analogicznie $(c+b) \bmod m = c+b+m'$, przy czym $m'=0$ lub $m'=-m$. Tak więc suma współrzędnych nowego pola początkowego wynosi \[((r+a) \bmod n) + ((c+b) \bmod m)) = r+a+n' + c+b+m' = (r+c) + (a+b) + n' + m' = (r+c) + g + n' + m'.\] Wszystkie składniki z ostatniej sumy są podzielne przez $g$, co daje tezę.

Z rysunku widać też, dlaczego, startując ciągiem $W$ z każdego pola początkowego, pokryjemy pozostałe pola planszy.

Rozwiązanie zatem polega na przejrzeniu kandydatów na $a$ ($1 \leq a \leq g-1$) i sprawdzeniu, który z nich spełnia warunek pokrycia, a następnie wypisanie odpowiedniego $W$. Mamy $O(n+m)$ kandydatów, a sprawdzenie warunku pokrycia algorytmem Euklidesa zajmie czas $O(\log(n+m))$.

Niestety, to rozwiązanie nie jest w pełni poprawne.

Wyjątki

Okazuje się, że istnieją rozmiary planszy $n \times m$, dla których nie istnieje żadna para $(a,b)$, która spełniałaby warunek pokrycia. Takich plansz jest jednak dość mało, gdyż z jednej strony $g = \mathrm{nwd}(n,m)$ musi być niewielkie (aby było mało kandydatów na $a$), a z drugiej strony zarówno $n$ jak i $m$ muszą mieć odpowiednio dużo czynników pierwszych (aby z każdym kandydatem któraś z liczb miała nietrywialne nwd).

W rozważanym zakresie $n,m \leq 10^6$ wszystkie takie plansze należą do dwóch grup:

Grupa 1 z planszą $n = 880 = 2^4 \cdot 5 \cdot 11$, $m = 4368 = 2^4 \cdot 3 \cdot 7 \cdot 13$; $\mathrm{nwd}(n,m) = 16$,
Grupa 2 z planszą $n = 13\,090 = 2 \cdot 5 \cdot 7 \cdot 11 \cdot 17$, $m = 16\,302 = 2 \cdot 3 \cdot 11 \cdot 13 \cdot 19$; $\mathrm{nwd}(n,m) = 22$.

Pozostałe plansze z każdej grupy $n,m$ mają rozmiary będące wielokrotnościami planszy $n\times m$ lub jej obrotu (czyli $m\times n$, $kn\times lm$, $km\times ln$ dla pewnych $l,m$ całkowitych dodatnich), przy czym musi być zachowane $\mathrm{nwd}(kn, lm) = \mathrm{nwd}(n,m)$.

Przekonanie się, że istnieją wyjątki, było możliwe przez napisanie programu, który dla wszystkich par $n,m \leq 10^4$ sprawdza wszystkich kandydatów. Szybszy program (który pozwolił wyznaczyć wszystkie wyjątki) wymagał osobnego rozpatrzenia małych i dużych wartości $\mathrm{nwd}(n,m)$.

Ponieważ wyjątków nie jest dużo, możemy dla każdego z nich spróbować wyznaczyć ciąg $W$, a następnie stablicować te odpowiedzi w kodzie źródłowym. Przykładowo, najmniejsza plansza z grupy 1 jest rozwiązywana przez ciąg DDDDDPGGPPPGLGPP, a najmniejsza z grupy 2 przez ciąg DDDDDDDDDDDDDDDDDPDLDP. Jak jednak znaleźć te ciągi?

Możemy to zrobić przeszukiwaniem z nawrotami, jeśli tylko będziemy mieli metodę sprawdzania, czy dany ciąg rzeczywiście jest poprawny.

Sprawdzanie poprawności ciągu

Mamy zatem zadanie: dla danej planszy $n\times m$ i ciągu długości $\mathrm{nwd}(n,m)$ sprawdzić, czy jest on poprawny. (Nawiasem mówiąc, jest to zadanie, które wykonuje program testujący poprawność rozwiązań zawodników.)

Przypomnijmy, że wykonanie ciągu $W$ przesuwa łazika z pola (0,0) na pole $(r,c)$ dla pewnych wartości $r,c$. Z naszych poprzednich rozważań wynika, że dla liczb $r,c$ musi być spełniony warunek pokrycia (żeby łazik wrócił na pole (0,0) dopiero po $k=\mathrm{lcm}(n,m)$ powtórzeniach).

Załóżmy zatem, że warunek pokrycia jest spełniony. Startując z pola (0,0) łazik odwiedzi $\mathrm{lcm}(n,m)$ pól. Startując z pola (0,1) łazik odwiedzi inny zbiór $\mathrm{lcm}(n,m)$ pól. W ogólności jest $\mathrm{nwd}(n,m)$ zbiorów rozmiaru $\mathrm{lcm}(n,m)$, które pokrywają planszę i mają taką własność, że łazik, startując z dowolnego pola zbioru, odwiedzi wszystkie pozostałe pola z tego zbioru.

Aby ciąg $W$ był poprawny, łazik w jednym powtórzeniu instrukcji z $W$ musi zatem odwiedzić wszystkie zbiory (czyli każde z $\mathrm{nwd}(n,m)$ odwiedzanych pól musi należeć do innego zbioru).

Na poniższym rysunku mamy planszę $16 \times 16$ i $(r,c) = (1,5)$, co spełnia warunek pokrycia. Zaznaczono też ciąg DDDDDPGGPPPGLGPP przechodzący przez wszystkie 16 zbiorów: