Rezydencja

W tym (już całkiem wakacyjnym) odcinku proponuję zadanie o ninja zakradającym się do rezydencji. Co prawda ninja został świetnie wyszkolny, lecz rezydencja jest nie tylko świetnie strzeżona, ale i złożona z nieskończenie wielu pomieszczeń. Nie będzie łatwo.

Pomieszczeń jest co prawda nieskończenie wiele, ale wszystkie wyglądają dokładnie tak samo. Każde z nich ma kształt kwadratu, na którego bokach znajdują się drzwi pozwalające na przejście do sąsiednich pomieszczeń. Ninja może stawać tylko w n bezpiecznych punktach (wszystkie drzwi są takimi bezpiecznymi punktami) oraz przemieszczać się pomiędzy niektórymi z nich. Czyli tak naprawdę dostajemy nieskierowany graf, w którym krawędzie mają dodatnie wagi, a wierzchołki 1,2,3,4 odpowiadają drzwiom prowadzącym do sąsiednich pomieszczeń.

rezydencja

Ninja aktualnie stoi w podanym bezpiecznym punktcie w jednym z pomieszczeń. Jego celem jest jak najszybsze przedostanie się do (także podanego) bezpiecznego punktu w pomieszczeniu położonym X pomieszczeń na prawo i Y pomieszczeń w górę od tego początkowego (czyli przejście z pomieszczenia (0,0) do pomieszczenia (X,Y)). Na poniższej ilustracji widać przykład, w którym X=0 oraz Y=-2.

rezydencja1

Jak pewnie się domyślacie, naszym zadaniem jest wyliczenie takiej optymalnej trasy. Pewnie domyślacie się również, że zadanie pochodzi z japońskiej olimpiady informatycznej (oryginalną treść można znaleźć tutaj). Dostajemy tak naprawdę dwie wersje zadania: w prostszej (wartej 30% wszystkich punktów) możemy założyć, że |X|,|Y|\leq 3, a w tej trudniejszej wiemy tylko, że |X|,|Y|\leq 10^9. W obydwu wersjach podany graf składa się z co najwyżej 100000 wierzchołków oraz 200000 krawędzi.

Naszym zadaniem jest więc wyznaczenie najtańszej ścieżki łączej podane dwa wierzchołki w nieskończonym grafie utworzonym przez powielenie grafu podanego na wejściu. Nawet jeśli ograniczymy się do wersji, w której |X|,|Y|\leq 3, graf dalej jest nieskończony. Chociaż… czy na pewno?

Skoro wszystkie pomieszczenia wyglądają dokładnie tak samo, a początek i koniec całej wycieczki znajdują się w pomieszczeniach, które leżą niedaleko od siebie, to odwiedzanie pomieszczeń leżących w sporej odległości od tego początkowego i końcowego wydaje się raczej bez sensu. Ale jak ukonkretnić tę intuicję?

Lemat 1. Jeśli dwa bezpieczne punkty położone w pomieszczeniach (0,0) oraz (X,Y) (gdzie X,Y\geq 0) są połączone choć jedną ścieżką, to istnieje między nimi najtańsza ścieżka, która przechodzi tylko przez pomieszczenia (X',Y'), gdzie X' \in [-1, X+1] oraz Y' \in [-1,Y+1].

Dowód. Wyobraźmy sobie takie dwa bezpieczne punkty i łączącą je najtańszą ścieżkę. Jeśli istnieje więcej niż jedna najtańsza ścieżka, wybierzmy taką, która dodatkowo minimalizuje liczbę przejść między różnymi pomieszczeniami. Teraz załóżmy, że ta wybrana najtańsza ścieżka przechodzi przez jakieś pomieszczenie (X',Y'), dla którego X' \leq -2. Taką ścieżkę można podzielić na pięć części tak jak na poniższej ilustracji.

rezydencja2

