Podatki

Większość z Was pewnie wie, że właśnie trwają Potyczki Algorytmiczne 2013 (które polecam, choć to pewnie oczywiste). Ja co prawda darowałem sobie udział, ale nie uniknąłem popatrzenia na kilka ciekawszych zadań. Jedno z nich wydało mi się o tyle intrygujące, że tak naprawdę jest pytaniem z geometrii, choć geometria ta jest dość podstępnie ukryta w zdawałoby się niewinnej treści dotyczącej prostokątów. Tych z Was, którzy chcieliby się dowiedzieć więcej, zapraszam do dalszej lektury: pojawią się drzewa, wektory, płaszczyzny dualne, sumy Minkowskiego, i… i będzie dość wesoło. Jak to zwykle w geometrii.

Zacznijmy od treści. Po wycięciu wszystkich Bajtazarów, Bajtalarów, itd. itp. dostajemy następujące pytanie: mając dane cztery ciągi a_1,a_2,\ldots,a_n, b_1,b_2,\ldots,b_n, a'_1,a'_2,\ldots,a'_n, b'_1,b'_2,\ldots,b'_n, znajdź i < j oraz i' < j', dla których wartość

(a_i+a_{i+1}+...+a_j)(b'_{i'}+b'_{i'+1}+...+b'_{j'})+(b_i+b_{i+1}+...+b_j)(a'_{i'}+a'_{i'+1}+...+a'_{j'})

jest największa.

OK, nie wygląda to szczególnie zachęcająco, a w zasadzie wygląda dość obrzydliwie. Na szczęście można zapisać wyrażenie, które chcemy maksymalizować, w trochę bardziej cywilizowany sposób. Zdefiniujmy sobie sumy częściowe wszystkich czterech ciągów:

\begin{array}{rcl}  x_i &=& a_1+a_2+\ldots+a_i, \\  y_i &=& b_1+b_2+\ldots+b_i,\\  y'_i &=& a'_1+a'_2+\ldots+a'_i,\\  x'_i &=& b'_1+b'_2+\ldots+b'_i  \end{array}

(w szczególności, x_0=y_0=x'_0=y'_0=0). Teraz widać, że tak naprawdę chcemy maksymalizować

(x_j - x_i)(y'_{j'}-y'_{i'}) + (y_j - y_i)(x'_{j'}-x'_{i'})

po wszystkich i < j oraz i' < j'. Trochę lepiej, ale jeszcze nie fantastycznie.

Pójdźmy więc krok dalej, i zdefiniujmy sobie wektory u_i = [x_i,y_i] oraz v_i=[y'_i,x'_i]. Dostajemy, że należy zmaksymalizować (u_j-u_i) \cdot (v_{j'}-v_{i'}), gdzie kropka oznacza znany i lubiany iloczyn skalarny. To nie wygląda już tak okropnie, prawda?

No dobrze, to może zakończmy rozważania natury estetycznej i zabierzmy się za rozwiązywanie. Wszystkich możliwych wyborów i,j,i',j' jest strasznie dużo, tym niemniej warto zacząć od napisania sobie rozwiązania brutalnego, które działa w czasie \mathcal{O}(n^4). Pisząc takie rozwiązanie warto zwrócić uwagę na to, że wybór i < j jest zupełnie niezależny od wyboru i' < j', dość naturalne jest więc osobne wygenerowanie wszystkich u_j - u_i oraz wszystkich v_{j'}-v_{i'}, a następnie wyszukanie kombinacji, która maksymalizuje iloczyn skalarny. Stąd już tylko jeden krok do następującej obserwacji: wyobraźmy sobie wszystkie różnice u_j-u_i jako punkty na płaszczyźnie. Czy wszystkie z nich są sensownymi kandydatami na optymalne rozwiązanie?

Pewnie, że nie! Jeśli mamy na przykład punkty (2,1), (4,2) i (8,4), można śmiało usunąć ten drugi. Ba, można dokonać nawet bardziej odważnej operacji.

Lemat. Żaden z punktów, które nie są wierzchołkami otoczki wypukłej, nie jest sensownym kandydatem na optymalne rozwiązanie.

