Omówienie zadania Wagony (II etap XXX OI)

Treść zadania

W zadaniu mamy dany jednowymiarowy tor, na którym stoi \(n\) niepołączonych ze sobą wagonów. Możemy wykonywać ruchy polegające na połączeniu dwóch grup połączonych wagonów stojących obok siebie, pod warunkiem, że różnica ich długości nie przekracza podanej nam na wejściu liczby \(d\). Każda taka operacja ma jednak koszt, dany funkcją \(f(w, v) = (aw + bv)\ \text{mod}\ 1001\), gdzie \(a, b\) to stałe podane nam na wejściu, a \(w, v\) to kolejno długości lewej i prawej grupy wagonów. Naszym celem jest połączenie wszystkich \(n\) wagonów w jedną grupę, minimalizując jednocześnie sumaryczny koszt operacji.
Zauważmy, że funkcji opisującej koszt brakuje jakichkolwiek regularności, które pozwoliłyby nam zastosować standardowe techniki optymalizacyjne. W związku z tym rozwiązanie nie będzie korzystać z żadnych jej własności.

Rozwiązanie \(n \leq 10^5\)

W przypadku, gdy \(n\) jest relatywnie małe, możemy manualnie obliczyć najlepsze rozwiązanie za pomocą programowania dynamicznego. Niech \(dp[x]\) oznacza najmniejszy możliwy koszt uzyskania połączonego ciągu wagonów o długości \(x\) przy założeniu, że żadne dwa wagony nie są na początku połączone. W celu obliczenia wartości \(dp[x]\), czyli kosztu uzyskania połączonej grupy wagonów o długości \(x\), musimy rozpatrzeć wszystkie możliwe długości dwóch grup, które po połączeniu dadzą nam grupę o długości \(x\). Niech \(i\) będzie oznaczać długość lewej grupy, a \(j\) prawej. Przede wszystkim, aby wynikiem połączenia tych dwóch grup była grupa o długości \(x\), musi zachodzić \(i+j=x\). Zauważmy także, że grupy wagonów mogą mieć jedynie długości dodatnie, zatem \(0 < i, j < x\). Z treści zadania wiemy, że można łączyć tylko grupy, których różnica długości wynosi co najwyżej \(d\), czyli trzeba zapisać także warunek \(|i-j| \leq d\). Dla \((i, j)\) spełniających warunki, koszt uzyskania grupy o długości \(x\) będzie równy sumie kosztów uzyskania grup długości \(i\) oraz \(j\), a także kosztowi połączenia tych dwóch grup w jedną.
Zatem będziemy rozważać wszystkie pary \((i, j)\) takie, że \(0 < i, j < x \), \(i + j = x\), oraz \(|i - j| \leq d\). Minimalny koszt uzyskania grupy wagonów o długości \(x\) będzie po prostu minimum z wartości postaci \(dp[i] + dp[j] + f(i, j)\) dla \((i, j)\) spełniających warunki. Można jednak zauważyć, że jeśli za każdym razem spróbujemy przejrzeć wszystkie wartości \(i\) mniejsze od \(x\) oraz odpowiadające im \(j = x - i\), to otrzymamy złożoność \(O(n^2)\). Możemy jednak natychmiast odrzucić niektóre \(i\). Z równań \(|i - j| \leq d\) oraz \(j = x - i\) możemy zapisać \(|2i - x|\leq d\), czyli \(x - d \leq 2i \leq x + d\). Zatem \(\frac{x - d}{2} \leq i\leq\frac{x + d}{2}\), czyli zostaje nam \(O(d)\) kandydatów na \(i\), których musimy rozpatrzeć dla danego \(x\).

Takie rozwiązanie ma złożoność \(O(n\cdot d)\) i otrzymuje \(21\) punktów

Rozwiązanie wzorcowe

