Lepsza produktywność

Tym razem krótko o zadaniu z NWERC 2015, w którym interesuje nas podzielenie podanego zbioru przedziałów na ustaloną liczbę niepustych grup tak, aby zmaksymalizować sumę długości przecięć przedziałów przydzielonych do tej samej grupy. Spróbujemy rozwiązać je nieco szybciej niż autorzy!

Całą treść można zobaczyź tutaj. Dość istotne jest w niej to, że przecięcie przedziałów przydzielonych do tej samej grupy koniecznie musi mieć niezerową długość, czyli na przykład [1,2] oraz [2,3] nie mogą trafić do tej samej grupy. Istotne są też dość małe limity na liczbę podanych przedziałów n \leq 200. O liczbie grup p wiemy tylko, że nie przekracza n.

Wyobraźmy sobie przedział [\ell_i,r_i], w którym zawiera się pewien inny przedział [\ell_j,r_j], czyli formalnie \ell_i \leq \ell_j oraz r_j \leq r_i. Twierdzimy, że bez straty ogólności i-ty przedział jest jedynym przedziałem w swojej grupie lub i-ty oraz j-ty przedział są w tej samej grupie. Jeśli bowiem jest inaczej, to znaczy i-ty nie jest jedynym przedziałem w swojej grupie, a j-ty przedział znajduje się w innej grupie, możemy przenieść ten i-ty tak, aby znalazł się w tej samej grupie co j-ty. Łatwo sprawdzić, że nie popsuje to rozwiązania, a być może nawet zwiększy sumaryczną sumę długości przecięć. Dalej, możemy tymczasowo usunąć i-ty przedział ze zbioru i spróbować powtórzyć całe rozumowanie. Prędzej lub później doprowadzi to do sytuacji, w której żaden przedział nie zawiera się w innym. Musimy jednak pamiętać, że tymczasowo usunęliśmy pozostałe przedziały. Wiemy jednak, że bez straty ogólności każdy z tych usuniętych albo jest jedynym przedziałem w swojej grupie albo w zasadzie nie jest istotny. Wystarczy więc zgadnąć ile z tych tymczasowo usuniętych przedziałów tworzy jednoelementowe grupy, nazwijmy tę liczbę p', i znaleźć optymalny podział nieusuniętych przedziałów na p-p' grup. Następnie musimy tylko wybrać p' tymczasowo usuniętych przedziałów o największych długościach (dokładniej: możemy wybrać dowolne p' z nich, ale skoro maksymalizujemy sumę długości to w zasadzie nie mamy dużego pola manewru) i dorzucić je jako jednoelementowe grupy do skonstruowanego rozwiązania.

Zredukowaliśmy efektywne rozwiązanie całego zadania do wyliczenia, dla każdego p', optymalnego podziału na p' grup zbioru przedziałów, z których żaden nie zawiera się w innym. Dlaczego miałoby to być prostsze niż rozwiązanie oryginalnego problemu? Nooo takie przedziały na pewno łatwiej sobie wyobrazić. Jeśli posortujemy je bowiem względem lewych końców, czyli tak by \ell_1 \leq \ell_2 \leq \ldots \leq \ell_n, prawdą będzie także r_1 < r_2 < \ldots < r_n. Gdyby tak bowiem nie było, czyli r_i \geq r_{i+1} dla jakiegoś i, to przecież i+1-ty przedział zawierałby się w i-tym! (Tak naprawdę także lewe końce będą ściśle rosnące, ale nie jest to istotne.) Twierdzimy, że w związku z tym optymalny podział można sobie wyobrażać tak jak na poniższej ilustracji.

lepsza1

