Omówienie zadania Montażysta (I etap XXIX OI)

Obserwacje

Na początek zróbmy dwie proste obserwacje. Przede wszystkim, nie opłaca się robić przerw między montowanymi filmami, tzn. po zmontowaniu filmu można od razu montować kolejny. Tak jest, bo w dowolnym rozwiązaniu, w którym istnieje przerwa długości \(t\) dni, możemy ją usunąć i zacząć montować wszystkie filmy po niej o \(t\) dni wcześniej. Oczywiście nie popsuje to poprawności rozwiązania.

Po drugie, wybrane filmy opłaca się montować w kolejności ich terminów publikacji. Załóżmy dla uproszczenia naszych rozważań, że terminy te są nierosnące: \(d_1 \leq d_2 \leq \ldots \leq d_n.\) (W programie to założenie realizujemy przez wstępne posortowanie filmów po ich terminach publikacji, jednak z zapamiętaniem ich oryginalnych numerów, żeby można było je odtworzyć w odpowiedzi.) Zatem jeśli wybierzemy pewien podzbiór filmów, to można je montować w kolejności rosnących numerów. Tak jest, bo jeśli w optymalnym rozwiązaniu mamy jakąś inną kolejność, to znaczy, że istnieją w nim dwa filmy \(a\) i \(b\), które montujemy po sobie, dla których \(a > b\), więc \(d_a > d_b\).

Zamieńmy teraz te filmy miejscami. Ta zamiana nie ma wpływu na inne filmy, bo nadal sumaryczny czas montażu tych dwóch wynosi \(t_a + t_b\). Film \(b\) będzie zmontowany wcześniej (więc nic się tu nie popsuje), a film \(a\) zostanie zmontowany później, ale nadal zdąży na termin publikacji \(d_b\) (bo wcześniej film \(b\) zdążył) więc również na termin \(d_a\).

Zamiana zmniejsza liczbę inwersji w ciągu numerów filmów i nie psuje poprawności rozwiązania. Wykonując zamiany tak długo, jak liczba inwersji jest dodatnia, w końcu dojdziemy do poprawnego rozwiązania, w którym zbiór filmów montujemy w kolejności rosnących numerów.

Tak więc rozwiązanie jest jednoznacznie wyznaczone przez wybór podzbioru filmów do montowania. Dla danego podzbioru łatwo jest w czasie \(O(n)\) sprawdzić, czy prowadzi on do poprawnego rozwiązania, przeglądając filmy po kolei i sprawdzając, czy nie przekraczamy żadnego terminu.

To prowadzi do rozwiązania, w którym sprawdzamy wszystkie możliwe podzbiory. Ma ono złożoność czasową \(O(2^n n)\) i zalicza pierwsze podzadanie.

Programowanie dynamiczne

