Gra planszowa

Urodziny kojarzą się zwykle z prezentami, a prezenty (i ich owijanie) z otoczką wypukła. Wiadomo. W związku z tym dzisiaj proponuję zadanie o najbardziej odległych różnokolorowych punktach, które pojawiło się kilka dni temu na Akademickich Mistrzostwach Polski w Programowaniu Zespołowym.

Rozważamy n \leq 250 000 punktów na płaszczyźnie. Każdy z tych punktów ma przypisany pewien kolor, przy czym na pewno nie jest tak, że wszystkie punkty są tego samego koloru. Interesuje nas wyznaczenie największej możliwej odległości (euklidesowej) między dowolną parą różnokolorowych punktów. Pełną treść (zadania G) można zobaczyć tutaj.

Na pierwszy rzut oka zadanie wygląda całkiem standardowo. W końcu prawie każdy z Was rozwiązywał już kiedyś wersję, w którym jesteśmy proszeni o wyznaczenie największej możliwej odległości między dowolnymi dwoma z podanych n punktów (bez kolorów). Może wystarczy więc lekko zmodyfikować rozwiązanie tej standardowej wersji? Może. Najpierw wypadałoby je sobie przypomnieć.

Aby uprościć sytuację zauważamy, że wystarczy rozważać te z podanych punktów, które są wierzchołkami otoczki wypukłej całego zbioru. Załóżmy bowiem, że para najbardziej odległych punktów to p_i oraz p_j, gdzie p_j znajduje się ściśle wewnątrz otoczki. Wtedy możemy przedłużyć odcinek \overline{p_i p_j} tak, żeby dotknął brzegu otoczki. To oczywiście nie może zmniejszyć długości. Następnie lekko obracamy otrzymany odcinek wokół p_i w odpowiednim kierunku (to jest zgodnie lub przeciwnie do ruchu wskazówek zegara) tak, aby jeszcze bardziej zwiększyć jego długość. Łatwo zauważyć, że jest to możliwe tak długo, jak jego drugi koniec nie jest jednym z wierzchołków otoczki. Cały proces ilustruje poniższy obrazek.

gra1

Czyli jeśli p_i oraz p_j to faktycznie para najbardziej odległych punktów, to p_j jest jednym z wierzchołków otoczki. Symetryczne rozumowanie daje nam, że także p_i jest takim wierzchołkim, więc faktycznie możemy z czystym sumieniem zapomnieć o pozostałych punktach.

Od tego momentu możemy więc założyć, że pracujemy z wielokątem wypukłym, którego wierzchołki nazwiemy p_1,p_2,  \ldots,p_n. Wyobraźmy sobie teraz, że ustawiamy taki wielokąt na stole i zaczynamy toczyć (powiedzmy, że w prawo). Podczas całego procesu rejestrujemy największą wysokość wierzchołka (nad poziomem stołu) tak jak na poniższym rysunku.

gra2

Teraz twierdzimy, że ta największa zarejestrowana wysokość to dokładnie największa możliwa odległość między parą wierzchołków otoczki. Jest w miarę jasne, że dla każdej zarejestrowanej wysokości możemy wskazać parę wierzchołków o przynajmniej tak dużej odległości. Z drugiej strony, wyobraźmy sobie parę najbardziej odległych wierzchołków p_i oraz p_j. Skoro jest to najbardziej odległa para wierzchołków, to zmiana i lub j o jeden nie może polepszyć wyniku. Z tego zaś wynika, że po obróceniu wielokąta tak, że odcinek \overline{p_i p_j} stanie się odcinkiem pionowym cały wielokąt oprze się na wierzchołku p_i, a p_j stanie się wierzchołkiem o największej wysokości.

