Omówienie zadania Kucharz (III etap XXIV OI)

Treść zadania

Mamy \(n\) karteczek na szpikulcu, z którego możemy zdejmować tylko z góry oraz pewien poziom energii \(e\). Karteczki możemy zdejmować za pomocą trzech operacji. Koszt każdej z nich zależy od aktualnej liczby karteczek na szpikulcu \(k\):

• weź jedno zamówienie z góry – operacja ta kosztuje \(jedno(k)\) i zwiększa naszą energię o \(1\)
• weź dwa zamówienia z góry – operacja ta kosztuje \(dwa(k)\) i nie zmienia naszego stanu energii
• weź \(\lfloor \frac{k}{2} \rfloor\) zamówień z góry – operacja ta kosztuje \(polowa(k)\) i zmniejsza naszą energię o \(1\)

Nasz stan energii nigdy nie może spaść poniżej zera. Jakim minimalnym kosztem możemy zdjąć wszystkie karteczki ze szpikulca?

W zadaniu należało zwrócić uwagę na nietypowo niski limit pamięci wynoszący 8 MB, który oznaczał, że nawet pamięć rzędu \(3 \cdot n\) była niedopuszczalna. I to właśnie optymalizacja złożoności pamięciowej okazywała się tutaj największym wyzwaniem.

Dostęp do wartości \(jedno(k)\), \(dwa(k)\) i \(polowa(k)\) na szczęście został zapewniony w ramach biblioteczki, niewliczającej się do ograniczenia pamięciowego.

Podzadanie 1

Niewiele możemy wywnioskować na podstawie kosztów \(jedno(n)\), \(dwa(n)\) i \(polowa(n)\), dlatego intuicja podpowiada, że musimy rozważyć wykonanie każdego z tych ruchów:

• Wzięcie z góry jednej karteczki z góry sprowadza nas do tożsamego zadania, ale z liczbą karteczek mniejszą o jeden i energią większą o jeden.
• Wzięcie dwóch karteczek sprowadza nas do tożsamego zadania, ale z liczbą karteczek mniejszą o dwa i równą energią.
• Wzięcie \(\lfloor \frac{n}{2} \rfloor \) karteczek sprowadza nas do tożsamego zadania, ale z liczbą karteczek równą \(\lceil \frac{n}{2} \rceil \) i energią o jeden mniejszą.

Powyższe rozumowanie szkicuje nam algorytm programowania dynamicznego, w którym pierwszym wymiarem stanu będzie liczba karteczek, natomiast drugim – ilość energii, która nam pozostała. Taki algorytm można wyrazić następującą rekurencją, która w komórce \(dp[n][e]\) policzy wynik zadania:

\(dp[ile\_kartek][ile\_energii] = \min \left( \begin{array}{l} jedno(ile\_kartek)&+&dp[ile\_kartek-1][ile\_energii+1]\\ dwa(ile\_kartek)&+&dp[ile\_kartek-2][\;\;\; ile\_energii \;\;\;] \\ polowa(ile\_kartek)&+&dp[\;\;\; \lceil \frac{ile\_kartek}{2} \rceil \;\;\;][ile\_energii-1] \end{array} \right) \)

Trzeba tu oczywiście uważać jeszcze na skrajne przypadki, np. nie możemy w żadnym momencie mieć ujemnej ilości energii ani ujemnej liczby kartek.

Pozostało pytanie, jak duża musi być taka tablica programowania dynamicznego? Przy pojedynczym przejściu liczba karteczek zawsze się zmniejsza, ale liczba energii może wzrosnąć. Może wzrosnąć jednak o co najwyżej jeden, więc nasza liczba energii nigdy nie przekroczy \(e+n\), gdyż możemy wykonać co najwyżej \(n\) operacji wzięcia jednej karteczki z góry, zanim nie wyczyścimy szpikulca.

W takim razie nasza tablica potrzebuje \(O(n(n+e))\) stanów. Ponieważ w pierwszym podzadaniu mieliśmy zagwarantowane, że zarówno liczba karteczek na szpikulcu \(n\), jak i początkowa energia kucharza \(e\), są ograniczone przez \(1000\), to taka tablica dla tego podzadania mieści się w limicie pamięci.

Przedstawiony algorytm działa w złożoności czasowej \(O(n(n+e))\) i wykorzystuje pamięć tego samego rzędu. Jego zastosowanie pozwalało na uzyskanie 12 punktów.

Ograniczenie drugiego wymiaru

Zauważmy, że jednostki energii wydajemy tylko przy wykonywaniu operacji typu \(polowa()\). Jednak każde wykonanie operacji \(polowa()\) zmniejsza nam liczbę karteczek niemal dwukrotnie! Oznacza to, że takich operacji wykonamy co najwyżej \(\lceil \log n \rceil\) i nigdy nie skorzystamy z większej ilości energii. Tak więc drugi wymiar w naszym programowaniu dynamicznym możemy ograniczyć przez \(\lceil \log n \rceil\).

Pozwala nam to na osiągnięcie algorytmu o złożoności czasowej i pamięciowej \(O(n \log n)\). Niestety, jest to nadal za dużo pamięci, żeby pokonać wszystkie podzadania. Rozwiązanie oparte na powyższej obserwacji otrzymywało \(20\) punktów.