Dowód. Zacznijmy od obserwacji pomocniczej: jeśli mamy dwa punkty (x_0,y_0) i (x_1,y_1) oraz trzeci punkt, który leży na łączącym je odcinku, czyli jest postaci (x,y)=\alpha (x_0,y_0)+(1-\alpha)(x_1,y_1), to jeśli (x_0,y_0) i (x_1,y_1) są rozpatrywane jako kandydaci na rozwiązanie, nie warto rozpatrywać także (x,y). Dlaczego? Nasz zysk to nic innego niż (x,y) \cdot v dla pewnego v, czyli \alpha (x_0,y_0) \cdot v + (1-\alpha) (x_1,y_1) \cdot v. Stąd dostajemy, że wybierając \alpha=0 lub \alpha=1 na pewno nie pogorszymy sumarycznego kosztu, a może nawet uda nam się go polepszyć.

Mając obserwację pomocniczą jest już łatwo. Weźmy sobie bowiem jakiś punkt, który leży w środku otoczki. Wtedy można przedstawić go jako kombinację liniową dwóch punktów należących do jej brzegu, no i z obserwacji jeden z nich jest przynajmniej tak samo dobry. Następnie przedstawiamy punkt, który leży na brzegu otoczki, jako kombinację liniową dwóch jej wierzchołków, i znów z obserwacji jeden z nich jest przynajmniej tak samo fajny.

Dostajemy więc pierwszy pomysł na optymalizację: zbiór wszystkich wygenerowanych różnic można przyciąć wyznaczając otoczkę wypukłą odpowiadających im punktów. Niestety nie widać jeszcze, żeby miało to dawać istotny zysk, a poza tym tych różnic jest przecież kwadratowo wiele. Ale skoro wiemy już, że tak naprawdę interesuje nas tylko otoczka wypukła, może dałoby się ją wygenerować jakoś sprytniej niż wyznaczając wszystkie różnice?

Okazuje się, że dałoby się, i to w jakim stylu! Zastosujemy strategię dziel-i-zwyciężaj. Wygenerowanie wszystkich różnic u_j - u_i dla 1\leq i < j \leq n można sprowadzić do wygenerowania wszystkich różnic dla 1\leq i < j \leq m, wszystkich różnic dla m+1 \leq i < j \leq n, oraz wszystkich różnic dla i\in [1,m], j\in [m+1,n], gdzie m jest dowolnie wybranym indeksem. Dlaczego jest to fajne? Dlatego, że o ile tylko umiemy sprawnie wygenerować otoczkę wypukłą punktów odpowiadających wszystkim różnicom dla i\in [1,m], j\in [m+1,n], będziemy w stanie (dość efektywnie) wygenerować całą otoczkę: wystarczy tylko za każdym razem wybierać m, które leży mniej więcej w połowie drogi między i a j. Ale czy rzeczywiście umiemy? Przecież nie wydaje się to jakoś istotnie różnić od oryginalnego problemu.

Ale jednak się różni, i to znacznie. Wybór i jest bowiem w pełni niezależny od wyboru j, co okazuje się dość istotnie upraszczać całą sytuację.

Lemat. Mając dane dwa zbiory \{p_1,p_2,\ldots,p_k\} oraz \{q_1,q_2,\ldots,q_k\}, w czasie \mathcal{O}(k\log k) można skonstruować otoczkę wypukłą wszystkich punktów postaci p_j-q_i.

Dowód. Zdefiniujmy X jako otoczkę wypukłą zbioru \{p_1,p_2,\ldots,p_k\} i Y jako otoczkę wypukłą zbioru \{q_1,q_2,\ldots,q_k\}. Następnie popatrzmy na zbiór Z=\{x+y : x\in X, y\in Y\}. Jest to tak zwana suma Minkowskiego wielokątów X i Y, i dość łatwo uwierzyć, że jeśli wielokąty te są wypukłe, to samo można powiedzieć o Z. Dość prosty (można by wręcz powiedzieć, że niebezpiecznie ocierający się o bycie trywialnym) przykład takiej sumy można zobaczyć na poniższej ilustracji.

podatki-sum

Co więcej, można udowodnić, że Z ma nie więcej niż 2k wierzchołków, no i wyznaczyć je w czasie \mathcal{O}(k), o ile tylko mamy dostęp do wierzchołków X i Y posortowanych zgodnie z ruchem wskazówek zegara. Lub, jeśli ktoś woli, przeciwnie. Jak? Otóż okazuje się, że każda z krawędzi dowolnego z dwóch wielokątów jest także krawędzią sumy. Pozostaje tylko ustalić, w jakiej kolejności należałoby „skleić” dwa ciągi krawędzi, jest to jednak o tyle proste, że krawędzie wielokąta wypukłego muszą coraz bardziej skręcać w lewo. Czyli wyznaczenie X+Y tak naprawdę redukuje się do scalenia dwóch posortowanych ciągów.

