Adriatyk

Tym razem popatrzymy na jeszcze ciepłe zadanie prosto ze słonecznej Chorwacji, kraju tysiąca wysp. A właściwie, jak przekonamy się już za chwilę, 250 tysięcy! Zadanie pochodzi z tegorocznej edycji Central European Olympiad in Informatics, która odbyła się w poprzednim tygodniu. Fajne w nim jest to, że (jak to często bywa na tego typu zawodach) ma kilka dość różnych rozwiązań o coraz lepszych czasach działania, i wcale nie jest tak, że najszybsze z nich jest jednocześnie najbardziej męczące w implementacji.

Treść (zadania Adriatic) można zobaczyć tutaj. Dostajemy n punktów o współrzędnych całkowitych z zakresu [1,2500]. Z punktu (x,y) można skoczyć do punktu (x',y') dokładnie wtedy, gdy x < x' i y < y' lub x > x' i y > y'. Definiuje to w naturalny sposób odległość d(A,B) między dwoma punktami A i B, która jest najmniejszą liczbą skoków potrzebnych do przedostania się z A do B (autor/autorzy gwarantują, że zawsze jest to możliwe). Naszym zadaniem jest wyznaczenie dla każdego punktu A sumy jego odległości do wszystkich pozostałych punktów, czyli \sum_{B\in P} d(A,B).

Warto już w tym momencie zwrócić uwagę na ograniczenia podane w treści. Są one dość zastanawiające, bo niby n\leq 250 000 (stąd wspomniane wcześniej 250 tysięcy wysp), lecz w części testów n jest istotnie mniejsze. Konkretniej, rozwiązanie działające dla n\leq 1500 może dostać 50% punktów, a poradzenie sobie z n\leq 25000 gwarantuje 80%. No, coś tam można dostać nawet za rozwiązanie wersji z n\leq 100, ale nie jest to chyba szczególnie ciekawe. O wiele bardziej intrygujące jest to, że ograniczenie współrzędnych do [1,2500] obowiązuje niezależnie od limitu na n, co od razu powinno wzbudzić naszą podejrzliwość. No, zresztą odrobina podejrzliwości jest zawsze na miejscu!

Wybierzmy punkt A=(x_A,y_A). Interesuje nas wyznaczenie najrótszych ścieżek z ustalonego źródła do wszystkich pozostałych wierzchołków w nieważonym grafie skierowanym. Pewnie można by więc skonstruować graf i przeszukać go wszerz w czasie \mathcal{O}(n^2). Takie rozwiązanie nie jest super szybkie, i w ewidentny sposób należy poszukać jakiegoś sposobu na wykorzystanie szczególnej struktury naszego grafu, ale warto najpierw wyobrazić sobie kolejne kroki przeszukiwania wszerz.

W pierwszym kroku odwiedzimy wszystkie punkty, które leżą (ściśle) w prawejgórnej i lewejdolnej ćwiartce, przyjmując (x_A,y_A) za środek układu współrzędnych. W kolejnych krokach będziemy odwiedzać punkty z pozostałych ćwiartek. Warto zauważyć, że jeśli skoczymy już do jednej z tych dwóch pozostałych ćwiartek, na pewno tam zostaniemy. Czemu? Powiedzmy, że jesteśmy w lewejgórnej ćwiartce. Wszystkie punkty, do których możemy skoczyć, leżą w lewejgórnej, lewejdolnej, i prawejgórnej ćwiartce. No ale przecież odwiedziliśmy już w pierwszym kroku wszystkie punkty z tych dwóch ostatnich, czyli kuszący jest dla nas tylko skok do punktu z tej samej ćwiartki. Tak naprawdę możemy więc zupełnie osobno wyznaczyć odległości do wszystkich punktów w lewejgórnej i prawejdolnej ćwiartce. Od tego momentu będziemy więc rozważali tylko te pierwsze (może warto już teraz zwrócić uwagę na to, że interesuje nas zarówno wnętrze tej ćwiartki, jak i jej brzeg).