Aby uzyskać wzorcowe rozwiązanie należy zastanowić się, które ze stanów są nam tak naprawdę potrzebne do obliczenia \(dp[n]\). W tym celu spojrzymy na programowanie dynamiczne od końca, zaczynając od \(dp[n]\), które jest naszym wynikiem, więc na pewno musimy je obliczyć. Wiemy, że \(dp[n]\) jest bezpośrednio zależne od wartości \(dp\) na przedziale \(\left[\frac{n-d}{2}, \frac{n+d}{2}\right]\). Można zauważyć, że wszystkie stany na przedziale \(\left(\frac{n+d}{2}, n\right)\) są nam zupełnie niepotrzebne. Nie mogą zostać użyte ani do bezpośredniego policzenia \(dp[n]\), ani żadnych innych stanów, od których ono zależy, ponieważ żaden stan nie zależy od stanów o numerach większych od siebie (grupy wagonów możemy jedynie łączyć, nie możemy ich rozbijać na mniejsze). Chcemy teraz policzyć stany na przedziale \(\left[\frac{n-d}{2}, \frac{n+d}{2}\right]\). Można zauważyć, że zbiór stanów, od których zależą te stany, także będzie spójnym przedziałem. Jego lewy kraniec będzie po prostu lewym krańcem stanu \(dp[\frac{n-d}{2}]\), czyli tego o najmniejszym numerze z poprzedniej warstwy. Analogicznie można obliczyć prawy kraniec dla ostatniego stanu z poprzedniej warstwy. Uzyskujemy w ten sposób spójny przedział \(\left[\frac{n}{4} -\frac{d}{4} - \frac{d}{2}, \frac{n}{4} +\frac{d}{4}+ \frac{d}{2}\right]\). Możemy kontynuować takie „schodzenie” warstwami do czasu, aż nie dotrzemy do trywialnego stanu \(dp[1]\), który wynosi po prostu \(0\).

Poziomów takich będzie \(O(\log(n))\), ponieważ za każdym razem środkiem przedziału jest \(n\) podzielone przez coraz większą potęgę liczby \(2\). Na każdym poziomie będzie \(O(d)\) stanów, ponieważ lewy i prawy kraniec są odległe od siebie o pewną sumę szeregu geometrycznego o ilorazie równym \(2\). Taki szereg można nietrudno ograniczyć przez \(2\cdot d\). Mamy zatem \(O(d\cdot\log(n))\) stanów do policzenia. Należy jednak pamiętać, że obliczanie każdego stanu zajmuje \(O(d)\) czasu.
Zatem złożoność takiego rozwiązania to \(O(d^2\log(n))\)

Implementacja

Aby sprawnie zaimplementować takie rozwiązanie, użyjemy rekurencji. Poczynając od stanu \(n\) będziemy poruszać się po drzewie niezbędnych stanów w sposób podobny do tego, w jaki robi to algorytm DFS. Kiedy wchodzimy do „wierzchołka” \(k\), czyli chcemy policzyć \(dp[k]\), wywołujemy rekurencyjnie funkcję liczącą wartość stanów dla wartości na przedziale \(\left[\frac{k - d}{2}, \frac{k + d}{2}\right]\). Dopiero kiedy mamy policzone wszystkie te stany, możemy obliczyć wartość \(dp[k]\). Taki algorytm unika liczenia niepotrzebnych stanów, jednakże potrafi bardzo wiele razy liczyć te same stany, co negatywnie wpływa na złożoność. W celu uniknięcia tego problemu użyjemy haszmapy, na której będziemy trzymać wartości wcześniej obliczonych stanów. Wtedy, za każdym razem, kiedy trafimy na już obliczony stan, możemy po prostu wziąć jego wartość z tablicy, zamiast rekurencyjnie liczyć go na nowo. Po zastosowaniu takiej optymalizacji, rozwiązanie będzie już miało docelową złożoność \(O(d^2\log(n))\).

Wyniki w niektórych testach mogą być bardzo duże, wystarczająco aby przekroczyć maksymalną wartość zmiennej typu \(\verb|long long|\). Aby uzyskać \(100\) punktów wymagane jest użycie zmiennej typu \(\verb|unsigned long long|\). Rozwiązanie, które używa zwyczajnej zmiennej typu \(\verb|long long|\) otrzyma maksymalnie \(90\) punktów.