Multizbiory

W kolejnym odcinku proponuję zadanie polecane przez mojego korespondenta (chwilowo) w Jekaterinburgu, mieście znanym z przemysłu ciężkiego i turnieju Ural Sport Programming Championship, którego tegoroczną atrakcją był bezwzględny pojedynek 5 najlepszych drużyn z Rosji vs 5 najlepszych drużyn z Chin. Popatrzmy na zadanie, którego nie udało się pokonać żadnej z nich!

Treść (zadania D) wymaga niestety więcej niż jednego zdania, ale naprawdę warto. Mamy dany ciąg liczb liczb S_1,S_2,\ldots,S_n. Patrzymy się na jego wszystkie spójne podciągi, czyli fragmenty postaci S_i,S_{i+1},\ldots,S_j, które sortujemy w dość dziwny sposób. Mianowicie aby porównać dwa fragmenty X i Y, szukamy najmniejszej liczby a, która występuje różną liczbę razy w X i Y (jeśli takiej liczby nie ma, fragmenty są dla nas takie same, czyli X \sim Y). X jest mniejszy niż Y (lub, dla uproszczenia opisu, X \prec Y) dokładnie wtedy, gdy a występuje więcej razy w X niż w Y. Teraz naszym zadaniem jest wyznaczenie k-tego fragmentu w tym dziwnym porządku. Pewnie warto przez chwilę zwątpić, czy ten dziwny porządek jest faktycznie porządkiem, czyli czy X \prec Y \prec Z implikuje, że X \prec Z. W przeciwnym wypadku ciężko byłoby bowiem mówić o sortowaniu, no ale na szczęście tak właśnie jest.

Widzimy, że n\leq 150 000, no i k \leq \frac{n(n-1)}{2}, czyli pewnie wygenerowanie i posortowanie wszystkich fragmentów nie jest najlepszym z możliwych pomysłów. Ba, problematyczne byłoby już nawet samo wygenerowanie, nie mówiąc o tym, że porównanie dwóch fragmentów wydaje się wymagać czasu proporcjonalnego do ich długości. Zaczyna się robić ciekawie!

Co prawda interesuje nas wyznaczenie k-tego fragmentu, ale może wypadałoby urealnić oczekiwania i zacząć od próby skonstruowania efektywnego sposobu zliczania fragmentów, które są ściśle mniejsze od danego? Jest to dość standardowe podejście: zamiast rozwiązywać „znajdź najmniejsze dobre rozwiązanie”, patrzymy na „czy dane rozwiązanie jest dobre”. Zwykle wystarczy potem zastosować tylko wyszukiwanie binarne, i elegancko dostajemy odpowiedź. No, w tym konkretnym przypadku nie będzie tak łatwo, a nawet będzie całkiem trudno, ale to w tym momencie nieistotne.

Mając dany fragment X chcemy policzyć, ile jest fragmentów Y=S_i,S_{i+1},\ldots,S_j, dla których Y \prec X. Dość naturalne jest ustalenie i i przyjrzenie się wszystkim j, które spełniają żądany warunek. Po chwili namysłu można dostrzec, że

lepiej już nie będzie

lub, mówiąc bardziej formalnie, S_i,S_{i+1},\ldots,S_{j+1} \prec S_i,S_{i+1},\ldots,S_j: dodając kolejne elementy możemy tylko pogorszyć swoją sytuację, to jest zmniejszyć a, które ma więcej wystąpień. Wynika stąd, że interesują nas dokładnie j należące do pewnego przedziału [f_i,n]. Ale jak wyznaczyć to nieszczęsne f_i? Pewnie moglibyśmy zacząć od f_i=i i zwiększać je o jeden dopóki X \preceq S_i,S_{i+1},\ldots,S_{f_i}. Brzmi to całkiem rozsądnie, choć pojawiają się przynajmniej dwa problemy (OK, tak naprawdę to brzmi dość głupio, ale chciałem jakoś optymistycznie). Przede wszystkim potrzebujemy efektywnej metody na sprawdzanie, czy aktualne f_i należy zwiększyć o jeden. Jest to jednak dość łatwe: trzeba tylko skonstruować strukturę danych, która umożliwi nam przechowywanie dla każdego a różnicy między liczbą wystąpień w X i liczbą wystąpień w aktualnym S_i,S_{i+1},\ldots,S_{f_i}, oraz znajdowanie najmniejszego a, dla którego ta różnica nie jest zerem. No i zwiększanie f_i o jeden. Taką strukturą może być zwykłe drzewo licznikowe, które umożliwia wykonywanie zarówno aktualizacji, jak i pytań, w czasie \mathcal{O}(\log n). Dysponując takim narzędziem będziemy w stanie wyznaczyć każde f_i w czasie \mathcal{O}(n\log n). No i niby fajnie, ale w tym momencie pojawia się drugi problem: przecież mamy aż n różnych f_i, które wypadałoby znaleźć! Na szczęście można zauważyć, że f_{i+1} \geq f_i, czyli dla kolejnego i możemy zacząć od f_{i+1}=f_i. Jest to o tyle wygodne, że wspomniane przed chwilą drzewo licznikowe bez większych problemów pozwala także na zwiększenie i o jeden (lub, patrząc inaczej, na usunięcie S_i z aktualnego fragmentu). Czyli dla kolejnych i zwiększamy f_i o jeden tak długo, jak aktualny fragment jest większy lub równy X, a następnie usuwamy S_i ze struktury. Ponieważ f_i \leq n, wykonamy nie więcej niż 3n operacji na strukturze, co daje sumaryczny czas \mathcal{O}(n\log n). Fantastycznie.

