Omówienie zadania Armia klonów (II etap XXIX OI)

Wykonywane w zadaniu operacje wygodnie nam będzie podzielić na bloki, z których każdy zaczyna się pojedynczą operacją skanowania, po której następują operacje kopiowania. Poprawność pierwszego bloku wynika z tego, że cały proces musimy zacząć od operacji skanowania pierwszego robota. Jasne jest również, że w każdym bloku będziemy mieli co najmniej jedną operację kopiowania, ponieważ nie opłaca nam się wykonać dwóch operacji skanowania z rzędu. Ale to, ile dokładnie bloków opłaca nam się stworzyć i ile razy operacja kopiowania będzie używana w każdym bloku, stanowi właśnie trudność zadania.

Podzadania 2 i 3 (programowanie dynamiczne)

Standardowym pomysłem w przypadku takich zadań optymalizacyjnych jest próba zastosowania metody programowania dynamicznego. Spróbujmy wyznaczyć jednowymiarową tabelkę \(dp\), w której \(dp[k]\) będzie oznaczać minimalny czas stworzenia \(k\) robotów. Załóżmy, że obliczyliśmy już wartość \(dp[k]\) i zastanówmy się, do jakich stanów możemy przejść ze stanu posiadania dokładnie \(k\) robotów przy pomocy operacji zawartych w jednym bloku. Czyli zaczynając od \(k\) robotów, najpierw wykonujemy operację skanowania o koszcie \(a\), a następnie jedną lub więcej operacji kopiowania, każda o koszcie \(b\). Wobec tego możemy przejść do stanu \(2k\) krawędzią o koszcie \(a + b\), do stanu \(3k\) krawędzią o koszcie \(a + 2b\) i w ogólności do stanu \(i \cdot k\) krawędzią o koszcie \(a + (i - 1) \cdot b\).

Algorytm wypełnienia tabelki może więc wyglądać następująco. Na początku inicjujemy jej komórki na \(+\infty\), oprócz \(dp[1] = 0\), ponieważ czas stworzenia jednego robota, którego już mamy, jest zerowy. Następnie iterujemy się kolejno po coraz większych licznościach armii robotów. Gdy rozpatrujemy liczność \(k\), uaktualniamy wartości \(dp[i\cdot k]\) na podstawie \(dp[k]\): \[dp[ik] = \min(dp[ik],\ dp[k] + a + (i-1)b) \quad\quad\textrm{dla } i\geq 2.\] Tę wewnętrzną pętlę po \(i\) oczywiście przerywamy w momencie dojścia do pierwszej komórki większej niż \(n\). Odpowiedzią do zadania będzie minimum z wartości \(dp\) dla komórek większych od \(n\).

Warto zauważyć, że jeżeli potraktujemy stany w naszym programowaniu dynamicznym jako wierzchołki pewnego grafu, a przejścia pomiędzy stanami jako skierowane, ważone krawędzie, to nasz algorytm to nic innego jak algorytm Dijkstry szukania najkrótszej ścieżki w tym grafie. Ze szczególnej postaci tego grafu wynika bardzo prosta kolejność analizowania wierzchołków w zewnętrznej pętli, natomiast wewnętrzna pętla to nic innego jak relaksacja krawędzi.

A jaka jest złożoność czasowa algorytmu? Wydawałoby się, że ponieważ mamy dwie zagnieżdżone pętle, będzie to \(O(n^2)\). Ale zauważmy, że dla ustalonej wartości \(k\) wewnętrzna pętla przechodzi jedynie po wielokrotnościach \(k\), kończąc na pierwszej wielokrotności większej niż \(n\). Wobec tego wykona ona jedynie \(\frac{n}{k}\) obrotów. Więc sumując wszystkie obroty pętli wewnętrznych, dostaniemy sumę \(\frac{n}{1} + \frac{n}{2} + \ldots + \frac{n}{n}\), co asymptotycznie jest równe \(O(n \log n)\). Dzięki czemu ten algorytm poradzi sobie zarówno z drugim, jak i z trzecim podzadaniem.

Drugie podzadanie było przewidziane dla mniej wydajnych algorytmów korzystających z programowania dynamicznego, w których korzystamy na przykład z dwuwymiarowych stanów, biorących pod uwagę zarówno liczbę gotowych robotów, jak i zawartość pamięci drukarki.

Pełne rozwiązanie

Oznaczmy przez \(x_i\) liczbę operacji wykonywanych w jednym bloku i niech \(m\) to będzie liczba wszystkich bloków. Koszt czasowy wykonania wszystkich operacji to będzie \(m \cdot a\) na wykonanie wszystkich skanowań plus \((x_1+x_2+\ldots+x_m-m) \cdot b\) na wykonanie wszystkich kopiowań. Ponieważ każdy blok wielkości \(x_i\) zwiększa nam liczbę robotów w armii razy \(x_i\), tak więc ostateczna liczność armii to będzie \(x_1\cdot x_2\cdots x_m\). Teraz chcielibyśmy znaleźć takie wartości \(x_i\), które spowodują, że ten iloczyn będzie większy od \(n\), a koszt jak najmniejszy.