Drobną niedogodnością jest jednak to, że nie do końca możemy sobie pozwolić na naiwne symulowanie całego procesu. W końcu możliwych obrotów jest dość sporo. Można jednak zauważyć, że takich ciekawych nie ma wcale tak dużo. Wystarczy przecież rozważać tylko te momenty, w których zmienia się wierzchołek podparcia lub wierzchołek o największej wysokości. To z kolei następuje wtedy gdy jeden z boków naszego wielokąta staje się odcinkiem poziomym. Po chwili zastanowienia można zauważyć, że tak naprawdę wystarczy rozważać sytuacje, w których wielokąt leży na jednym z boków. To prowadzi do dość prostej procedury, w której jednym palcem śledzimy aktualny bok, na którym leży wielokąt, a drugi trzymamy na wierzchołku o największej wysokości. Po przesunięciu pierwszego palca na kolejny (w kolejności ruchu wskazówek zegara) bok drugi palec albo zostaje w miejscu albo także przesuwa się zgodnie z ruchem wskazówek zegara. Po wyznaczeniu otoczki cały proces działa w czasie liniowym (od rozmiaru otoczki).

Może warto wspomnieć w tym momencie o innym (może nawet bardziej naturalnym) podejściu. Można bowiem próbować rozważać kolejne wierzchołki p_i i dla każdego z nich wyszukiwać binarnie najbardziej odległy p_j. Niestety, takie podejście nie daje nam żadnych szans na sukces. Nietrudno bowiem skonstruować przykład, w którym te odległości oscylują w dowolnie skomplikowany sposób (czyli nie jest tak, że najpierw rosną a potem maleją).

gra3

Świetnie, ale jak rozwiązać wersję, w której interesuje nas para różnokolorowych punktów? Pewnie warto zacząć od rozważenia wersji, w której mamy tylko dwa możliwe kolory. Dla ustalenia uwagi nazwijmy je niebieskim i zielonym. Dość łatwo zauważyć, że w zasadzie taki sam argument daje nam, że wystarczy rozważać tylko niebieskie punkty leżące na otoczce wszystkich niebieskich punktów oraz tylko zielone punkty leżące na otoczce wszystkich zielonych punktów (znów możemy bowiem przedłużyć i lekko obrócić odcinek odpowiadający parze najbardziej odległych punktów polepszając wynik, chyba że obydwa końce są już wierzchołkami odpowiednich otoczek). Tak naprawdę pracujemy więc z dwoma wielokątami wypukłymi. Teraz można powtórzyć całe rozumowanie z obracaniem wielokąta (tym razem: dwóch wielokątów) i utrzymywaniem najwyższego wierzchołka, jest jednak troszkę trudniej. Wyobraźmy sobie, że jednocześnie obracamy obydwa wielokąty utrzymując niebieski wierzchołek o najmniejszej współrzędnej y i zielony wierzchołek o największej współrzędnej y. Dalej jest prawdą, że interesują nas tylko momenty, w których jeden z tych wierzchołków ulega zmianie. Jeśli jednak chcielibyśmy ograniczyć się tylko do chwil, w których jeden z niebieskich boków staje się odcinkiem poziomym, to pewnie trzeba by później rozważyć także chwile, w których jeden z zielonych boków staje się takim odcinkiem. Czyli teraz musimy najpierw przejść po kolejnych bokach jednego wielokata utrzymując wierzchołek tego drugiego, a potem powtórzyć procedurę zamieniając ze sobą wielokąty. Pozwala nam to na znalezienie dwóch najbardziej odległych różnokolorowych punktów w czasie liniowym od rozmiarów obydwu otoczek (pomijając czas potrzebny na znalezienie otoczek).

