Zbiórka

Dla złapania oddechu po walce z palindromami proponuję niezbyt trudne (choć nieco podchwytliwe) zadanie z „udawanej” geometrii, które pojawiło się całkiem niedawno na zawodach ACM ICPC NWERC 2014. Udawanej, bo w 2D i z odległością taksówkarza, ale też całkiem fajne.

Treść (zadania G) jest tutaj. Dostajemy n punktów na płaszczyźnie oraz liczbę d. Teraz chcielibyśmy wybrać nowy punkt (x^*,y^*), który jest odległy o co najwyżej d od każdego z podanych, gdzie odległość między (x,y) a (x',y') to |x-x'|+|y-y'|, czyli tak zwana odległość taksówkarza. Takich punktów może być wiele, więc interesuje zminimalizowanie sumy odległości podanych punktów do (x^*,y^*). Skoro n \leq 10^5, pewnie celujemy w rozwiązanie o złożoności \mathcal{O}(n\log n).

Zacznijmy od standardowej sztuczki: obróćmy płaszczyznę o 45 stopni. Nietrudno zauważyć, że pozwala to na zastąpienie odległości taksówkarza odległością maksimum, którą definiujemy jako \max(|x-x'|,|y-y'|). Najprościej przekonać się o tym wyobrażając sobie okrąg w każdej z tych metryk (okrąg, czyli zbiór punktów w odległości d od danego (x,y)). W jednej jest to kopnięty kwadrat, a w drugiej po prostu kwadrat.

Po przejściu do odległości maksimum dostajemy, że szukany punkt (x^*,y^*) powinien spełniać \max(|x_i-x^*|,|y_i-y^*|)\leq d dla każdego z podanych punktów (x_i,y_i). Przekształcając i łącząc te warunki otrzymujemy więc, że x^*\in [x_{\min},x_{\max}] oraz y^*\in [y_{\min},y_{\max}] dla pewnych x_{\min},x_{\max},y_{\min},y_{\max}, które wyliczamy w czasie \mathcal{O}(n). W tym momencie być może mamy szczęście i, na przykład, x_{\min} > x_{\max}, co oznacza, że nie istnieje żadne rozwiązanie. Ale pewnie jednak mamy pecha i trzeba myśleć dalej.

Interesuje nas zminimalizowanie \sum_i \max(|x_i-x^*|,|y_i-y^*|) po wszystkich x^*\in [x_{\min},x_{\max}] oraz y^*\in [y_{\min},y_{\max}]. W tym momencie przejście do odległości maksimum nie wydaje się już takim świetnym pomysłem, wróćmy więc do metryki taksówkarza. Chcemy więc zminimalizować \sum_i |x_i-x^*|+|y_i-y^*| po wszystkich (x^*,y^*) należących do „kopniętego” prostokąta.

Zapomnijmy na chwilę o warunku nałożonym na (x^*,y^*). Wtedy minimalizacja \sum_i \max(|x_i-x^*|,|y_i-y^*|) jest równoważna niezależnemu wybraniu x^*, które minimalizuje \sum_i |x_i-x^*|, oraz y^*, które minimalizuje \sum_i |y_i-y^*|). To zaś oznacza, że najlepiej wybrać x^* i y^*, które są odpowiednio medianą wszystkich x_i oraz y_i (warto pamiętać, że mediana nie musi być jednoznacznie wyznaczona). Medianę umiemy wyliczyć w czasie \mathcal{O}(n), więc łatwo znaleźć takie najlepsze (x^*,y^*). Teraz być może mamy szczęście i znaleziony punkt należy do dozwolonego obszaru (to jest wspomnianego przed chwilą kopniętego prostokąta) i rozwiązaliśmy zadanie. Ale być może nie mamy.

Zauważmy, że jeśli dane (x^*,y^*) leży ściśle w środku dozwolonego obszaru, czyli nie na jego brzegu, to (x^*-1,y^*) oraz (x^*+1,y^*) także należą do dozwolonego obszaru. Jednocześnie albo przynajmniej jeden z tych dwóch lekko przesuniętych punktów ma mniejszą sumę odległości taksówkarza od wszystkich (x_i,y_i), albo (zakładając, że mediana wszystkich x_i jest jednoznacznie zdefiniowana), x^* jest dokładnie medianą wszystkich x_i. Podobnie, (x^*,y^*-1) oraz (x^*,y^*+1) także należą do dozwolonego obszaru, oraz albo jeden z tych dwóch punktów ma mniejszą sumę odległości taksówkarza, albo (zakładając, że mediana wszystkich y_i jest jednoznacznie zdefiniowana), y^* jest dokładnie medianą wszystkich y_i. Jaki z tego wniosek? Albo wyznaczone w paragrafie wyżej (x^*,y^*) leży w środku wyznaczonego obszaru i zakończyliśmy już całą zabawę, albo wystarczy rozważać takie (x^*,y*), które leżą dokładnie na brzegu. (To rozumowanie nie jest jeszcze w 100% poprawne, bowiem, jak zauważyliśmy przed chwilą, mediana nie zawsze jest zdefiniowana. Ale możne je uogólnić.) Każdy z tych brzegów leży na prostej postaci y=x+b lub y=-x+b, wystarczy więc osobno sprawdzić 4 przypadki odpowiadającej sytuacji, w której (x^*,y^*) leży na konkretnym boku.