Zobaczmy jednak, że jeżeli ustalimy liczbę bloków, to wszystko w koszcie jest stałe oprócz sumy \(x_1+x_2+\ldots+x_m\). Innymi słowy, przy ustalonej wartości \(m\) chcielibyśmy znaleźć taki iloczyn \(x_i\), który jest większy od \(n\), przy jednoczesnej minimalizacji sumy tych \(x_i\). I tutaj obserwacja jest taka, że stać nas na przejrzenie wszystkich sensownych wartości \(m\). Zastanówmy się bowiem, ile maksymalnie bloków możemy potrzebować. Jeżeli rozważymy najkrótsze możliwe bloki o długości \(2\), czyli wszystkie wartości \(x_i\) będą równe \(2\), to wtedy wystarczy, że \(2^m\) przekroczy wartość \(n\). A to oznacza, że \(m\) jest ograniczone przez \(\log(n + 1)\). Możemy zatem przeiterować się po wszystkich możliwych wartościach \(m\), których będzie \(O(\log n)\).

Na rozgrzewkę rozważmy przypadek \(m = 2\), czyli chcemy znaleźć dwie liczby naturalne \(x_1\), \(x_2\), dla których \(x_1 x_2 > n\), natomiast \(x_1+x_2\) jest możliwie mała. Ponieważ w dalszych rozważaniach będzie nam wygodniej używać nieostrej nierówności, więc zapiszmy \(x_1 x_2 \geq n+1 = N\). Gdyby wartości \(x_1\) i \(x_2\) mogłyby być rzeczywiste, to wtedy do tego problemu optymalizacji moglibyśmy zastosować metody rachunku różniczkowego. Możemy bowiem wtedy zapisać, że \(x_2 = \frac{N}{x_1}\), a minimalizacja sumy to minimalizacja funkcji \(f(x_1) = x_1 + \frac{N}{x_1}\). W celu znalezienia ekstremum funkcji przyrównujemy jej pochodną do zera, czyli \(f'(x_1) = 1 - \frac{N}{x_1^2} = 0\). Z tego dostajemy rozwiązanie, że \(x_1 = \sqrt{N}\), z czego wynika, że również \(x_2 = \sqrt{N}\). Ten wynik nie jest zaskakujący. Geometrycznie oznacza on bowiem, że wśród prostokątów o ustalonym polu powierzchni \(N\) najmniejszy obwód ma kwadrat o boku \(\sqrt{N}\).

Dla większej liczby bloków intuicyjnie spodziewamy się, że najlepszy wynik w liczbach rzeczywistych uzyskamy biorąc wartości \(x_i\) równe sobie, czyli równe \(\sqrt[m]{N}\). Jednak w naszym zadaniu wartości \(x_i\) muszą być całkowite. Znowu intuicja powoduje, że chyba najlepiej byłoby, gdyby były zbliżone do \(\sqrt[m]{N}\). Zatem część z nich powinna być równa temu pierwiastkowi zaokrąglonemu w dół i tę wartość oznaczmy przez \(S\), a część pierwiastkowi zaokrąglonemu w górę i będzie to \(S + 1\). W szczególności wynika to, że wartości \(x_i\) nie mogą różnić się od siebie o więcej niż \(1\).

Okazuje się, że rzeczywiście tak musi być. Załóżmy bowiem przez sprzeczność, że mamy jakieś wartości, które różnią się o więcej niż \(1\), czyli powiedzmy, że mamy jakieś \(x_i > x_j + 1\). Zobaczmy, jak zmieni się iloczyn, jeżeli wartość \(x_i\) zmniejszymy o \(1\), natomiast wartość \(x_j\) zwiększymy o \(1\): \[(x_i-1)(x_j+1) = x_i x_j + x_i - (x_j+1) > x_i x_j.\] Zauważmy zatem, że operacja zmniejszenia długości bloku \(x_i\) i zwiększenia długości bloku \(x_j\), mająca w zamierzeniu wyrównanie ich długości, spowodowała zwiększenie iloczynu przy jednoczesnym niezmienieniu sumy wartości \(x_i\). Dopóki zatem mamy jakieś wartości w ciągu \(x_i\), które różnią się o więcej niż \(1\), możemy wykonać tę operację bez pogarszania rozwiązania. A ponieważ mamy skończoną liczbę bloków, nie będziemy mogli poprawiać ich długości w nieskończoność. Wobec tego w końcu uzyskamy sytuację, kiedy rzeczywiście ich długości będą równe albo \(S\), albo \(S + 1\).

Ale jak wybrać, które z wartości \(x\) będą równe \(S\), a które \(S + 1\)? Jasne jest, że kolejność \(x_i\) nie ma znaczenia, wobec tego istotne jest jedynie, ile z wartości \(x_i\) będzie równe \(S\) i oznaczmy tę wartość przez \(k\). Wtedy pozostałe \(m - k\) wartości będzie musiało być równe \(S + 1\). Ponieważ \(k \leq m \leq \log n\), również możemy przeiterować się po wszystkich możliwościach wyboru \(k\).

Dla każdego takiego wyboru liczymy \(S^k \cdot (S + 1)^{m - k}\) i sprawdzamy, czy ta wartość jest większa lub równa \(N\). Jeśli tak, to bierzemy minimum z dotychczas obliczonego najmniejszego kosztu oraz z kosztu aktualnego iloczynu, czyli \(ma + (sm-k)b\).

Ostatecznie złożoność czasowa tego rozwiązania będzie wynosić \(O(\log^3 n)\), ponieważ najpierw musimy przeiterować się po wszystkich wyborach wartości \(m\), potem po wszystkich wyborach wartości \(k\), a następnie obliczyć iloczyn.

Na koniec jeszcze jedna uwaga implementacyjna. Należy uważać na przepełnienia, które mogą wystąpić podczas wykonywania mnożenia. Warto więc sprawdzić wzory, zwłaszcza w przypadku \(m = 1\), ale gdyby był on problematyczny, można go rozpatrzyć osobno.