Fajnie, ale przecież nie możemy ograniczać się do dwóch kolorów. Nie jest to jednak wielki problem. Powiedzmy bowiem, że kolorów jest więcej. Podzielmy je na dwie mniej więcej równoliczne grupki i nazwijmy je, odpowiednio, odcieniami niebieskiego i odcieniami zielonego. Mamy trzy możliwości w kwestii szukanej pary punktów: być może jeden jest odcieniem niebieskiego a drugi odcieniem zielonego, być może obydwa są odcieniami niebieskiego, a być może obydwa są odcieniami zielonego. Tę pierwszą możliwość możemy sprawdzić utożsamiając ze sobą wszystkie odcienie (to znaczy myśląc o wszystkich odcieniach niebieskiego jako o niebieskim i odpowiednio o wszystkich odcieniach zielonego jako o zielonym) i używając wyżej opisanej procedury. Tę drugą i trzecią możemy zaś uwzględnić uruchamiając się rekurencyjnie na wszystkich punktach, których kolory są odcieniami niebieskiego, i (osobno) tych, których kolory są odcieniami zielonego. Poprawność takiego rozwiązania jest w miarę oczywista, ale czy jest ono dostatecznie szybkie?

Nasze rozwiązanie dla dwóch kolorów działa w czasie \mathcal{O}(n\log n) o ile uwzględnimy także koszt znalezienia otoczki. Ponieważ dzielimy kolory na dwie mniej więcej równoliczne grupki, można myśleć, że całkowity czas działania jest opisany rekurencją T(n)=\mathcal{O}(n\log n)+2T(n/2), którego rozwiązaniem jest \mathcal{O}(n\log^2 n). Nie jest to co prawda do końca prawda (podział nie musi być przecież dokładnie na dwa zbiory punktów o równych licznościach), ale nietrudno pokazać, że taka intuicja nie odbiega (asymptotycznie) od prawdy. Jeśli bowiem popatrzymy na punkty danego koloru, uczestniczą one w \mathcal{O}(\log n) instancjach prostszego problemu, w którym mamy tylko dwa kolory. Taka złożoność w zupełności wystarczała do rozwiązania zadanie, ale może da się lepiej?

Pewnie tak, i to nawet nietrudno. Tak naprawdę jedynym powodem, dla którego czas działania to \mathcal{O}(n\log^2 n) a nie \mathcal{O}(n\log n) jest konieczność wyznaczania otoczek. To z kolei wymaga posortowania punktów, a następnie liniowego przejrzenia ich, na przykład, od lewej do prawej. Teraz wydaje się, że będziemy wielokrotnie sortować te same punkty, co pewnie nie jest najlepszym możliwym pomysłem. Lepiej obiecać, że każde wywołanie rekurencyjne zwróci posortowaną listę punktów, które mu przekazaliśmy. Wtedy możemy najpierw wykonać obydwa wywołania rekurencyjne, wyliczyć obydwie otoczki w czasie liniowym, przejść po nich dwoma palcami także w czasie liniowym, i wreszcie (znów w czasie liniowym) skleić dwie posortowane listy w jedną. Daje to rozwiązanie o złożoności \mathcal{O}(n\log n), które jednak nie działa istotnie szybciej od tego poprzedniego.

Na koniec proponuję zastanowienie się nad następującym zadaniem: jak szybko można znaleźć parę najbliższych różnokolorowych punktów?

Advertisements

4 myśli nt. „Gra planszowa

  1. Bardzo ładne zadanie!

    A drużyna Uniwersytetu Jagiellońskiego znalazła ciekawy wariant rozwiązania:
    Dla i = 0, 1, …, log n -1 dzielimy kolory na te, które mają i-ty bit zapalony i te, które mają i-ty bit zgaszony. To z kolei dzieli punkty na dwie grupy, dla których liczymy obie otoczki (w czasie liniowym, bo mamy listę punktów wstępnie posortowaną) i szukamy najdalszych punktów.

    Ponieważ najdalsza różnokolorowa para punktów musi się różnić na którymś bicie, na pewno ją znajdziemy, w czasie O(n log n).

  2. „Dokładniej, wystarczy rozważyć te momenty, w których przynajmniej jeden z boków naszego wielokąta staje się odcinkiem poziomym.” Tu chyba dałoby radę trochę pomóc czytelnikowi zrozumieć jak to dokładnie ma działać. Przykładowo jeśli wielokątem jest kwadrat, to najciekawsze są te momenty gdy wszystkie boki tworzą kąty +-45* z podłożem.

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