Podział na części (oznaczone na rysunku jako A,B,C,D,E) jest wyznaczony przez przejścia między pomieszczeniami z X'=0 i X'=-1 oraz X=-1 i X=-2 (ponieważ założyliśmy, że odwiedzamy przynajmniej jedno pomieszczenie, dla którego X' \leq -2, jest to poprawna definicja). Teraz zauważmy, że ponieważ wszystkie pomieszczenie wygląda dokładnie tak samo, możemy poprzestawiać części otrzymując inną najtańszą ścieżkę.

rezydencja3

Ta nowa najtańsza ścieżka ma jednak mniejsza liczbę przejść między różnymi pomieszczeniami, a więc otrzymujemy sprzeczność z założeniem. Analogiczne rozumowanie można przeprowadzić zaczynając od założenia, że najtańsza ścieżka przechodzi przez pomieszczenie z Y' \leq -2, X' \geq X+2, lub Y' \geq Y+2.

Możemy już rozwiązać prostszą wersję zadania, w której |X|,|Y| \leq 3. Powyższy lemat pozwala nam na przycięcie grafu do co najwyżej 6 \times 6 pomieszczeń, na których uruchamiamy algorytm Dijkstry. Noo… albo i nie pozwala, bo otrzymany graf jest co prawda skończony, ale wciąż spory. W zależności od szczegółów implementacji może się zdarzyć, że nasz rozwiązanie będzie działać więcej niż kilka sekund.

Zauważmy jednak, że skoro każde pomieszczenie wygląda dokładnie tak samo i istotne są dla nas tylko bezpieczne punkty odpowiadające drzwiom oraz punktowi startowemu i końcowemu, tak naprawdę możemy zastąpić podany na wejściu graf przez jego skompresowaną wersję zawierający tylko te istotne punkty. Koszt krawędzi w nowym małym grafie to koszt najtańszej ścieżki w tym oryginalnym, który wyznaczamy odpalając algorytm Dijkstry (6 razy). Łatwo sprawdzić, że taka podmiana nie zmienia odpowiedzi i pozwala rozwiązać zadanie nawet w wersji, w której |X|,|Y| \leq 1000, ale to wciąż trochę słabo.

Spróbujmy najpierw uporać się z (pewnie prostszą wersją), w której jedna współrzędna (powiedzmy, że Y) jest dość mała. Bez straty ogólności możemy założyć, że X,Y\geq 0. Niech R oznacza koszt najtańszej ścieżki łączącej lewe drzwi z prawymi drzwiami w tym samym pomieszczeniu, a f(X,Y) koszt szukanej najkrótszej ścieżki, która zaczyna się w określonym bezpiecznym punkcie w pomieszczeniu (0,0), a kończy w określonym bezpiecznym punkcie w pomieszczeniu (X,Y).

Lemat 2. Jeśli X \geq 6 i Y\in [0,X-5] to f(X-1,Y)+R=f(X,Y).

Dowód. Łatwo zauważyć, że f(X,Y) \leq f(X-1,Y)+R, można bowiem „wkleić” ścieżkę odpowiadającą R w ścieżkę odpowiadającą f(X-1,Y). Pozostaje pokazać, że nie da się lepiej. W tym celu pokażemy, że zawsze możliwe jest takie pokrojenie na kawałki (i poprzestawianie tych kawałków) ścieżki odpowiadającej f(X,Y), że jeden z nich połączy lewe drzwi pewnego pomieszczenia z prawymi drzwiami tego samego pomieszczenia. Wymaga to odrobinę żmudnej analizy kilku przypadków.

Jeśli na naszej ścieżce (tej odpowiadającej f(X,Y)) już znajduje się kawałek łączący lewe drzwi z prawymi drzwiami tego samego pomieszczenia, nie musimy niczego kroić. Załóżmy więc, że tak nie jest. Teraz popatrzmy na wszystkie lewe/prawe drzwi, których używamy do przejście między pomieszczeniem (X',Y') do (X'+1,Y'), gdzie X' \in [1,X-2] (w obydwu kierunkach, to znaczy z (X',Y') do (X'+1,Y') jak i z (X'+1,Y') do (X',Y')). Mamy tylko 4 różne „lokalne” sytuacje (choć tak naprawdę każda z nich ma dwie wersje w zależności od kierunku w którym idziemy).

rezydencja4

Teraz po chwili zastanowienia i rozważeniu kilku przypadków dostajemy, że jeśli sytuacja I występuje przynajmniej dwukrotnie, możemy wyciąć i przestawić obok siebie odpowiadające jej kawałki, a następnie zauważyć, że albo umożliwi nam to polepszenie ścieżki (jeśli kawałki miały różne kierunki) lub spowoduje połączenie lewych drzwi z prawymi drzwiami tego samego pomieszczenia. Podobnie jeśli przynajmniej dwukrotnie występuje sytuacja III oraz jeśli dwukrotnie wystąpi zarówno sytuacja II jak i sytuacja IV (tutaj potrzebne jest dodatkowo założenie, że wśród najtańszych ścieżek wybieramy tę złożoną z jak najmniej krawędzi). Dostaliśmy więc, że sytuacje I i II występują co najwyżej raz. Z założenia, że X \geq 6 (czyli X \geq 4) wnioskujemy, że sytuacja II występuje co najwyżej raz, a sytuacja IV przynajmniej raz. Lub na odwrót. W każdym z tych dwóch przypadków możemy skorzystać z założenia, że Y\in [0,X-5] aby wywnioskować, że nasza ścieżka zawiera także kawałek łączący górne drzwi z dolnymi drzwiami tego samego pomieszczenia. Co więcej, analizując możliwe przypadki można pokazać, że zawsze można „skleić” taki kawałek z sytuacją II lub IV tak, aby otrzymać (odpowiednio) sytuację I lub III, czyli skrócić ścieżkę. Otrzymujemy więc sprzeczność.

Przepisując powyższy lemat aby pozbyć się R dostajemy, że jeśli X \geq 6 oraz Y \in [0,X-5] to

f(X,Y)-f(X-1,Y)=f(X+1,Y)-f(X,Y).

Pozwala to na wyliczenie f(X,Y) w czasie \mathcal{O}(1) o ile tylko, na przykład, Y \in [0,10] (a X jest dowolnie duże) korzystając ze stablicowanych wartości f(X,Y) dla X,Y\in [0,15] w następujący sposób: jeśli X\in [0,15] korzystamy ze stablicowanej wartości, a jeśli X \geq 16 zwracamy f(15,Y)+(f(15,Y)-f(14,Y))\cdot (X-15).

Ale co zrobić gdy zarówno X jak i Y są duże? W zasadzie to samo. Korzystając z podobnego rozumowania jak to w Lemacie 2 można pokazać, że wtedy

f(X,Y)-f(X-1,Y-1)=f(X+1,Y+1)-f(X,Y)

(darujmy sobie przecyzyjne określenie co znaczy „duże”). Pozwala to na wyznaczenie dowolnego f(X,Y) w dwóch krokach: najpierw jednocześnie „redukujemy” jednocześnie X i Y. Po takiej redukcji albo Y jest już małe (czyli możemy skorzystać z poprzedniego akapitu), albo X jest małe (czyli możemy skorzystać z metody analogicznej do tej z poprzedniego akapitu).

Reklamy

Jedna myśl nt. „Rezydencja

  1. Dowody na obrazkach są zawsze śliczne (w abstrakcyjnym sensie piękna), ale że chciało Ci się jeszcze zrobić śliczne (w estetycznym sensie) ilustracje, to podziwiam:)

    A mi wychodzi takie rozwiązanie (sorry, ale używam widoku w którym mamy ściany z oknami i stropy z włazami):

    Dostępne ruchy dzielimy na 4 kategorie: „w poziomie = od okna do okna”, „w pionie = od włazu do włazu”, „z okna do włazu” i „z włazu do okna”.
    Możemy myśleć, że ninja ma dwa stany: siedzi na parapecie, albo wisi we włazie.
    Dwa pierwsze typy ruchów są jakby „jokerami” – nie zmieniają stanu i można je wykorzystać w dowolnym miejscu ścieżki o ile ninja jest w odpowiednim stanie:) W szczególności możemy wszystkie ruchy tych typów zgrupować koło by były blisko siebie.
    Ruchy pozostałych dwóch typów nazywam „skośnymi” (no pun intended) i muszą występować na przemian (ewentualnie rozdzielone jokerami) powodując alternacje między stanami. To czy liczba tych aleternacji jest parzysta czy nie, jest zdeterminowane gdy tylko ninja podejmie jedną z 4×4 decyzji na temat początku i końca swojej misji.
    Ruchy skośne można zamieniać ze sobą miejscami o ile zachowamy odpowiedni typ.
    Teraz chciałbym przekonać do paru lematów:

    Lemat 1. Jeśli ruchów skośnych jest co najmniej 3, to wszystkie muszą mieć zgodny wektor (np. być „w prawo do góry”).
    D-d: Patrzymy na pierwsze 3 takie ruchy, które nie są zgodne (np. bez straty ogólności 2 z nich są „raczej w górę” a jeden „raczej w dół”). Skoro są 3, to zaczynają się i kończą w przeciwnych stanach, więc możemy wszystkie jokery przesunąć tak by były na lewo lub na prawo od tej trójki, tymsamym oczyszczając obraz sytuacji: mamy trzy skośne ruchy tuż obok siebie. Co więcej, wolno nam zamienić miejscami dwa skrajne stany i tymsamym doprowadzić do sytuacji, że pierwsze dwa są niezgodne ze sobą (np. pierwszy jest do góry, a drugi w dół).Teraz pozostaje przekonać, że (i tutaj ciężko bez rysunku i case inspection), że drugi lub trzeci ruch wraca z powrotem do tego samego pokoju, (lub jest tak po zamienieniu miejscami dwóch skrajnych ruchów). Jak wiemy zostawanie w tym samym pokoju przez dwa ruchy zabija ninję z powodu „zemsty zrelaksowanego Dijkstry”.

    Wniosek 1. Jeśli liczba alternacji jest nieparzysta, to wszystkie skośne ruchy są zgodne.
    D-d: Jest albo jeden albo co najmniej trzy takie ruchy.

    Lemat 2. Jeśli wśród ruchów jest chociaż jeden pionowy, to wszystkie ruchy pionowe i skośne muszą być zgodne z jego kierunkiem. Analogicznie jeśli istnieje chociaż jeden poziomy.
    D-d: Jako, że jokery można przesuwać, to można je sobie przesunąć tak by „zanihilowały” niepokorny ruch skośny czy pionowy przy pomocy zemsty Dijkstry.

    Wniosek 2. Jeśli start i cel leżą dokładnie na tej samej prostej (ścianie lub podłodze) (i nie są dokładnie tym samym punktem), to sekwencja ruchów _musi_ składać się z jednego zakrętu, długiego prostego sprintu, oraz zakrętu. Nasz wybór ogranicza się do tego, czy chcemy iść jedną czy drugą stroną tej prostej (tj. od jakiego zakrętu zacząć) reszta jest zdeterminowana.
    D-d: Liczba alternacji musi być parzysta. Zero alternacji nie wchodzi w grę bo musimy kiedyś zacząć iść w stronę celu. Zatem alternacji musi być co najmniej 2. Nie może ich być więcej niż 3, bo wszystkie musiałyby mieć zgodny kierunek co oznacza, że nigdy byśmy nie mogli wrócić do prostej na której leży cel – jokery nam nie pomogą, bo jeśli jest chociaż jeden taki joker, to jest zgodny z kierunkiem zakrętów. Zatem zakrętów muszą być dwa. Ewentualnie moglibyśmy się jeszcze trochę przespacerować w kierunku prostopadłym do prostej, ale to nie ma nieujemny koszt więc po co. Pozostaje nam sprint do celu.

    Wniosek 3. Jeśli start i cel mają tę samą jedną ze współrzędnych ale nie leżą na tej samej ścianie ani podłodze, to jedyną sensowną drogą jest sprint do celu używając jokerów.
    D-d: Liczba zakrętów musi być parzysta. Jeśli jest ich zero, super. Jeśli więcej niż 2, to muszą być zgodne ze sobą i jokerami i wtedy nie da się zniwelować ich wpływu na dryfowanie z ustalonego kursu. Jeśli są dokładnie dwa to też nie mogą być zgodne, bo by nie dało się wrócić na kurs inaczej jak niezgodnym z nimi jokerem. A zatem pozostaje przypadek że są dokładnie dwa i są niezgodne, ale wtedy możemy je przesunąć tuż obok siebie i zabić przy pomocy Dijkstry.

    Wniosek 4. Jeśli start i cel mają obie współrzędne różne, to wszystkie zakręty muszą być zgodne.
    D-d: Wiemy, że zakręty będą zgodne jeśli ich ilość to 0,1,3 lub więcej. Jeśli zakrętów byłoby dokładnie 2 i byłyby niezgodne (dajmy na to jeden „raczej w górę” a drugi „raczej w dół”) to skoro na wzajem znoszą swój wkład w ruch względem pewnej osi, to (niezerowy przecież) ruch na tej osi musi wynikać z wykorzystania jokerów. Ale jeśli jest choć jeden joker, to musi być zgodny z zakrętami, co rodzi sprzeczność.

    Proponowany Algorytm :
    0. sprawdź czy start i cel to ten sam punkt. Jeśli tak, zwróć 0
    1. sprawdź czy start i cel leżą na jednej ścianie lub podłodze. Jeśli tak, to sprawdź lepszą z dwóch opcji: iść jedną albo drugą stroną prostej wyznaczonej przez start i cel.
    2. sprawdź czy start i cel mają tę samą jedną ze współrzędnych. Jeśli tak, to wal prosto do celu
    3. w przeciwnym razie droga składa się z pewnej niezerowej liczby zgodnych zakrętów oraz ewentualnie pewnej liczby poziomych i pionowych jokerów. Parzystość liczby zakrętów jest zdeterminowana. Znając ich dokładną liczbę, możesz też jednoznacznie ustalić liczbę pionowych i poziomych jokerów. Pozostaje więc ustalić ile ma być tych zakrętów. Każda para zakrętów daje ten sam efekt co po jednym jokerze każdego typu. Pozostaje kwestia co się bardziej opłaca: dwa zakręty czy te dwa jokery. W zależności od tego, albo użyj jednego zakrętu i samych jokerów, albo na maksa dużo zakrętów i kilka jokerów tego typu którego trzeba więcej.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s