Mikołaj

W świątecznym odcinku rozwiążemy zadanie o Mikołaju. Mikołaj co prawda pojawia się w treści, lecz nie jest tam istotny, więc by podtrzymać świąteczny nastrój skonstruujemy rozwiązanie o złożoności \mathcal{O}(n\log^*n), gdzie \log^* to znany i lubiany logarytm z gwiazdką. W zadaniu dostajemy ciąg całkowitych liczb a_1,a_2,\dots,a_n oraz parametr L i jesteśmy proszeni o wyznaczenie spójnego fragmentu a_i,a_{i+1},\ldots,a_j o długości przynajmniej L, który maksymalizuje średnią wartość, czyli \frac{a_i+a_{i+1}+\ldots+a_j}{j-i+1}.

Zadanie pochodzi z ostatnich Mistrzostw Wielkopolski w Programowaniu Zespołowym, a oryginalną treść można zobaczyć tutaj. Istotne w niej (oprócz podanego wyżej sformułowania) są limity n\leq 10^6, latex L\in (0,N] i a_i\in [-10^6,10^6]. Dodatkowo warto zwrócić uwagę na smutny kawałek mówiący o tym, że w przypadku, gdy istnieje wiele spójnych fragmentów długości przynajmniej L, które maksymalizują średnią, należy wypisać najdłuższy z nich, a gdy jest wiele najdłuższych ten, który zaczyna się jak najwcześniej. Nie będziemy się tym szczególnie przejmować, jednak (w zależności od wybranej metody) może to mniej lub bardziej utrudnić implementację.

Zacznijmy od przeformułowania problemu. Policzmy najpierw wszystkie sumy prefiksowe s_i = a_1+a_2+\ldots_ai, wtedy celem staje się maksymalizacja wyrażenia \frac{s_j-s_{i-1}}{j-i+1} po wszystkich i,j dla których j-i+1\geq L. Co pewnie od razu daje nam naiwne rozwiązanie o złożoności \mathcal{O}(n^2), ale przecież musimy lepiej. Ale jak?

Pewnie należy zacząć od wyobrażenia sobie sytuacji. W tym zaś zwykle pomaga rysunek! Narysujmy więc sobie n+1 punktów postaci p_i=(i,s_i). Wtedy \frac{s_j-s_{i-1}}{j-i+1} to nic innego niż nachylenie odcinka łączącego p_{j-1} i p_i, czyli całe zadanie sprowadza się do znalezienia i+L\leq j dla których nachylenie odcinka p_i - p_j jest jak największe. (Być może warto choć przez chwilę zastanowić się nad sensownością tego warunku. Jego celem nie jest sztuczne utrudnienie zadania, lecz sprawienie, że nie jest ono trywialne. Łatwo bowiem pokazać, że bez niego wynik to po prostu \max_i a_i.)

Dość naturalnym pomysłem byłoby ustalenie i (czy też raczej rozważanie kolejno i=n,n-1,\ldots,1) i znalezienie dla niego najlepszego możliwego j. Interesują nas oczywiście tylko j=i+L,i+L+1,\ldots,n no i chciałoby się wybrać najlepsze z nich w czasie istotnie mniejszym niż n, czyli pewnie w \mathcal{O}(\log n). Może więc dałoby się zastosować tutaj wyszukiwanie binarne? Nie jest to jednak zupełnie trywialne. Przypomnijmy, że interesuje nas j, które maksymalizuje nachylenie odcinka p_i - p_j, a to nachylenie może być przecież zupełnie dowolne dla kolejnych j. Na szczęście można zauważyć, że większość j nie jest dla nas szczególnie interesująca niezależnie od tego jak właściwie wygląda p_i.

Lemat. Dla dowolnego punktu P leżącego na lewo od wszystkich p_{i+L},p_{i+L+1},\ldots,p_n prawdziwe jest następujące zdanie: jeśli bowiem p_j nie leży na lewejgórnej otoczce wszystkich p_{i+L},p_{i+L+1},\ldots,p_n, istnieje p_{j'} dla którego nachylenie odcinka P-p_j jest ściśle mniejsze niż nachylenie odcinka P-p_{j'}.

