Fragmentacja

Dziś proponuję przyjemne (choć może niezbyt trudne) i świeże zadanie F z NEERC Northern Subregional 2014. Autor prosi nas o pokrojenie podanego ciągu na jak najmniej kawałków tak, aby przestawiając otrzymane kawałki można było posortować cały ciąg. Oczywiście interesuje nas skonstruowanie rozwiązania o liniowym czasie działania.

Treść można zobaczyć tutaj. Nie ma w nim wiele więcej ponad to co napisałem wyżej, choć… no właśnie, autor życzy sobie wypisania nie tylko najmniejszej możliwej liczby kawałków, ale też samego optymalnego podziału. Ewidentnie ma to na celu podniesienie nam ciśnienia, więc na razie zajmiemy się wyliczeniem tylko liczby kawałków. Być może istotne jest też ograniczenie na długość ciągu n \leq 10^5 i jego elementy a_i\in [1,10^5].

Na pierwszy rzut oka może się wydawać, że zadanie jest wręcz trywialne. Zamiast liczyć kawałki można bowiem równie dobrze liczyć cięcia. Teraz jeśli w naszym ciągu mamy dwóch sąsiadów \ldots,a_i,a_{i+1},\ldots, to jedyny przypadek, w którym nie trzeba wykonać między nimi cięcia to ten, gdy a_{i+1} jest następnikiem a_{i} w posortowanym ciągu, gdzie przez następnik rozumiemy element, która docelowo znajdzie się tuż za a_i. Jeśli liczby w ciągu nie powtarzają się, każda (poza największą) z nich ma unikalnie zdefiniowany następnik, dostajemy więc prosty warunek na to, czy należy wykonać cięcie między a_i a a_{i+1}. Jeśli jednak liczby mogą się powtarzać, nie jest tak prosto. Nie bardzo bowiem wiadomo, gdzie w posortowanym ciągu trafi a_i, a więc też nie bardzo wiadomo jaki jest jej następnik. Czasami możemy jednak zauważyć, że a_{i+1} na pewno nie jest następnikiem a_i, a co za tym idzie na pewno trzeba wykonać między nimi cięcie. Jest tak gdy a_{i+1} < a_i lub a_i < a_k < a_{i+1} dla pewnego k. No i co?

No i nie wiadomo co. Jak na razie udało nam się zdecydować, że w niektórych miejscach na pewno trzeba wykonać cięcie. Fajnie byłoby umieć czasami stwierdzić, że w niektórych miejscach na pewno nie warto ciąć. Na pewno nie warto ciąć między a_i a a_{i+1} jeśli a_i=a_{i+1}. Możemy więc zaczać całe rozumowanie od „sklejenia” ze sobą duplikatów, które występują jeden po drugim. Zastanówmy się teraz, w których miejscach mamy dylemat w kwestii ewentualnego cięcia. Od tego momentu wygodniej będzie myśleć nie o cięciu między a_i a a_{i+1}, lecz o cięciu tuż za a_i. Dzięki wcześniejszemu sklejeniu duplikatów jedyna sytuacja, w której nie wiemy czy ciąć za a_i, to a_{i+1} równe najmniejszej liczbie większej niż a_i w zbiorze wszystkich wartości \{a_i : i=1,2,\ldots,n\}. Jeśli jest jednak tak, że zarówno a_i jak i ta liczba występują dokładnie raz w całym ciągu, na pewno nie należy ciąć. Pewnie dałoby się wykombinować jeszcze parę takich specjalnych przypadków, ale nie wydaje się to fantastycznym pomysłem. Lepiej poszukać jakiegoś wygodnego sposobu na opisanie całej sytuacji.

Wyboraźmy sobie graf,którego wierzchołki są podzielone na s=|\{a_i : i=1,2,\ldots,n\}| grup X_1,X_2,\ldots,X_s. Jak łatwo się domyśleć, wierzchołki w X_k odpowiadają kolejnym wystąpieniom k-tego elementu \{a_i : i=1,2,\ldots,n\} w ciągu. Teraz jeśli wierzchołek odpowiadający a_i należy do X_k, a wierzchołek odpowiadający a_{i+1} do X_{k+1}, łączymy te dwa wierzchołki skierowaną krawędzią. Na przykład dla ciągu [3,1,2,3,4,2,3,1,4,3,4] otrzymamy poniższy graf.