Umiemy więc policzyć, ile fragmentów jest mniejszych od danego X. Używając bardzo podobnej (a może nawet prostszej) metody można też zliczyć fragmenty, które są równe (w sensie naszego dziwnego porządku) X. O ile więc tylko ktoś podrzuciłby nam fragment X, który wydaje się sensownym kandydatem na k-ty w porządku, umielibyśmy sprawdzić, czy nie jest to przypadkiem ściema (konkretnie: jeśli mamy \ell fragmentów, które są mniejsze, i e takich, które są równe X, wystarczy sprawdzić, czy \ell < k \leq \ell + e). Niestety, nie mamy co liczyć na żadną życzliwą podpowiedź. Nic to, poradzimy sobie sami!

Spróbujemy zastosować strategię przypominającą wyszukiwanie binarne. Na dobry początek możemy stwierdzić, że szukany fragment na pewno znajduje się (w zdefiniowanym wyżej porządku) między S_1,S_2,\ldots,S_n a (dowolnym) pustym fragmentem. Załóżmy więc, że wiemy już, że szukany X leży między fragmentami F a T. Co dalej? Gdyby tylko dało radę dobrać się do fragmentu M, który leży dokładnie w połowie drogi między F a T, byłoby już całkiem spoko. Powolutku policzylibyśmy sobie ile jest fragmentów mniejszych niż M, porównali tę liczbę z k, no i w zależności od wyniku zastąpili F lub T przez M (lub stwierdzili, że to właśnie M jest tym, czego brakuje nam do szczęścia). Dobranie się do takiego M wydaje się jednak być dość problematyczne, gdyż zakłada, że znamy cały porządek na fragmentach. A przecież nie znamy (czy też może: nie stać nas na to, żeby znać go w całości)!

