Autostrada

Zgodnie z tradycją, choć tym razem ze sporym opóźnieniem, proponuję omówienie jednego zadania z ostatniej edycji Wielkiej Przesmyckiej. Jest w nim odrobina geometrii, ale główna trudność ma charakter bardziej algorytmiczny niż implementacyjny, a zadanie jest dość konkretne nawet w wersji easy.

Dostajemy prostą postaci y=a\cdot x+b, na której chcemy otworzyć co najwyżej k punktów. Po ich wybraniu, każda z podanych na wejściu n wiosek podpina się do najbliższego otwartego punktu, przy czym odległość mierzymy w metryce taksówkarza (co od razu powinno wzbudzić Wasze podejrzenia!). Wioski mają różne wagi, i jeśli oznaczymy przez w_i oraz (x_i,y_i) wagę i współrzędne i-tej z nich, to taka wioska płaci w_i(|x-x_i|+|y-y_i|), gdzie (x,y) jest otwartym punktem na prostej (takim, dla którego taki koszt jest jak najmniejszy, czyli najbliższym). Teraz celem w całym zadaniu jest wybranie otwartych punktów tak, żeby zminimalizować sumę takich kosztów.

Oryginalną treść można znaleźć tutaj. Istotne, jak zwykle, są limity n,k\leq 100 w wersji basic i n\leq 1000, k\leq 10^9 w wersji professional. Więc, też jak zwykle, zacznijmy od wersji easy.

Naturalne wydaje się zastosowanie programowania dynamicznego. Chcemy „pokroić” zbiór wszystkich wiosek na podzbiory, które podpinają się do tego samego otwartego punktu. Jeśli wybierzemy już taki podział, jest dość łatwo. Wystarczy bowiem zauważyć, że interesuje nas wybranie x tak, aby zminimalizować:

\sum_i w_i(|x-x_i|+|a\cdot x+b-y_i|)=\sum_i w_i(|x-x_i|+a|x-\frac{y_i-b}{a}|)

co sprowadza się do wybrania mediany w multizbiorze (w którym umieszczamy w_i razy wszystkie x_i oraz \frac{y_i-b}{a}). Czyli niby fajnie, ale pojawia się dość fundamentalny kłopot. Chciałoby się powiedzieć, że można uporządkować wioski tak, że podzbiór tych, które podpinają się do tego samego otwartego punktu zawsze tworzy spójny przedział w tym porządku. Ale nijak nie widać jak taki porządek miałby wyglądać, w szczególności nie działa posortowanie po współrzędnej x czy y. Spróbujmy więc zupełnie inaczej.

Warto poczynić następującą obserwację: co prawda punktów na prostej y=a\cdot x+b jest sporo, ale tylko 2n z nich jest istotnymi kandydatami na te otwarte. Z powyższego rozumowania wynika bowiem, że wystarczy otwierać punkty postaci x=x_i oraz x=\frac{y_i-b}{a} (które łatwo wyobrazić sobie na rysunku). Czyli poprzedni akapit nie był taki całkiem bezużyteczny!

Mamy więc 2n punkty, z których chcemy wybrać co najwyżej k. Uporządkujmy je od lewej do prawej i nazwijmy (kolejno) P_1,P_2,\ldots,P_{2n}. Powiedzmy, że wybraliśmy już, które z punktów P_1,P_2,\ldots,P_i powinny zostać otwarte, podpięliśmy każdą wioskę do najlepszego z już otwartych punktów, no i zastanawiamy się co dalej. Okazuje się, że w tym momencie szczegóły wszystkich poprzednich wyborów nie są super istotne: ważna jest tylko liczba już otwartych punktów k' i numer ostatniego z nich P_j.

Lemat 1. Jeśli daną wioskę lepiej podpiąć do P_a niż do P_b, gdzie a<b, to lepiej podpiąć ją do P_a niż do dowolnego z P_{b},P_{b+2},\ldots,P_{2n}.

Dowód. Oznaczmy P_i=(x'_i,a\cdot x'_i+b) oraz ustalmy, że wioska znajduje się w punkcie (x,y) (jej waga tylko skaluje wynik, nie ma więc znaczenia). Koszt podpięcia wioski do P_i to |x-x'_i|+|y-(ax'_i+b)|=|x'_i-x|+a|x'_i+\frac{b-y}{a}|. Wyobraźmy sobie funkcję f(z)=|z-x|+a|z+b-y|. Nietrudno zauważyć, że wygląda ona jakoś tak:

autostrady