Spróbujmy wybrać największy podzbiór filmów, stosując programowanie dynamiczne. Będziemy dodawać filmy po kolei; numer aktualnie rozważanego filmu będzie pierwszym wymiarem naszej tabelki. Co musimy wiedzieć o prawidłowym rozwiązaniu ograniczonym do filmów ze zbioru \(\{1, \ldots, i\}\), żeby móc je rozszerzyć o kolejny film? Potrzebujemy wiedzieć, ile filmów zostało wybranych w tym rozwiązaniu oraz jaki jest sumaryczny czas ich montażu. Ponieważ liczba wybranych filmów jest ograniczona przez \(i\), to zrobimy z niej drugi wymiar tabelki. Niech zatem \(dp[i,k]\) oznacza minimalny czas na prawidłowe zmontowanie dokładnie \(k\) filmów ze zbioru \(\{1, \ldots, i\}\). Rekurencja jest następująca:
\[dp[i,k] = \left\{\begin{array}{ll} \min( dp[i-1,k],\ dp[i-1,k-1] + t_i ) & \textrm{ jeśli } dp[i-1,k-1] + t_i \leq d_i, \\ dp[i-1,k] & \textrm{ w przeciwnym przypadku.} \end{array}\right.\]
Jej poprawność wynika z faktu, że możemy albo nie montować \(i\)-tego filmu (i wtedy \(k\) filmów musi być wziętych ze zbioru \(\{1,\ldots,i-1\}\), więc minimalny czas ich montażu to \(dp[i-1,k]\)), albo zmontować \(i\)-ty film, ale tylko wtedy, gdy możemy odpowiednio wcześnie skończyć montowanie \(k-1\) filmów ze zbioru \(\{1,\ldots,i-1\}\).

Warunkami początkowymi rekurencji są \(dp[0,0] = 0\) oraz \(dp[0,k] = \infty\) dla \(k > 0\). Natomiast odpowiedzią będzie maksymalne \(k\), dla którego \(dp[n,k] \neq \infty\). Czas działania tego algorytmu to \(O(n^2)\), co daje zaliczenie drugiego podzadania.

Algorytm zachłanny

Czasem analiza rozwiązania opartego na programowaniu dynamicznym może nas prowadzić do odkrycia algorytmu zachłannego. Zauważmy, że jeśli dla zbioru \(\{1,\ldots,i-1\}\) maksymalna liczba zmontowanych filmów to \(k\), to dla zbioru \(\{1,\ldots,i\}\) ta liczba może być równa albo \(k\), albo \(k+1\), bo możemy co najwyżej rozszerzyć rozwiązanie o film \(i\)-ty. Rozszerzenie możemy zrobić wtedy, gdy \(dp[i-1,k] + t_i \leq d_i\) i sumaryczny czas będzie wynosić \(dp[i-1,k] + t_i\).

Jeśli nie możemy rozszerzyć rozwiązania, to wtedy odpowiedź pozostaje równa \(k\), ale nadal musimy wykonać trochę dodatkowej pracy, by obliczyć minimalny czas montażu. Nie musi być on bowiem równy \(dp[i-1,k]\). W ogólności musimy popatrzeć na optymalny czas dla \(k-1\) filmów \(dp[i-1,k-1]\) i jeśli \(dp[i-1,k-1] + t_i \leq d_i\), to możemy wziąć \(\min(dp[i-1,k],\ dp[i-1,k-1] + t_i)\). Jak jednak obliczyć \(dp[i-1,k-1]\) bez wykonywania całego programowania dynamicznego?

Niech \(S \subseteq \{1,\ldots,i-1\}\) będzie optymalnym zbiorem \(k\) filmów o czasie montażu \(dp[i-1,k]\). Może się okazać, że istnieje pewien film \(s \in S\), który ma dłuższy czas montażu niż film \(i\)-ty, czyli: \(t_s > t_i\). Wtedy, zamieniając film \(s\)-ty na \(i\)-ty, dostajemy poprawne rozwiązanie \(S\setminus\{s\}\cup\{i\}\) z \(k\) filmami o krótszym czasie montażu \(dp[i-1,k] - t_s + t_i\). Obiecującym pomysłem może być więc wymiana filmu \(s\) o maksymalnym czasie montażu spośród wszystkich filmów ze zbioru \(S\).

Pytanie, czy taka ewentualna wymiana będzie optymalna? Innymi słowy, czy jest spełnione \(dp[i-1,k-1] = dp[i-1,k] - t_s\). Załóżmy nie wprost, że nie jest, czyli \(dp[i-1,k-1] + t_s < dp[i-1,k]\). Niech \(r\) będzie ostatnim filmem wziętym w rozwiązaniu \(S\). Ponieważ \(s\) miał najdłuższy czas montażu, więc \(t_r \leq t_s\). Jeśli dodamy \(r\) jako \(k\)-ty film do optymalnego zbioru \(S'\subseteq\{1,\ldots,i-1\}\) zawierającego \(k-1\) filmów, a możemy to zrobić, bo \(d_r \geq dp[i-1,k] > dp[i-1,k-1] + t_s \geq dp[i-1,k-1] + t_r,\) to dostaniemy rozwiązanie dla \(k\) filmów o czasie \(dp[i-1,k-1] + t_r \leq dp[i-1,k-1] + t_s < dp[i-1,k]\), czyli lepszym niż optymalny, co da nam sprzeczność (i tym samym kończy dowód).

Zatem możemy zaproponować następujący algorytm zachłanny: będziemy dodawać filmy po kolei, cały czas utrzymując częściowe rozwiązanie (sumę czasów oraz zbiór użytych filmów) dla maksymalnego \(k\). Jeśli możemy je rozszerzyć do \(k+1\), to to robimy, w przeciwnym wypadku dodajemy film \(i\)-ty do zbioru i wyrzucamy z niego film o najdłuższym czasie montażu.

Zbiór możemy reprezentować na kolejce priorytetowej, wtedy operacje dorzucenia i usunięcia będą działały w czasie \(O(\log n)\). Uwzględniając początkowe sortowanie filmów, dostaniemy algorytm o złożoności \(O(n\log n)\), zaliczający wszystkie podzadania.