Rozwiązanie wzorcowe

Rozwiązanie wzorcowe będzie oparte na takim samym algorytmie dynamicznym.

Drugiego wymiaru – tego opisującego ilość energii – już bardziej nie ograniczymy, ale być może nie musimy trzymać tablicy \(dp[j]\) dla wszystkich \(j\) jednocześnie. Jakie stany musimy mieć w pamięci, żeby policzyć \(dp[i]\)? Na pewno wszystkie z \(dp[i-1]\), żeby rozważyć wykonanie pojedynczego zamówienia. Przyda nam się też \(dp[i-2]\), aby rozważyć wzięcie dwóch zamówień z góry naraz. Musimy jeszcze trzymać \(dp[\lceil \frac{i}{2} \rceil]\).

Czego natomiast potrzebujemy, żeby policzyć \(dp[i+1]\), mając policzone \(dp[i]\)? Na pewno dwóch stanów: \(dp[i]\) oraz \(dp[i-1]\), ale mamy je na szczęście zapisane. Możemy natomiast zwolnić stan \(dp[i-2]\). Więc te stany (które nazwiemy pierwszą warstwą) udało nam się „przesunąć” o jeden.

Jeśli \(\lceil \frac{i+1}{2} \rceil = \lceil \frac{i}{2} \rceil\), to mamy też zapisany stan \(dp[\lceil \frac{i+1}{2} \rceil]\), więc posiadamy wszystkie informacje potrzebne do wyliczenia \(dp[i+1]\).

Komplikacja natomiast pojawia się, kiedy \(i\) jest parzyste. Wówczas, aby policzyć \(dp[i+1]\) potrzebujemy stanu \(dp[\frac{i}{2}+1]\). Żeby go poznać, to poza \(dp[\frac{i}{2}]\) musieliśmy jeszcze mieć informację o \(dp[\frac{i}{2}-1]\). Te stany rzędu \(\frac{i}{2}\) nazwiemy drugą warstwą. Po policzeniu \(dp[\frac{i}{2}+1]\), nie potrzebujemy już \(dp[\frac{i}{2}-1]\), więc druga warstwa zawsze zawiera nie więcej niż dwa elementy.

Do policzenia \(dp[\frac{i}{2}+1]\) potrzebujemy jeszcze trzeciej warstwy, w której będziemy trzymać \(dp[\lceil \frac{i}{4}] \rceil\). Dzięki niemu drugą warstwę możemy przesuwać w sposób analogiczny do przesuwania pierwszej warstwy, dopóki \(i\) nie jest podzielne przez 4. Dla \(i\) podzielnego przez 4, \(\lceil \frac{i+1}{4} \rceil = \frac{i}{4}+1 \neq \frac{i}{4} = \lceil \frac{i}{4} \rceil\) , więc nie wystarcza nam trzymanie \(dp[ \frac{i}{4} ]\), gdyż żeby policzyć \(dp[\frac{i}{4} +1]\) musieliśmy trzymać w trzeciej warstwie jeszcze jeden stan: \(dp[\frac{i}{4}-1]\) (który teraz będziemy mogli zwolnić, utrzymując, że w warstwie są nie więcej niż dwa elementy) oraz mieć czwartą warstwę ze stanem \(dp[\lceil \frac{i}{8} \rceil]\).

Jednak w przypadku \(i\) podzielnego przez \(8\), do policzenia tego stanu będziemy potrzebować stanu \(dp[ \frac{i}{8} -1]\) oraz piątej warstwy rzędu \(\frac{i}{16}\). Powtarza się to dla następnych warstw, każda kolejna odpowiada liczbie kartek rzędu dwa razy mniejszego, aż do warstwy, zawierającej tablicę dynamiczną dla jednej kartki na szpikulcu.

Widać więc, że takich warstw będzie niewiele: \(O(\log n)\), a każda z nich w określonym momencie ma co najwyżej dwa elementy: dwie tablice programowania dynamicznego – każda wielkości \(O(\log n)\), na mocy ograniczenia na potrzebną ilość energii. Tak więc złożoność pamięciowa naszego rozwiązania wynosi \(O(\log^2 n)\).

Jaka będzie złożoność czasowa takiego podejścia? Każde przesunięcie robimy w czasie logarytmicznym, gdyż tyle stanów ma tablica programowania dynamicznego dla określonej liczby kartek. Ile przesunięć wykonamy? Zaskakująco mało! Zauważmy, że pierwszą warstwę przesuniemy około \(n\) razy, drugą około \(\frac{n}{2}\) razy (bo robimy to tylko, gdy liczba kartek jest parzysta), trzecią około \(\frac{n}{4}\) razy itd. Tak więc sumarycznie przesunięć zrobimy \(n+\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\dots = O(n)\). Skoro każde przesunięcie kosztuje nas czas \(O(\log n)\), to złożoność czasowa naszego algorytmu wynosić będzie \(O(n \log n)\).

Program implementujący powyższe rozwiązanie mógł już liczyć na otrzymanie 100 punktów.