Omówienie zadania Zapiekanki (III etap XXIV OI)

Prosta analiza testu przykładowego prowadzi do wniosku, że strategia zachłanna w tym zadaniu raczej nie zadziała. Przykładowo Bajtazar mógłby za każdym razem czekać, aż uzbiera się \(z\) klientów, aby całkowicie wypełnić piekarnik (oczywiście w ostatnim pieczeniu niekoniecznie). Ale symulacja tego procesu dla testu przykładowego daje dalece nieoptymalny czas oczekiwania, a mianowicie \(27\). Z kolei strategia, w której Bajtazar cały czas trzyma włączony piekarnik i co \(d\) chwil wydaje co najwyżej \(z\) zapiekanek, osiąga na teście przykładowym jeszcze gorszy wynik — \(29\).

W rozwiązaniu posłużymy się zatem metodą programowania dynamicznego. Stany określone będą przez aktualny czas oraz zbiór obsłużonych klientów.

Rozwiązanie \(O(kT)\)

Niech \(s_i\) oznacza chwilę, w której \(i\)-ty klient został obsłużony, tzn. dostał swoją zapiekankę. Z warunków zadania mamy \(t_i \leq s_i\). Na początek poczynimy dość oczywistą obserwację:

Obserwacja 1. Istnieje rozwiązanie optymalne, w którym obsługujemy klientów w kolejności przychodzenia, tzn. \(s_1 \leq s_2 \leq \ldots \leq s_k\).

Dowód. Załóżmy, że mamy jakieś rozwiązanie optymalne, w którym \(s_i > s_{i+1}\) dla pewnego \(1 \leq i < k\). W rozwiązaniu tym czas oczekiwania klientów o numerach \(i\) oraz \(i+1\) wynosi \(s_i - t_i + s_{i+1} - t_{i+1}\). Ale mamy nierówności \(t_i \leq t_{i+1} \leq s_{i+1} < s_i\), zatem możliwe jest obsłużenie tych klientów w przeciwnej kolejności (tzn. klienta \(i\) w chwili \(s_{i+1}\), a klienta \(i+1\) w chwili \(s_i\)). Da to czas oczekiwania \(s_{i+1} - t_i + s_i - t_{i+1}\), czyli dokładnie taki sam (czas oczekiwania pozostałych klientów też się nie zmienił). Możemy zatem dokonywać zmian tak długo, aż nie będzie istniał żaden indeks \(i\), dla którego \(s_i > s_{i+1}\). \(\square\)

Zdefiniujmy podproblem dla programowania dynamicznego w następujący sposób: jesteśmy w chwili \(t\), piekarnik jest pusty (więc możemy od razu zacząć nowe pieczenie) i dotychczas obsłużyliśmy już pewien podzbiór \(i\) klientów. Z obserwacji 1 wynika, że równie dobrze mogli to być klienci \(\{1, \ldots, i\}\), tak więc wystarczy nam znać jedynie liczbę obsłużonych klientów. Wypełnimy tablicę \(\mathit{dp}\), gdzie \(\mathit{dp}[t,i]\) oznacza minimalny czas oczekiwania klientów \(\{i+1, \ldots, k\}\), jeśli pierwszą chwilą, w której możemy uruchomić piekarnik jest chwila \(t\). Przy takich oznaczeniach naszym celem jest wyznaczenie wartości \(\mathit{dp}[0,0]\).

W chwili \(t\) musimy zdecydować, czy chcemy uruchomić piekarnik. Jeśli nie, to decyzję odkładamy na następny moment, czyli przechodzimy do sytuacji \(\mathit{dp}[t+1,i]\). Jeśli tak, to musimy też zdecydować, ile zapiekanek pieczemy. Łatwo zauważyć, że opłaca się piec zapiekanki dla jak największej liczby klientów, przy czym każdy z nich musi być gotowy odebrać zapiekanki w momencie zakończenia pieczenia, czyli w chwili \(t+d\). Ponadto nie możemy piec więcej niż \(z\) zapiekanek. Formalnie, pieczemy zapiekanki dla tych klientów \(j\) ze zbioru \(\{i+1, \ldots, \min(k, i+z)\}\), dla których \(t_j \leq t+d\) (znowu na bazie obserwacji 1 możemy rozważyć tych najwcześniejszych).

Oznaczmy przez \(J\) zbiór tych klientów. Ich sumaryczny czas oczekiwania wynosi \(\sum_{j\in J} (t+d-t_j)\). Następna chwila, w której możemy podjąć nową decyzję to \(t+d\) (moment zakończenia pieczenia). Zatem rekurencja wygląda następująco:

\[ \mathit{dp}[t,i] = \min\!\big( \mathit{dp}[t+1, i],\ \mathit{dp}[t+d, i + \lvert J \rvert] + \sum_{j\in J} (t+d-t_j) \big). \tag{1} \]