Podsumujmy więc całą sytuację. W pierwszym kroku skaczemy do jakiegoś punktu z prawejgórnej lub lewejdolnej ćwiartki, a następnie kontynuujemy zabawę w lewejgórnej ćwiartce. Teraz wypada zauważyć, że ze wszystkich punktów w prawejgórnej ćwiartce interesuje nas tylko ten z największa współrzędną y, a ze wszystkich punktów w lewejdolnej ten z najmniejszą współrzędną x. Łatwo się o tym przekonać patrząc na poniższą ilustrację, na której lekko szare są ćwiartki, do których możemy dostać się w jednym kroku, a trochę bardziej szary jest fragment lewejgórnej ćwiartki, który możemy odwiedzić w dwóch krokach.

adriatyk1

Czyli jeszcze nieodwiedzona część interesującej nas ćwiartki to dokładnie \{(x,y): x \leq x_{\min} \wedge y \geq y_{\max} \}, gdzie x_{\min} jest najmniejszą współrzędną x wszystkich punktów w lewejdolnej ćwiartce, a y_{\max} największą współrzędną y wszystkich punktów w prawejgórnej ćwiartce. I fajnie, oznacza to bowiem, że łatwo wyobrazić sobie sytuację po dwóch pierwszych krokach. Ale co stanie się dalej?

Dalej będzie tak samo. No może nie tak samo, ale podobnie, to znaczy nieodwiedzony obszar będzie miał taką samą postać, przy czym wartość x_{\min} ulegnie (być może) zmniejszeniu, a y_{\max} (też być może) zwiększeniu. Konkretniej, trzeba uaktualnić x_{\min} i y_{\max} uwzględniając, odpowiednio, najmniejszą współrzędną x i największą współrzędną y wszystkich punktów odwiedzonych w drugim kroku. Pozostaje kwestia efektywnego dobrania się do punktów, które należy teraz odwiedzić.

Jeszcze raz podsumujmy sytuację. W poprzednich krokach odwiedziliśmy już wszystkie punkty \{(x,y)\in P: x > x_{\min} \vee y < y_{\max} \} z interesującej nas ćwiartki. Teraz chcielibyśmy raz-dwa wygenerować i odwiedzić wszystkie dotychczas nieodwiedzone punkty \{(x,y)\in P: x > x'_{\min} \vee y < y'_{\max} \}, gdzie x'_{\min} \leq x_{\min} i y'_{\max} \geq y_{\max}. Przejrzyjmy sobie (całkiem osobno) wszystkie punkty (x,y)\in P, dla których x\in [x'_{\min},x_{\min}), i (x,y)\in P, dla których y\in (y_{\max},y'_{\max}]. Niektóre z tych punktów być może należą do nieinteresującej nas w tym momencie ćwiartki, a co nawet gorsze (bo trudniejsze do wcześniejszego przewidzenia) niektóre być może zostały już odwiedzone. Nie przejmujmy się tym: po prostu przejdźmy przez wszystkie i wyciągnijmy tylko te, które warto teraz odwiedzić. Następnie uznajmy je za odwiedzone, zapiszmy ich odległość od punktu startowego, i przejdźmy do kolejnego kroku, uaktualniając x_{\min} i y_{\max}. Okazuje się, że właśnie uzyskaliśmy rozwiązanie o sumarycznym czasie działania \mathcal{O}(n^2)! Otóż przejrzenie punktów, których współrzędna x (lub y) należy do pewnego przedziału może być wykonane przez wcześniejsze posortowanie punktów względem współrzędnych x i (zupełnie osobno) y. Następnie po prostu przesuwamy się po odpowiedniej liście w lewo (w przypadku współrzędnych x) lub w prawo (w przypadku tych drugich) wyciągając punkty, których odpowiednia współrzędna należy do interesującego nas w danym kroku przedziale. Być może czasami wyciągniemy punkt, który należy do nieinteresującej nas ćwiartki. Być może jest też tak, że czasami wyciągniemy punkt, który został już odwiedzony. Ale patrząc na całą historię trochę bardziej globalnie, każdy z n punktów będzie wyciągnięty co najwyżej dwukrotnie, czyli czas przeszukiwania dla ustalonego punktu startowego jest tylko liniowy.