Dowód. Pewnie wypada zacząć od zdefiniowania lewejgórnej otoczki. Jest to ten fragment całej otoczki, który składa się z odcinków tworzących kąty należące do [0,\frac{\pi}{2}] idąc zgodnie z ruchem wskazówek zegara. Dla wygody przedłużmy sobie ten fragment dodając wirtualny punkt (\infty,y_{\max}), gdzie y_{\max} jest największą ze współrzędnych y wszystkich punktów. Teraz jeśli rozważymy p_j=(x,y), który nie leży na tym fragmencie, możemy znaleźć punkt z otoczki, który znajduje się dokładnie nad nim, czyli p'=(x,y') gdzie y' > y. Łatwo uwierzyć, że nachylenie P-p' jest ściśle większe niż nachylenie P-p_j jeśli P znajduje się na lewo od całego fragmentu.

mikolaj

Jeśli p' jest jednym z p_{j'}, otrzymaliśmy tezę. Jeśli tak nie jest, to p' należy do odcinka łączącego pewne p_{j'} i p_{j''}, które leżą na otoczce. Łatwo uwierzyć, że nachylenie P-p_{j'} lub P-p_{j''} nie jest mniejsze niż nachylenie P-p_j, co znów daje tezę.

Powyższy lemat mówi, że możemy zapomnieć o wszystkich p_j, które nie leżą na lewejgórnej otoczce. Jest to fajne z przynajmniej dwóch powodów. Po pierwsze, dość łatwo utrzymywać tę otoczkę rozważając coraz mniejsze i. Ma ona bowiem taką przyjemną własność, że utworzenie lewejgórnej otoczki dla zbioru punktów z dorzuconym jednym nowym, który leży na lewo od wszystkich poprzednich, sprowadza się do wyrzucenia pewnego prefiksu poprzedniej lewejgórnej otoczki i doklejenia nowego punktu, tak jak na poniższej (jak zwykle tendencyjnej) ilustracji.

mikolaj21

Drugi powód jest nawet lepszy. Jeśli bowiem kolejne punkty na otoczce to p_{j_1}, p_{j_2}, \ldots, p_{j_s}, to można zauważyć, że nachylenie P-p_{j_k} dla kolejnych k najpierw rośnie, potem być może przez chwilę zostaje takie samo, a następnie maleje. Nas interesuje pierwsze k, dla którego nachylenie maleje, możemy więc zastosować wyszukiwanie binarne! Pozwoli nam ono na znalezienie takiego k w czasie \mathcal{O}(\log n). Jest tutaj jednak jedna subtelność: w wyszukiwaniu binarnym chcielibyśmy mieć dostęp do dowolnego p_{j_k} w czasie stałym. Oznacza to, że cała otoczka powinna być przechowywana w tablicy czy strukturze typu vector/deque.

No dobrze, czyli pokazaliśmy, że dysponując aktualną otoczką trzymaną w strukturze ze stałym dostępem jesteśmy w stanie wybrać najlepsze możliwe j w czasie \mathcal{O}(\log n). Wspomnieliśmy również, że aktualizacja otoczki po zmniejszeniu i o jeden sprowadza się do usunięcia jej pewnego prefiksu i dorzucenia jednego nowego punktu, co może być dość łatwo wykonane o ile tylko punkty przechowujemy w kolejności od prawej do lewej. Co prawda może się zdarzyć, że w jednym kroku będziemy musieli usunąć wiele punktów, lecz skoro ich całkowita liczba to n, to sumaryczny czas spędzony na aktualizacji otoczki to tylko \mathcal{O}(n). Zaś sumaryczny czas spędzony na wyszukiwaniu binarnym to \mathcal{O}(n\log n), co w zupełności wystarczało do rozwiązania zadania. Ale chciałoby się lepiej, prawda?

Ano chciałoby się. No to spróbujmy. W przedstawionym powyżej rozwiązaniu odrobinę niedbałe wydaje się to, że co prawda udało nam się sprytnie ograniczyć zbiór j, które mogą odpowiadać optymalnemu rozwiązaniu, lecz przejrzeliśmy wszystkie możliwe i. A przecież sytuacja jest dość symetryczna, prawda? Równie dobrze można by więc ustalić j i pokazać, że wtedy wystarczy rozważać tylko te i, które odpowiadają punktom leżącym na prawejdolnej otoczce punktów p_1,p_2,\ldots,p_{j-L}. A może dałoby się jakoś chytrze połączyć te dwie metody?

Powiedzmy, że interesują nas i\leq i_0 i j\geq j_0, gdzie j_0-i_0\geq L. Wtedy wybór i jest niezależny od wyboru j, gdyż zawsze będziemy mieli j-i\geq L. Teraz jeśli interesuje nas maksymalizacja nachylenia odcinka p_i - p_j, bez straty ogólności możemy rozważać tylko i leżące na prawejdolnej otoczce punktów p_1,p_2,\ldots,p_{i_0} oraz tylko j leżace na lewejgórnej otoczce punktów p_{j_0},p_{j_0+1},\ldots,p_n. Tak naprawdę szukamy więc stycznej do tych dwóch otoczek, jak na poniższym rysunku.

mikolaj3

Taka styczna jest jednoznacznie wyznaczona, o czym pewnie najłatwiej przekonać się wyobrażając sobie bardzo długi patyk, który wsadzamy między otoczki i próbujemy jak najbardziej przekręcić. Ale jak ją szybko znaleźć? Można znów zastosować wyszukiwanie binarne. Tak naprawdę szukamy bowiem dwóch punktów p_{i'} i p_{j'}, które wyznaczają prostą, która separuje obydwie otoczki. Mając kandydata na i' można wyszukać binarnie j', dla którego druga otoczka jest na prawo od prostej przechodzącej przez p_{i'} i p_{j'}. Następnie możemy sprawdzić, czy pierwsza otoczka jest na lewo od tej prostej. Jeśli tak, znaleźliśmy nasze i' i j'. Jeśli nie, patrząc na p_{i'-1} i p_{i'+1} i wykonując prosty test na skręczanie można stwierdzić, czy właściwe i' jest przed czy też za naszym niefortunnie wybranym kandydatem. Czyli stosując dwa zagnieżdżone wyszukiwania binarne możemy wybrać optymalne i i j w czasie \mathcal{O}(\log^2n), o ile tylko obydwie otoczki są przechowywane w strukturze ze stałym dostępem. A nawet lepiej: zachowując odrobinę ostrożności można uzyskać czas \mathcal{O}(\log n).

No dobrze, ale skąd wziąć te i_0 i j_0? Podzielmy cały ciąg na fragmenty długości \log n i wypróbujmy kolejne i_0, które odpowiadają ostatnim elementom w kolejnych kawałkach, czyli i_0=\alpha\log n. Dla każdego takiego i_0 wybierzmy j_0=i_0+L i zastosujmy opisaną wyżej metodę (na razie ignorując kwestię przechowywania obydwu otoczek). Następnie zauważmy, że w większości przypadków umożliwia nam to wyznaczenie optymalnego rozwiązania. Jedyna sytuacja, w której możemy mieć z tym problem, to taka, że w szukanym optymalnym rozwiązaniu jest j-i< L+\log n. Najpierw wróćmy jednak do kwestii zapisywania otoczek. Przypomnijmy, że umiemy przechowywać aktualną prawą otoczkę w tablicy rozważając kolejne j_0=n,n-1,\ldots,1. Podobnie umiemy przechowywać aktualną lewą otoczkę rozważając kolejne i_0=1,2,\ldots,n. Ale, niestety, musimy zdecydować czy idziemy w lewo czy w prawo. Nie jest to jednak wielki problem. Można bowiem zapisać sobie gdzieś z boku jak zmienia się prawa otoczka gdy zmniejszamy aktualne j_0 o jeden (a dokładnie, zapisać jakie punkty zostają z niej wtedy usunięte). Taki zapis historii pozwala nam na odwrócenie zmian, czyli tak naprawdę przechowywanie aktualnej prawej otoczki dla kolejnych j_0=1,2,\ldots,n. Ponadto możemy skonstruować taki zapis w czasie \mathcal{O}(n), czyli sumaryczny czas działania całej procedury to \mathcal{O}(n+\frac{n}{\log n}\log n)=\mathcal{O}(n).

Jeśli tylko j-i > L+\log n możemy być pewni, że powyższa metoda pozwoli na znalezienie optymalnego rozwiązania w czasie \mathcal{O}(n), co rzecz jasna nie kończy jeszcze całej historii. Jest to jednak pewien postęp: przed chwilą wiedzieliśmy tylko, że j-i\in [L,n], a teraz wiemy już, że j-i\in [L,L+\log n]. Spróbujmy więc powtórzyć rozumowanie. Podzielmy cały ciąg na fragmenty długości \log\log n i wypróbujmy kolejne i_0=\alpha\log\log n. Dla każdego takiego i_0 znów wybierzmy j_0=i_0+L. Teraz jednak zamiast rozważać całe otoczki, myślmy tylko o sufiksie tej pierwszej złożonym z ostatnich \log n punktów, no i prefiksie tej drugiej złożonym z pierwszych \log n punktów. Skoro obydwie otoczki są zapisane w tablicach, sprowadza się to do patrzenia nie na całą tablicę, lecz tylko na jej kawałek, co nie przysparza żadnych dodatkowych trudności technicznych. Stosując zagnieżdżone wyszukiwanie binarne dla każdych takich dwóch fragmentów długości \log n na pewno wyznaczymy w czasie \mathcal{O}(n+\frac{n}{\log\log n}\log\log n)=\mathcal{O}(n) optymalne rozwiązanie jeśli j-i \in [L+\log\log n,L+\log n]. Co dalej?

Dalej jest tak samo. Dzielimy ciąg na fragmenty długości \log\log\log n, potem na fragmenty długości \log\log\log\log n, i tak dalej. W każdej z takich iteracji spędzamy tylko czas \mathcal{O}(n), no i prędzej lub później doprowadzimy do sytuacji, w której przedział, w którym znajduje się j-i odpowiadające potencjalnemu optymalnemu rozwiązaniu, ma długość ściśle mniejszą niż jeden, co daje nam n kandydatów do sprawdzenia. Ilość iteracji potrzebnych do doprowadzenia do takiej prostej sytuacji to nic innego jak logarytm iterowany, czyli sumaryczna złożoność całego rozwiązania to \mathcal{O}(n\log^* n).

Wszystkim, którzy dotarli aż tutaj, życzę udanych świąt i nowego roku, w którym wszystkie algorytmy będą liniowe!

Reklamy

5 myśli nt. „Mikołaj

  1. Ej, jak się pojawiła sztuczka z loglogn, to myślałem, że następnym etapem będzie jakiś wariant sztuczki czterech rosjan i stwierdzenie w stylu „no to możemy sobie stablicować wszystkie możliwe fragmenty długości loglogn” …

    • Trochę ciężko robi się takie tablicowanie w 2D. Tzn wydaje mi się, że powinno dać się zrobić coś w tym stylu, ale nie widzę jak dokładnie. Zresztą, gwiazdka pasowała mi do Mikołaja 😉

  2. Chyba jest też tak, że i-j < 2*L, bo w przeciwnym razie punkt po środku pi,pj, byłby zawsze niegorszym kandydatem niż i, bądź j (w zależnośći od tego po której stronie odcinka i-j leży).
    Btw. mam wrażnie, że to zadanie robiliśmy na jakimś ACMie (a dokładniej to chyba tarlandil robił).

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