fragmentacja1

Teraz należy zauważyć, że wybranie, po których a_i nie ma cięcia, sprowadza się do wybrania niektórych (być może wszystkich, być może żadnej) krawędzi w tym grafie. Trzeba jednak uważać: nie możemy wybrać tych krawędzi całkiem dowolnie. Wybierając bowiem krawędź łączącą wierzchołek odpowiadający a_i z wierzchołkiem odpowiadającym a_j decydujemy, że a_i będzie ostatnim elementem o takiej wartości w posortowanym ciągu, a a_j pierwszym elementem o takiej wartości (też w posortowanym ciągu). Czyli dla każdego X_i możemy mieć co najwyżej jedną krawędź wchodzącą do jakiegoś wierzchołka z X_i, no i co najwyżej jedną krawędź wychodzącą z jednego z jakiegoś wierzchołka z X_i. Co więcej, jeśli |X_i| > 1, nie może być tak, że jakiś wierzchołka z X_i ma jednocześnie niezerowy stopień wejściowy i wyjściowy. Nietrudno przekonać się, że te warunki są konieczne i wystarczające, wystarczy więc pokazać, jak znaleźć największy spełniające je zbiór krawędzi.

Wyobraźmy sobie, że kolejno wybieramy krawędzie wychodzące z X_{s},X_{s-1},\ldots,X_1. Jasne staje się wtedy, że należy skorzystać z programowania dynamicznego. Dla każdego i=s,s-1,\ldots,1 wyznaczamy najlepsze rozwiązanie w grafie przykrojonym do X_i\cup\ldots x_s. Aby móc przejść z i do i-1, konieczne jest osobne wyznaczenie najlepszego rozwiązania, które nie wybiera żadnej krawędzi wychodzącej z X_i, oraz najlepszego rozwiązania, które wybiera krawędź wychodzącą z danego u\in X_i, dla każdego możliwego u. Wyliczamy więc |X_i|+1 liczb. Aby wyznaczyć najlepsze możliwe rozwiązanie, które wybiera krawędź wychodzącą z u\in X_i, musimy „zgadnąć” kolejną krawędź, to jest zdecydować, czy rozwiązanie nie wybiera żadnej krawędzi wychodzącej z X_{i+1}, czy też może wybiera krawędź wychodzącą z pewnego v\in X_{i+1}, przy czym jeśli |X_i| > 1 v nie może być drugim końcem (jedynej możliwej) krawędzi wychodzącej z u. Naiwna metoda wymagałaby przeiterowania się po wszystkich możliwych v, co mogłoby być dość wolne. Można jednak zauważyć, że interesuje nas to v, które maksymalizuje wynik. Wystarczy więc wcześniej wyznaczyć dwa różne v',v''\in X_{i+1}, które odpowiadają najliczniejszym rozwiązaniom, a następnie rozważyć te z nich, które są różne niż drugi koniec krawędzi wychodzącej z u. Zmniejsza to czas wyliczenia odpowiedzi dla danego u do \mathcal{O}(1) i daje obiecaną na samym początku złożonośc liniową o ile potrafimy szybko skonstruować cały graf. Konstrukcja grafu wymaga zaś tylko posortowania wszystkich elementów.

Może warto jeszcze krótko skomentować kwestię wyznaczenia samego optymalnego podziału. Nie wymaga to żadnego nowego pomysłu, lecz jest odrobinę męczące. Trzeba tylko przejść i=1,2,\ldots,s za każdym razem wybierając odpowiedni v (ewentualnie zapamiętać v, które maksymalizuje liczbę krawędzi) pamiętając, że pracujemy ze „skompresowaną” wersją oryginalnego ciągu.

Advertisements

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