Wybraźmy sobie wszystkie fragmenty, które leżą (w naszym dziwnym porządku) między F a T. Dla każdego i prawe końce takich fragmentów S_i,S_{i+1},\ldots,S_j tworzą spójny przedział j\in [f_i,f'_i], co więcej używając opisanej wyżej metody umiemy efektywnie wyznaczyć wszystkie f_i i f'_i. Można więc przedstawić interesujący nas zbiór jako sumę n mniejszych zbiorów (każdy z nich jest tak naprawdę posortowany, choć nie będzie to dla nas istotne). Ale co z tego?

Odpowiedź jest prosta i uzasadniona ewolucyjnie. Gdy nie wiadomo co zrobić, warto wpaść w panikę, to jest zrobić coś losowego. Zaszkodzić już nie zaszkodzi, a pomóc może. Spróbujmy więc wybrać losowy spośród fragmentów, które leżą między F a T. Jak? Skoro przedstawiliśmy je jako sumę n prostych do opisania zbiorów, wystarczy tylko wylosować zbiór (niekoniecznie jednostajnie, jako że ich rozmiary mogą być dość różne, czyli jeśli zbiory to A_1,A_2,\ldots,A_N, wybieramy A_i z prawdopodobieństwem \frac{|A_i|}{|A_1|+\ldots+|A_n|}), a następnie element w zbiorze. Następnie sprawdźmy, czy szukany fragment jest mniejszy czy większy (a może równy) od wylosowanego. I właściwie tyle. Ale ale jak to? Tyle? Dlaczego wybranie losowego elementu prowadzi do efektywnego rozwiązania? W tym momencie wypadałoby wiedzieć czym jest wartość oczekiwana i nierówność Azumy-Hoeffdinga.

OK, z tym drugim to tylko taki branżowy żarcik. Wybierając losowy element mamy sporą szansę, że liczba elementów między F a T istotnie się zmniejszy. Czemu? Najlepiej wyobrazić sobie sytuację korzystając z poniższej ilustracji, na której kolejne kropki reprezentują elementy między F a T ułożone w kolejności zgodnej z naszym dziwnym porządkiem. Powiedzmy, że jest ich N, a szukany element to duża czerwona kropka na pozycji k. Skoro wybieramy losowy element, z prawdopodobieństwem \frac{1}{2} będzie on w środkowym okienku długości \frac{N}{2}. Tak naprawdę sprawdzamy, czy wybrany element jest na prawo czy na lewo od szukanego, i w zależności od wyniku porównania pozbywamy się elementów na lewo lub na prawo od tego losowo wybranego. A to jest bardzo przyjemne: zawsze pozbędziemy się przynajmniej lewego lub prawego kawałka długości \frac{N}{4}. Czyli mamy przynajmniej \frac{1}{2} szansy na to, że liczba elementów między F a T spadnie przynajmniej o jedną czwartą.

multizbiory

Skoro zaczynamy z \frac{n^2}{2} kandydatami, szansa na to, że będziemy potrzebować dużo więcej niż, powiedzmy, 4\log \frac{n^2}{2} iteracji wydaje się dość mizerna. Darujemy sobie szczegółowe rachunki, wymagają one bowiem pewnej elementarnej wiedzy z rachunku prawdopodobieństwa: uwierzcie mi, że oczekiwana liczba rund to \mathcal{O}(\log n).

Świetnie. Otrzymaliśmy więc rozwiązanie o oczekiwanym czasie działania \mathcal{O}(n\log^2n), które w dodatku nie jest bardzo skomplikowane implementacyjnie: nawet ja dałem radę. Należy jednak zadać sobie pytanie: czy możliwe jest osiągnięcie liniowego czasu działania?

Tego nie wiem. Ale przecież nie może być tak, że \mathcal{O}(n\log^2n) to najlepsza możliwa złożoność! Zbicie liczby iteracji wydaje się raczej skazane na porażkę, jednak korzystaliśmy przecież także z drzewa licznikowego. Czy rzeczywiście musi być to drzewo licznikowe? Otóż nie musi, i korzystając z trochę bardziej zaawansownej struktury można uzyskać czas \mathcal{O}(n\log n\log\log n).

Reklamy

4 myśli nt. „Multizbiory

  1. Nie wiem czy to ważne, ale zgubiłem się na akapicie zaczynającym się od „Wybraźmy sobie wszystkie fragmenty, które leżą między F a T.”.
    To taki detal : f_i było już zdefiniowane wcześniej (ale wymagało istnienia X), zaś przedział tworzą nie podciągi, tylko j-ty — jak połączy się te dwa fakty i przeczyta drugie zdanie to można się nieźle zamieszać.

  2. Powiedzmy, że mamy kartkę w kratkę N x N pól, gdzie każde pole oznacza jeden przedział [początek,koniec].
    Tylko trójkątny fragment (początek<koniec) tej kraty ma oczywiście sens.
    Dla każdego pola wiemy, że musi być nie mniejsze od sąsiada po lewej, nie mniejsze od sąsiada u góry (no i asymetrycznie dla prawej i dołu). (Your milege may vary jeśli trzymasz mentalną kartkę inaczej niż ja).
    Mamy więc coś w klasycznym stylu: mając daną "bi-montoniczną" tablicę liczb, znajdź w niej K-ty co do wielkości element.
    Dałbym sobie coś uciąć, że już raz Ty (i/lub Młody) robiliście to zadanie i że dało się to jakoś sprytnie…. a może to było to samo zadanie?

  3. No ja robiłem (co do Marcina nie mogę się wypowiadać ;), i to wtedy da się jakoś tam fajnie, przy czym trzeba umieć porównywać dwa dowolne elementy, co w naszej sytuacji wydaje się dość kłopotliwe.

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