czyli jest wypukła (jak mówią niektórzy „szczęśliwa”, choć ja tego nie jestem pewien). Z definicji x'_1 < x'_2 < \ldots < x'_{2n}, czyli skoro lepiej podpiąć wioskę do P_a niż do P_b, gdzie a<b, to x'_b znajduje się już na tej wznoszącej części wykresu, więc dla kolejnych x'_{b+1},x'_{b+2},\ldots,x'_{2n} może być tylko gorzej. Tym akcentem kończymy dowód lematu.

Czyli jeśli zdecydujemy się otworzyć kolejny punkt P_{i+1}, to być może niektóre wioski podepną się teraz do P_{i+1} zamiast do P_j. Na pewno nie zdarzy się jednak tak, że jakaś wioska była wcześniej podpięta do jakiegoś P_{j'}, gdzie j'<j, a teraz powinna zostać podpięta do P_{i+1}. No i świetnie się składa, bo przecież nie mamy jak zapamiętać tych j'.

W zasadzie otrzymaliśmy już efektywne rozwiązanie wersji basic. Dla wszystkich i=1,2,\ldots,2n, k'=0,1,\ldots,k oraz j=1,2,\ldots,i wyznaczamy najmniejszy możliwy koszt po wybraniu k' z pierwszych i punktów tak, że ostatni wybrany punkt to P_j. Trzeba tylko efektywnie wyznaczyć "poprawkę" spowodowaną dodaniem punktu P_{i+1}, gdy ostatnio wybrany punkt to P_j. Można to jednak wyliczyć naiwnie przeglądając wszystkie wioski i sprawdzając dla każdego z nich, czy ma ona bliżej do P_{i+1} czy do P_j (i jeśli tak, odpowiednio zmniejszając sumaryczny koszt) w całkowitym czasie \mathcal{O}(n^3). Właściwa część rozwiązania jest mniej kosztowna i zajmuje tylko czas \mathcal{O}(n^2k).

Chciałoby się szybciej. Najsłabszym kawałkiem powyższego rozwiązania jest wyznaczanie wszystkich \mathcal{O}(n^2) poprawek w czasie \mathcal{O}(n^3). To może spróbujmy jakoś sprytniej? Poprawki dla ustalonej wioski mają dość regularną postać. Jeśli bowiem chcemy przepiąć ją z P_i do P_j, gdzie i<j, to taka poprawka jest albo zerowa, albo składa się z dwóch składników zależnych, odpowiednio, tylko od i i tylko od j. Z rysunku, którego użyliśmy w Lemacie 1, wynika, że dla każdego ustalonego i ta pierwsza część poprawki jest niezerowa i taka sama dla wszystkich j=i+1,i+2,\ldots,j_i, gdzie j_i jest pewnym granicznym indeksem. Analogicznie, dla każdego ustalonego j ta druga część poprawki jest niezerowa i taka sama dla wszystkich i=j-1,j-2,\ldots,j_i. Te wszystkie graniczne indeksy można wyznaczyć w sumarycznym czasie \mathcal{O}(n) (dla ustalonej wioski!) chodząc sobie dwoma palcami po wykresie. Potem, już dla wszystkich wiosek jednocześnie, można akumulować odpowiednie części poprawek przeglądając pary (i,j) w odpowiedniej kolejności. Szczegóły nie są fascynujące, poprzestańmy więc na konkluzji, że wszystkie poprawki można wyznaczyć w sumarycznym czasie \mathcal{O}(n^2), co zmniejsza całkowity czas działania do \mathcal{O}(nk^2).

Czyli dalej słabo, bo przecież w wersji professional n\leq 1000 i k\leq 10^9. To drugie może wydawać się szczególnie bolesne patrząć na powyższą złożoność, ale na szczęście tak wysokie ograniczenie górne na k jest zwykła ściemą: nigdy nie opłaca się przecież otwierać więcej niż n punktów na naszej proste. Jest jednak (a przynajmniej może być) także wskazówką, że finalny czas działania nie powinien zależeć zbyt mocno od wartości k.

Oznaczmy sobie przez T_k koszt rozwiązania całego problemu z danym parametrem k. Odpalając rozwiązanie wersji easy na niezbyt dużych losowych danych można zauważyć ciekawą własność:

Lemat 2. T_1-T_2 \geq T_2-T_3 \geq T_3-T_4 \geq \ldots \geq T_{n-1}-T_{n}.

Mówiąc bardziej obrazowo, dokładnie kolejnych otwartych punktów daje nam tym mniej im więcej takich punktów już użyliśmy. Taką własność nazywa się diminishing returns. W tym konkretnym przypadku jest ona być może w miarę intuicyjna, ale nie znam dowodu, który nie wymagałby nieco żmudnego rozważenia wielu przypadków (i wcześniejszego pokazania jednej lub dwóch dodatkowych własności), w drodze wyjątku poproszę więc Was o przyjęcie tego faktu na wiarę. Ciekawsze jest bowiem co dalej, to znaczy cóż da się wycisnąć z takiej własności?

Całkiem sporo, i jest to najprzyjemniejszą częścią całego zadania. Zacznijmy od zignorowania parametru k i znajdźmy optymalne rozwiązanie przy założeniu, że można otworzyć dowolnie wiele punktów. W takim optymalnym rozwiązaniu pewnie otwartych jest wiele punktów, może n, choć może trochę mniej. Jeśli tak czy inaczej jest ich co najwyżej k, to znalezione rozwiązanie jest także optymalnym rozwiązaniem bez ignorowania k (bo patrzymy w nim na mniej ograniczony problem). Ale co jeśli jest ich więcej?

Wtedy musimy jakoś „ukarać” się za otwarcie zbyt wielu punktów. Zanim się za to zabierzemy, pomyślmy jednak jak znaleźć optymalne rozwiązanie bez ograniczenia na liczbę otwartych punktów. Jest to łatwe: trzeba tylko wyznaczyć poprawkę dla każdej pary (i,j), gdzie i<j, a następnie myśleć o całej sytuacji jako o znalezieniu najkrótszej ścieżki w DAGu, w którym koszt krawędzi prowadzącej z i do j to właśnie ta poprawka. Czyli potrafimy znaleźć takie optymalne rozwiązanie w czasie \mathcal{O}(n^2). Wróćmy więc do kary za otwarcie zbyt wielu punktów. Naturalnym pomysłem jest zwiększenie wagi krawędzi (i,j) o t, gdzie t\geq 0 jest pewnym parametrem. Intuicyjnie, im większe t, tym mniej chętnie używamy wielu krawędzi. Bardziej formalnie, popatrzmy się na funkcję f(t), która dla danego t zwraca koszt najkrótszej ścieżki w odpowiednio zmodyfikowanym grafie. Łatwo zauważyc, że f(t)=\min_i i\cdot t+T_i, czyli f(t) jest dolną kopertą funkcji liniowych i\cdot t+T_i. I co?

autostrady1

I to, że z Lematu 2 wynika, że dla t\in (T_{i+1}-T_{i+2},T_{i}-T_{i+1}) funkcją, która wyznacza brzeg dolnej koperty jest (i+1)t+T_{i+1}. Czyli dla każdego i istnieje t, dla którego wyznaczenie najkrótszej ścieżki w odpowiednio zmodyfikowanym grafie da nam szukane rozwiązanie! Co więcej, na brzegu dolnej koperty pojawiają się kolejno funkcje

n\cdot t+T_n, (n-1)t+T_{n-1},\ldots, t+T_1.

Do znalezienia odpowiedniej (nie za dużej, nie za małej) wartości parametru t możemy więc użyć użyć wyszukiwania binarnego. Czyli: wybieramy jakieś t, znajdujemy najkrótszą ścieżkę w odpowiednio zmodyfikowanym grafie, w zależności od tego, czy składa się ona z więcej czy z mniej niż k krawędzi kontynuujemy wyszukiwanie na lewo lub na prawo. Jeśli trafiliśmy w dokładnie k krawędzi, kończmy zabawę. Prędzej lub później trafimy na ten ostatni przypadek, i można pokazać, że wymaga to \mathcal{O}(\log C) iteracji, gdzie C szukany koszt.

OK, trochę skłamałem. Jeśli T_1-T_2 > T_2-T_3 > \ldots > T_{n-1}-T_{n} rzeczywiście tak jest. Jeśli jednak pojawiają się równości, to nie do końca wiadomo. Można jednak powiedzieć, że gdy istnieje wiele najkrótszych ścieżek, szukamy takiej o najmniejszej liczbie krawędzi, i połatać opisane powyżej rozwiązanie. Szczegóły, jak zwykle, zostawiam Czytelnikowi.

W kolejnym odcinku: finały ACM ICPC 2015!

Advertisements

Jedna myśl nt. „Autostrada

Skomentuj

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

Logo WordPress.com

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

Zdjęcie z Twittera

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

Facebook photo

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

Google+ photo

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

Connecting to %s