Wynika stąd, że najtrudniejszą obliczeniową częścią jest wyznaczenie otoczek wypukłych obydwu zbiorów, co może być dość łatwo wykonane w czasie \mathcal{O}(k\log k).

Jest to już właściwie koniec pierwszej części rozwiązania. Wybierając za każdym razem m leżące mniej więcej w środku i wywołując się rekurencyjnie dla dwóch powstałych podproblemów, uzyskamy w czasie \mathcal{O}(n\log^2n) zbiór \mathcal{O}(n\log n) punktów, których otoczka wypukła jest otoczką wypukłą zbioru wszystkich możliwych różnic. Czemu czas jest właśnie taki? Chyba najprostsze uzasadnienie wymaga wyobrażenia sobie drzewa wywołań rekurencyjnych. Ma ono \log n poziomów, na każdym z nich sumy rozmiarów podproblemów sumują się do n, czyli związane z nimi czasy wyliczania sum Minkowskiego to (w sumie) \mathcal{O}(n\log n), co (znów w sumie) daje nam \mathcal{O}(n\log^2n). Przy odrobinie cierpliwości czas ten można zmniejszyć do \mathcal{O}(n\log n), co pozostawiam jako ciekawe ćwiczenie.

Druga część całego rozwiązania wymaga zastanowienia się nad następującym pytaniem: mając dane dwa zbiory wektorów P i Q, znajdź p\in P i q\in Q, które maksymalizują p \cdot q. Jak się do tego zabrać? Najprościej pewnie przejrzeć wszystkie p\in P. Mając ustalony (p_x,p_y) \in P chcemy zmaksymalizować p_x q_x + p_y q_y po (q_x,q_y) \in Q, jest to jednak to samo, co policzenie maksymalnej wartości wyrażenia q_x \frac{p_x}{p_y} + q_y (a następnie przemnożenie wyniku przez p_y; tak naprawdę należałoby jeszcze osobno rozpatrzeć przypadek, gdy p_y <0, ale na szczęście nie jest ona możliwa ze względu na to, że wszystkie oryginalne b_i i d_i są dodatnie). Hmmm. Czy przypomina Wam to jakiś inny problem związany z geometrią?

Powinno! Na elementy Q można patrzeć jak na funkcje liniowe postaci y=a_i x + b_i . Wtedy maksymalizacja wspominanego wyżej wyrażenia sprowadza się do zlokalizowania funkcji liniowej, która przyjmuje największą wartość dla danego x. Po chwili refleksji można dojść do przydatnego wniosku, że jeśli funkcji jest k, można podzielić [-\infty,\infty] na co najwyżej k+1 przedziałów o takiej własności, że dla wszystkich x należących do jednego przedziału najlepsza funkcja jest taka sama, tak jak na poniższej ilustracji.

podatki-upper

Problem znajdowania takiego podziału jest znany jako konstrukcja górnej koperty zbioru funkcji liniowych, i może być dość ładnie rozwiązany w czasie \mathcal{O}(k\log k): otóż można w cwany sposób zamienić funkcje liniowe na punkty, co znane jest jako przejście na płaszczyznę dualną, policzyć górną otoczkę tychże punktów, a następnie wrócić z pozostałymi punktami do świata funkcji liniowych, czyli na płaszczyznę prymalną. Czyli takie jakby „There and back again”. Dość szczegółowy opis całej metody można znaleźć tutaj.

Mając dany podział [-\infty,\infty] na rozłączne przedziały, i znając najlepszą funkcję liniową dla każdego z nich, wystarczy teraz zlokalizować za pomocą wyszukiwania binarnego przedział odpowiadający danemu \frac{p_x}{p_y}, no i odczytać maksymalną wartość wyrażenia. Sumaryczna złożoność tej części to \mathcal{O}(k\log k).

I to już koniec! Konstruujemy dwa zbiory wektorów o rozmiarze k\in \mathcal{O}(n\log n), a następnie wyznaczamy maksymalną wartośc wyrażenia w czasie \mathcal{O}(k\log k). Całkowity czas działania to \mathcal{O}(n\log^2n), czyli całkiem ciekawie. Jeden z logarytmów bierze się tak naprawdę po prostu z sortowania, co oznacza, że całe rozwiązanie działa dość szybko.

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