Świetnie, dostaliśmy 50% punktów. Ale chcielibyśmy dostać więcej, nie? Zastanówmy się może trochę staranniej nad opisaną wyżej metodą. W k-tym kroku:

  1. dodajemy do wyniku k razy liczba punktów odwiedzonych w tym kroku,
  2. uaktualniamy x_{\min} uwzględniając wszystkie nowo odwiedzone punkty,
  3. uaktualniamy y_{\max} uwzględniając wszystkie nowo odwiedzone punkty.

adriatyk2

Patrząc na powyższą ilustrację łatwo zauważyć, że poszczególne operacje można zaimplementować w następujący sposób:

  1. dodajemy do wyniku k razy liczba punktów w szarym obszarze,
  2. uaktualniamy x_{\min} uwzględniając wszystkie punkty (x,y), dla których y<y'_{\max},
  3. uaktualniamy y_{\max} uwzględniając wszystkie punkty (x,y), dla których x>x'_{\min}.

(Chwili zastanowienia wymaga być może to, że w 2. i 3. uwzględniamy nie tylko nowo odwiedzone punkty.) Przypomnijmy, że wszystkie współrzędne pochodzą z zakresu [1,2500]. Oznacza to, że możemy stablicować sobie wszystkie informacje, których potrzebujemy w 2. i 3., czyli pozostaje tylko poradzić sobie ze zliczaniem punktów. Stablicowanie wszystkich możliwych odpowiedzi raczej nie jest wykonalne, ale zauważmy, że wystarczy, że będziemy w stanie wyznaczyć C(x_0,y_0)=|\{(x,y)\in P: x\leq x_0 \wedge y\geq y_0\}| dla dowolnego (x_0,y_0)\in [1,2500]\times [1,2500]. Wtedy otrzymamy liczbę punktów w szarym obszarze odejmując od siebie dwie z wyznaczonych wcześniej liczb. Czyli znów możemy stablicować sobie wszystkie potrzebne informacje! A to oznacza, że po odpowiednim preprocessingu jesteśmy w stanie zasymulować pojedynczy krok w czasie stałym. Dlaczego jest to lepsze niż opisane wyżej rozwiązanie o kwadratowym czasie działania? Otóż w każdym kroku zmniejsza się aktualna wartość x_{\min} lub zwiększa y_{\max}, czyli wszystkich kroków nie może być więcej niż 5000. A to oznacza, że poradzimy sobie nawet z n=25000.

Mamy więc już 80% punktów. Ale fajnie byłoby dostać 100%, nie?

W opisanym wyżej rozwiązaniu aktualna sytuacja jest całkowicie opisana przez x_{\min}, y_{\max} i numer kroku k. Jest to o tyle smutne, że daje 2500^3 możliwości, czyli troszkę za dużo. Można jednak dołożyć jeden trik: przypomnijmy, że interesuje nas suma wszystkich odległości. Zamiast dodawać za każdym razem do wyniku k razy liczba nowych punktów, można myśleć, że zwiększamy ostateczną odpowiedź o liczbę punktów (x,y)\in P, dla których x\leq x_{\min}\wedge y\geq y_{\max} (czyli zarówno tych odwiedzonych w aktualnym kroku, jak i tych, które odwiedzimy w przyszłości). Odrobina wyobraźni pozwala na przekonanie się, że prowadzi to do takiego samego ostatecznego wyniku. Pozwala to na opisanie aktualnej sytuacji tylko przez x_{\min} i y_{\max}. Dla każdej takiej pary współrzędnych wyznaczamy, o ile należy zwiększyć odpowiedź, jeśli zaczniemy z danym x_{\min} i y_{\max}. Rozpatrując współrzędne w odpowiedniej kolejności, i wykonując wcześniej preprocesing, który pozwala na wyznaczenie dowolnego C(x_0,y_0) oraz uaktualnienie x_{\min} i y_{\max}, możemy skorzystać z prostego programowania dynamicznego i wyznaczyć każdą z szukanych liczb w czasie stałym. Skoro jest ich 2500^2, całe rozwiązanie z dużym zapasem mieści się w limicie dwóch sekund. Mieści się też w kilku linijkach kodu. No, dostatecznie długich linijkach.

Reklamy

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