Potrzebujemy jeszcze określić warunki początkowe dla rekurencji. Mamy \(\mathit{dp}[t,k] = 0\) dla dowolnego \(t\), bo są to sytuacje, w których obsłużyliśmy już wszystkich klientów. Musimy też oszacować, jak dużą wartość może przyjąć parametr czasu \(t\), czyli jaka jest maksymalna chwila \(T\), do której na pewno uda się obsłużyć wszystkich klientów (wtedy będzie można przyjąć \(\mathit{dp}[T,i] = \infty\) dla \(i < k\)).

Obserwacja 2. W optymalnym rozwiązaniu ostatnie pieczenie nie skończy się później niż w chwili \(T = t_k + d \cdot \lceil k/z \rceil\).

Dowód. Nawet gdyby wstrzymać się z pieczeniem, do momentu, gdy przyjdzie ostatni klient, tj. chwili \(t_k\), i następnie piec zapiekanki bez przerwy, \(k\) zapiekanek uda się upiec w czasie \(d \cdot \lceil k/z \rceil\). \(\square\)

Musimy więc wypełnić tablicę \(\mathit{dp}\), która ma \(O(kT)\) komórek, przy czym \[T = t_k + d \cdot \lceil k/z \rceil.\] Wypełnienie komórki wymaga użycia wzoru (1), co zajmuje czas \(O(z)\), jeśli zbiór klientów \(J\) oraz koszt jego obsługi (tzn. sumaryczny czas oczekiwania klientów ze zbioru \(J\)) wyznaczamy, przeglądając wszystkich możliwych klientów.

Jednak przy odpowiednich obliczeniach wstępnych, możemy zbiory \(J\) wyznaczać w czasie stałym. Zdefiniujmy wartość \(\mathit{ost}(t)\) jako największy numer klienta, dla którego \(t_{\mathit{ost}(t)} \leq t+d\). Wtedy dla \(\mathit{dp}[t,i]\) zbiór \(J\) jest równy \(\{i+1, \ldots, \min(i+z, \mathit{ost}(t))\}\). Ponieważ tablicę \(\mathit{dp}\) wypełniamy w kolejności malejących wartości \(t\), możemy na bieżąco wyliczać aktualne \(\mathit{ost}(t)\). Wystarczy podstawić \(\mathit{ost}(t) := \mathit{ost}(t+1)\) i następnie zmniejszać \(\mathit{ost}(t)\) o \(1\), aż otrzymamy \(t_{\mathit{ost}(t)} \leq t+d\).

Jeśli dodatkowo wyznaczymy ciąg sum prefiksowych \(\mathit{pt}\) dla ciągu czasów, tzn. \(\mathit{pt}[0] = 0\) oraz \(\mathit{pt}[i] = \sum_{j=1}^{i} t_j\), to koszt obsługi klientów ze zbioru \(J\) będziemy mogli obliczyć ze wzoru \[ \sum_{j \in J} (t+d-t_j) = \lvert J \rvert \cdot (t+d) - \sum_{j\in J} t_j = \lvert J \rvert \cdot (t+d) - (\mathit{pt}[i+\lvert J\rvert] - \mathit{pt}[i]). \] Sumy prefiksowe możemy wyznaczyć w czasie \(O(k)\). Ostatecznie da nam to algorytm działający w czasie \(O(kT)\). Dla \(z=1\) mamy \(T = O(t_k + dk)\), zatem czas działania to inaczej \(O(t_k k + dk^2)\), co wystarcza do zaliczenia pierwszego podzadania. Poniżej pseudokod takiego rozwiązania.

Rozwiązanie \(O(k^3)\)

Widać, że problemem poprzedniego rozwiązania jest potencjalnie duża wartość \(T\). Dzieje się tak, gdyż decyzje o pieczeniu podejmujemy w każdej możliwej chwili, nie patrząc na to, że dla pewnych chwil na pewno nie będzie nam się opłacało zaczynanie pieczenia. W szczególności zauważmy, że w rozwiązaniu optymalnym musi zajść co najmniej jeden z przypadków: (1) uruchamiamy piekarnik w chwili 0 lub (2) kończymy pewne pieczenie w chwili \(t_j\) dla pewnego \(j\). Istotnie, gdyby żaden z tych przypadków nie zachodził, to moglibyśmy zacząć wszystkie pieczenia jedną chwilę wcześniej, co polepszyłoby nasze rozwiązanie.

Powyższy pomysł można uogólnić. Dla uproszczenia wyeliminujmy najpierw pierwszy przypadek. Każdego klienta, który pojawia się w chwili \(t_j < d\), zastępujemy klientem przychodzącym w chwili \(d\). Jednocześnie zapamiętujemy, że do ostatecznego wyniku musimy dodać \(d - t_j\). Po tej modyfikacji prawdziwa jest następująca obserwacja charakteryzująca możliwe chwile pieczenia:

Obserwacja 3. Istnieje rozwiązanie optymalne, w którym każde pieczenie kończy się albo w czasie \(t_j\) dla pewnego \(j\), albo w chwili \(t'+d\), gdzie \(t'\) jest chwilą, w której kończy się poprzednie pieczenie.

Dowód. Rozważmy pewne rozwiązanie optymalne. Dopóki istnieje w nim pieczenie kończące się w chwili \(t\), które nie spełnia powyższego warunku, pieczenie to przesuwamy tak, by zaczynało się o jedną jednostkę czasu wcześniej. Po skończonej liczbie takich kroków otrzymamy rozwiązanie, w którym każde pieczenie spełnia powyższy warunek. Ponieważ zagwarantowaliśmy \(t_j \geq d\) dla każdego \(j\), ostatecznie żadne pieczenie nie rozpoczyna się przed chwilą \(0\). \(\square\)

Powyższa obserwacja pozwala nam podzielić pieczenia na bloki składające się z kolejnych pieczeń wykonywanych bez przerw. Pierwsze pieczenie z każdego bloku kończy się w chwili \(t_i\). Powiemy, że blok jest zaczepiony w chwili, w której kończy się pierwsze pieczenie z tego bloku.

Dla przykładu z treści zadania mamy trzy bloki: pierwszy zaczepiony w chwili \(d=4\) z jednym pieczeniem, drugi zaczepiony w chwili \(t_3=10\) z trzema pieczeniami, oraz trzeci zaczepiony w chwili \(t_9=25\) z jednym pieczeniem.

Oczywiście sumaryczna liczba pieczeń jest ograniczona przez \(k\), zatem liczba pieczeń w każdym bloku też jest nie większa od \(k\). Zatem możemy usprawnić pierwsze rozwiązanie o założenie, że parametr \(t\) przyjmuje jedynie wartości ze zbioru \[ C = \{t_i + jd \mid 1 \leq i \leq k,\ {-1} \leq j \leq k \} \cap \{0,\ldots, T\}. \] Zbiór ten ma \(O(k^2)\) elementów, więc w tablicy \(\mathit{dp}\) trzeba wypełnić jedynie \(O(k^3)\) komórek.

Aby uzyskać taką złożoność czasową, musimy przechowywać jedynie komórki dla wartości \(t\) ze zbioru \(C\) oraz umieć szybko znajdować następną wartość \(t\). Załóżmy, że mamy wypełnioną tablicę \(\mathit{pt}\) oraz tablicę \(c[0\ldots m{-}1]\) zawierającą elementy zbioru \(C\) w kolejności rosnącej. Dalej kod wygląda następująco:

Rozwiązanie \(O(k^2)\)

Pociągnijmy dalej pomysł z blokami. Zauważmy, że każdorazowo po zakończeniu pieczenia podejmujemy decyzję, czy przedłużyć aktualny blok, czy też rozpocząć nowy blok w pewnej chwili \(t_j-d\). Nie analizowaliśmy jednak zależności pomiędzy czasem rozpoczęcia \(t\) a parametrem \(i\) (liczbą dotychczas obsłużonych klientów). A zależność ta pozwoli nam jeszcze przyspieszyć algorytm. Powiemy, że blok jest zaczepiony w kliencie \(i\), jeśli jest zaczepiony w \(t_i\) oraz \(i\) jest minimalnym indeksem o tej własności.

Obserwacja 4. Istnieje rozwiązanie optymalne, w którym dla każdego bloku zaczepionego w kliencie \(i\) klienci od 1 do \(i\) są obsłużeni przez pierwsze pieczenie z tego bloku albo przez poprzednie bloki.

Dowód. Jeśli blok jest zaczepiony w kliencie \(i\), to jego pierwsze pieczenie kończy się w czasie \(t_i\) oraz \(t_j < t_i\) dla \(j < i\). Gdyby więc klient \(i\) nie był obsługiwany przez pierwsze pieczenie bloku, to można by zacząć to pieczenie jedną chwilę wcześniej (klienci \(j < i\) nadal będą obsługiwani przez te same pieczenia) i uzyskać lepsze rozwiązanie. \(\square\)

Wynika z tego, że wystarczy, abyśmy rozważali komórki tablicy \(\mathit{dp}[t,i]\), dla których jest spełnione \(t=t_i\). Przyjmujemy dla uproszczenia, że \(t_0=0\) (zatem \(\mathit{dp}[0,0]\) ma też postać \(\mathit{dp}[t_i,i]\)). Założenie jest takie, że w chwili \(t_i\) zakończyliśmy pierwsze pieczenie z bloku, które zakończyło obsługę klientów \(\{1, \ldots, i\}\), a od chwili \(t_i\) rozpoczynamy kolejne pieczenia z bloku. W pewnym momencie przerwiemy blok, a następny będzie zaczepiony w pewnym \(t_j\). Rekurencja wygląda więc następująco:

\[ \mathit{dp}[t_i,i] = \min_{i+1\leq j \leq k} \big( \mathit{dp}[t_j,j] + \mathit{koszt}(i+1,j) \big), \]

gdzie \(\mathit{koszt}(i+1,j)\) jest kosztem obsługi klientów \(\{i+1,\ldots,j\}\) przy założeniu, że obsługujemy ich pieczeniami bloku zaczepionego w \(t_i\) lub pierwszym pieczeniem następnego bloku (zaczepionego w \(t_j\)). Ze względu na to, że wartość \(\mathit{koszt}(i+1,j)\) musi uwzględniać pieczenia z dwóch różnych bloków, wyznaczenie jej będzie wymagało trochę zręczności.

Zauważmy, że nowy blok zaczynamy w chwili \(t_j-d\), wobec tego ostatnie pieczenie z bloku zaczepionego w \(t_i\) musi zakończyć się ściśle przed chwilą \(t_j-d\). Ponieważ nie musimy minimalizować liczby pieczeń, w bloku zaczepionym w \(t_i\) możemy wykonać tyle pieczeń, ile się da, dzięki czemu będziemy mogli wyznaczyć maksymalną wartość \(x\), dla której klientów \(\{i+1,\ldots,x\}\) uda nam się obsłużyć w bloku zaczepionym w \(t_i\), natomiast klientów \(\{x+1,\ldots,j\}\) będziemy musieli obsłużyć w pierwszym pieczeniu następnego bloku (jeśli nie da się obsłużyć tych klientów, bo zostanie ich więcej niż pojemność piekarnika \(z\), to będziemy musieli przyjąć \(\mathit{koszt}(i+1,j)=\infty\)).

Wartość \(x\) wyznaczamy następująco. Będziemy dokładać kolejne pieczenia do bloku zaczepionego w \(t_i\), tak aby obsłużyć kolejnych klientów. Przyjmijmy, że klientów o numerach od \(i+1\) do \(x'\) przydzieliliśmy już do pieczeń w bloku zaczepionym w \(t_i\). Niech \(\mathit{koniec}\) będzie zmienną oznaczającą czas zakończenia ostatniego pieczenia w bloku (tj. pieczenia obsługującego klienta \(x'\)). Z kolei przez \(\mathit{zap}\) oznaczmy, ile jeszcze zapiekanek możemy dołożyć do tegoż ostatniego pieczenia. Wówczas zapiekankę dla klienta \(x'+1\) możemy dołożyć do ostatniego pieczenia w bloku dokładnie wtedy, gdy:

• \(\mathit{zap} > 0\) (w piekarniku jest miejsce);
• \(t_{x'+1} \leq \mathit{koniec}\) (klient pojawi się dostatecznie wcześnie).

Druga opcja to dołożenie nowego pieczenia do obsługi klienta \(x'+1\). Możemy z niej skorzystać, gdy zachodzą dwa poniższe warunki:

• \(t_{x'+1} \leq \mathit{koniec} + d\) (klient pojawia się dostatecznie wcześnie, by załapać się na pieczenie rozpoczynające się tuż po poprzednim pieczeniu);
• \(\mathit{koniec} + d < t_j - d\) (po dodaniu pieczenia blok zaczepiony w \(t_i\) zakończy się ściśle przed blokiem zaczepionym w \(t_j\)).

Zauważmy, że jeśli nie możemy dołożyć klienta \(x'+1\) ani do ostatniego pieczenia, ani do następnego, to możemy przerwać blok zaczepiony w \(t_i\), gdyż taka sytuacja została już obsłużona dla \(j=x'+1\).

Pseudokod rozwiązania podajemy poniżej. Korzystamy w nim z pomocniczych funkcji \(\mathit{MożnaObsłużyćOstatnim}\) i \(\mathit{MożnaObsłużyćNowym}\), które sprawdzają dwa zestawy warunków zdefiniowane powyżej, tj. mówią, czy kolejnego klienta możemy obsłużyć w ostatnim lub nowym pieczeniu bloku zaczepionego w \(t_i\).

W kodzie zamiast \(\mathit{dp}[t_i,i]\) używamy już jednowymiarowej tablicy \(\mathit{dp}[i]\). Wprowadzamy też dla uproszczenia dodatkowego klienta o numerze \(k+1\), dla którego \(t_{k+1} = T + d+1\).

Powyższy algorytm ma złożoność czasową \(O(k^2)\) i pamięciową \(O(k)\). Wystarcza to do rozwiązania wszystkich podzadań.