Czyli, bez straty ogólności, każda grupa jest postaci [\ell_i,r_i], [\ell_{i+1},r_i+1], \ldots, [\ell_j,r_j]. Wyobraźmy sobie bowiem dowolne rozwiązanie. Jeśli przedziały [\ell_i,r_i] oraz [\ell_{i+1},r_{i+1}] należą do różnych grup, [\ell_i,r_i] nie jest ostatnim przedziałem w swojej grupie (ostatnim czyli takim o największym indeksie), a [\ell_{i+1},r_{i+1}] nie jest pierwszym przedziałem w swojej grupie, możemy przerzucić i+1-ty przedział do tej samej grupy, do której należy i-ty. Nie spowoduje to zmiany długości przecięcia przedziałów należących do tej grupy ze względu na uporządkowanie \ell_1,\ell_2,\ldots,\ell_n oraz r_1,r_2,\ldots,r_n. Jeśli zaś [\ell_{i+1},r_{i+1}] jest jedynym przedziałem w swojej grupie, także możemy przerzucić go do tej samej grupy, do której należy i-ty przedział, jeśli jednocześnie wyrzucimy z tej grupy (to znaczy: przerzucimy do nowej grupy) wszystkie dalsze przedziały, które były w tej samej grupie co ten i-ty. Można sprawdzić, że nie spowoduje to zmiany sumy długości wszystkich przecięć, choć same przecięcie być może trochę się zmienią. Powtarzając takie rozumowanie prędzej lub później doprowadzimy do tego, że każda grupa jest żądanej postaci.

Co dalej? Dalej jest już standardowe programowanie dynamiczne. Dla każdego i=n,n-1,\ldots,1 oraz k=1,2,,\ldots,n wyznaczamy optymalny podział przedziałów [\ell_i,r_i],[\ell_{i+1},r_{i+1}],\ldots,[\ell_n,r_n] na k grup. W tym celu po prostu zgadujemy j, które wyznacza pierwszą grupę [\ell_i,r_i],[\ell_{i+1},r_{i+1}],\ldots,[\ell_j,r_j]. Sprawdzamy, czy r_i > \ell_j, wyciągamy koszt optymalnego podziału pozostałych przedziałów i dodajemy do niego r_i - \ell_j. Całość łatwo zaimplementować w czasie \mathcal{O}(n^3) i dostać Accepted.

Ale to przecież wolno. Czy naprawdę musimy naiwnie zgadywać każde j? Oznaczmy przez T_k[i] wyznaczany koszt optymalnego podziału. Zauważmy, że interesujące nas j tworzą spójny zakres i,i+1,\ldots,j(i), co więcej j(i) \leq j(i+1). Tak naprawdę w każdym kroku wyliczamy:

T_k,[i] = \min\{ T_{k-1}[j+1] + \ell_{j} -r_i : j=i,i+1,\ldots,j(i) \}.

Składnik -r_i pojawia się w każdym z wyliczanych wyrażeń, więc oznaczając f_k(j) = T_{k-1}[j+1] + \ell_j interesuje nas wyznaczenie minimum z f_k(i),f_k(i+1),\ldots,f_k(j(i)). Teraz jest już dość jasne, że obliczenia wykonywane dla kolejnych i nie są takie całkiem niezależne. Ale jak skorzystać z tej zależności?

Wystarczy przechowywać wszystkie f_k(i),f_k(i+1),\ldots,f_k(j(i)) w strukturze danych, która umożliwia szybkie wyznaczanie minimum, dorzucanie nowej liczby, oraz usuwanie wcześniej wrzuconej liczby. Taką strukturą może być na przykład zwykły set. Przed zmniejszeniem i o jeden dorzucamy f_k(i-1) oraz wyrzucamy f_k(j(i-1)+1),f_k(j(i-1)+2),\ldots,f_k(j(i)), a następnie pytamy się o minimum. Ponieważ każde f_k(i) zostanie wrzucone dokładnie raz (i wyrzucone co najwyżej raz), zmniejszy to czas wyliczenia T_k[i] do zamortyzowanego \mathcal{O}(\log n), dając nam tym samym rozwiązanie o całkowitym czasie działania \mathcal{O}(n^2\log n). Koniec?

Prawie. Przecież wcale nie jest jasne, że set to najlepszy możliwy wybór. Można skonstruować strukturę, w której wszystkie interesujące nas operacje działają w zamortyzowanym czasie stałym, co zmniejsza całkowity czas działania do kwadratowego. Taka struktura przydała nam się w jednym z archiwalnych odcinków, więc teraz już koniec. Chyba?

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