Udało nam się zredukować cały problem do wyznaczenia (x^*,y^*), które minimalizuje \sum_i |x_i-x^*|+|y_i-y^*| pod warunkiem, że y^*=ax^*+b, gdzie a\in\{-1,1\}, oraz |x_i-x^*|+|y_i-y^*|\leq d dla każdego i. Jest to tak naprawdę problem w 1D, wystarczy bowiem podstawić y^*=ax^*+b otrzymując, że |x^*-x_i|+|x^*-\frac{y_i-b}{a}|\leq d dla każdego i, oraz chcemy minimalizować \sum_i |x^*-x_i|+|x^*-\frac{y_i-b}{a}|. Wyobraźmy więc sobie, jak wygląda wykres funkcji f(x)=|x-x_1|-|x-x_2|.

zbiorka1

Widać, że warunek |x^*-x_i|+|x^*-\frac{y_i-b}{a}|\leq d oznacza tylko tyle, że x^*\in [x_{\min},x_{\max}] dla pewnych (łatwych do wyliczenia) x_{\min} i x_{\max}. Ale uwaga! x_{\min} i x_{\max} niekoniecznie są całkowite. Przecinając wszystkie warunki takiej postaci dostajemy, że interesuje nas zminimalizowanie \sum_i f_i(x^*) po wszystkich x^*\in [x_{\min},x_{\max}] (te nowe x_{\min} i x_{\max} to prostu, odpowiednio, maksimum i minimum z x_{\min} i x_{\max} wyznaczonych dla kolejnych i), gdzie f_i(x)=|x-x_i|+|x-x'_i|. Jak się za to zabrać?

Wyobraźmy sobie, że rozważamy coraz większe x^*. Każda funkcja f_i najpierw maleje, potem przez chwilę jest stała, a potem rośnie. W każdym momencie f_i jest więc funkcją liniową ax+b. Funkcja liniowa odpowiadająca danemu f_i zmienia się po raz pierwszy, gdy x^*=x_i, i po raz drugi, gdy x^*=x'_i. A więc możemy pokroić cały przedział [x_{\min},x_{\max}] na co najwyżej 3n kawałki o takiej własności, że na całym kawałku każda funkcja f_i jest funkcją liniową. Następnie, zamiast rozważać wszystkie możliwe x^*, możemy rozważać jednocześnie wszystkie x^* należące do jednego takiego kawałka. Wtedy naszym celem jest minimalizacja sumy funkcji liniowych, co przecież jest proste, bo suma funkcji liniowych jest znów funkcją liniową (a takie pewnie umiemy minimalizować na danym zakresie). Pozostaje tylko upewnić się, że potrafimy szybko skonstruować te wszystkie funkcje liniowe, które reprezentują naszą funkcję celu na kolejnych kawałkach. Nie jest to jednak trudne, możemy bowiem skanować kolejne „istotne” x^*, to znaczy równe pewnemu x_i lub x'_i, utrzymując f(x)=\sum_i a_i x +b (czyli, tak naprawdę, pamiętając \sum_i a_i oraz \sum_i b). Gdy któraś funkcja f_i(x) ulega zmianie, wystarczy odjąć ją od sumy, a następnie (już po zmianie) dodać. Trzeba tylko wcześniej posortować wszystkie x_i oraz x'_i, a następnie przejrzeć od lewej do prawej w czasie \mathcal{O}(1) na każdy, co daje nam sumaryczną złożoność \mathcal{O}(n\log n).

Tyle w kwestii zadania. Trik z obróceniem płaszczyzny o 45 pewnie nie był nam tak naprawdę potrzebny (zresztą w sumie się z niego wycofaliśmy), ale warto go znać. Co ciekawe, działa on nie tylko w 2D, co polecam jako ćwiczenie.

Advertisements

2 myśli nt. „Zbiórka

  1. „Co ciekawe, działa on nie tylko w 2D, co polecam jako ćwiczenie.” ???
    W 3D kula w metryce miejskiej to ośmiościan, w w metryce maksimum to sześcian, zatem te 2 metryki z pewnością nie są równoważne w 3D. W wyższych wymiarach też nie będzie działać, a 1D chyba za ciekawe nie jest :P. Czy chodziło może o coś innego?

    • Faktycznie mogłem napisać precyzyjniej. W 3D można przekształcić (x,y,z) -> (x+y+z,x+y-z,x-y+z,x-y-z) i wtedy chyba działa 🙂 więc jest wykładnicze puchnięcie wymiaru, ale można powiedzieć, że działa w zasadzie ta sama sztuczka.

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