Beetle

09.02.2011 - Anna Piekarska
TrudnośćTrudność

W 2009 roku udało mi się dostać do reprezentacji Polski na Bałtycką Olimpiadę Informatyczną. Jak większość tego typu imprez, także i ta co roku odbywa się w innym miejscu. Tym razem był to Sztokholm, a (prawie) równolegle do zawodów odywały finały ACM ICPC (a co za tym idzie, w programie było zdecydowanie więcej atrakcji niż w innych latach!). Zadaniem, które sprawiło mi najwięcej radości (chociażby dlatego, że udało mi się je rozwiązać pomimo tego, że początkowo wydawało mi się dość trudne), było beetle. Jest na tyle ciekawe, że chciałabym je Wam przedstawić.

Czego od nas chcą w tym zadaniu?

Danych jest $ n $ punktów na prostej osi. Startujemy wędrówkę w punkcie 0 i poruszamy się po osi w prawo lub w lewo. Jeśli napotkamy któryś z punktów, możemy go "wypić", czyli dodać do wyniku aktualną wartość punktu oraz usunąć punkt. Aktualna wartość kropli to $ m-t $ jeśli $ m > t $ lub 0 jeśli $ m\leq t $, gdzie $ t $ jest czasem jaki, który upłynął od początku wędrówki. W zadaniu proszą nas o policzenie maksymalnej ilości wody jaką możemy wypić.

Kilka bardziej lub mniej oczywistych spostrzeżeń na dobry początek

Jeśli w optymalnym rozwiązaniu w pewnym momencie pewne dwie krople $ x $ i $ y $ zostały już wypite, to wszystkie krople pomiędzy $ x $ a $ y $ również.

Dowód: Jeśli $ x $ oraz $ y $ zostały już wypite, to chrząszcz przebył trasę pomiędzy nimi. Nie opłaca się zostawiać niewypitej kropli, ponieważ jej wartość nigdy nie będzie wyższa, zaś wypicie kropli nie zajmuje nam czasu. Tak więc przechodząc wypijemy wszystkie.

Jeśli kropla najbardziej wysunięta na lewo spośród wypitych ma numer $ x $, zaś najbardziej wysunięta na prawo ma numer $ y $, to następną wypitą kroplą będzie kropla numer $ x-1 $ lub $ y+1 $ (lub nie będzie to żadna z nich i chrząszcz zakończy swój spacer).

Dowód: A która inna?

Rozwiązanie nieco zbyt wolne

Jak w każdym zadaniu, także i w tym warto zacząć od czegoś co działa i daje poprawne wyniki, aczkolwiek być może jeszcze nie tak szybko jak oczekują autorzy zadania. Spróbujmy rozwiązać zadanie za pomocą programowania dynamicznego!

Zauważmy, że z drugiego spostrzeżenia wynika, że do zapamiętania już wypitych kropli wystarczą nam dwie liczby nie większe niż $ n $, oznaczające odpowiednio początek i koniec sekwencji już wypitych kropli. Dołożenie jednej wartości logicznej pozwoli nam stwierdzić gdzie aktualnie znajduje się chrząszcz - jedynymi możliwościami są oba końce przedziału.

Wiemy już zatem gdzie jesteśmy w tym momencie i które punkty już odwiedziliśmy. Dołożenie wartości określającej czas, który upłynął od początku wędrówki, pozwoli nam w sposób wystarczający opisywać aktualną sytuację. Nie interesuje nas co się działo wcześniej. Ważna jest tylko obecna sytuacja i aktualnie osiągany wynik. W takim razie naszych stanów w programowaniu dynamicznym będzie $ n^2*2*m $.

Z każdego stanu możemy przejść do następnego w czasie stałym - wybrać jedną z trzech opcji - wypić kroplę następną w lewo, następną w prawo bądź zakończyć podróż. Można zapisać to tak:

$$t_1 = dp[left-1][right[1][time+dist(cur, left-1)]$$
$$t_2 = dp[left][right+1][0][time+dist(cur, right+1)]$$
$$dp[left][right][isleft][time] = m-time + max(t_1, t_2)$$
gdzie $ dist(a,b) = |a-b| $ (odległość dwóch punktów) i $ cur $ jest aktualną pozycją chrząszcza (czyli $ left $ lub $ right $ w zależności od $ isleft $)

Niestety, taka złożoność nas nie satysfakcjonuje. W pesymistycznym przypadku mamy $ 300^2*2*1000000 = 18*10^{10} $ operacji czyli dużo za dużo.

I co dalej?

Programowanie dynamiczne nasuwa się od razu - bo co innego? Poprzedni algorytm wygląda na dość ciekawą podstawę do ładnego i szybkiego rozwiązania. Tylko jak właściwie powinno ono wyglądać?

Rozwiązanie znalezione przez poprzedni algorytm można przedstawić na wykresie położenia $ x(t) $ od czasu $ t $ i zaznaczyć punkty oznaczające kolejne krople wody. Wtedy wynikiem algorytmu będzie $ \sum_{i=1}^{k} m-t(i) $, gdzie $ k $ jest liczbą odwiedzonych kropli, a $ t(i) $ czasem odwiedzenia $ i $-tej kropli. Spróbujmy przekształcić ten wzór. Dla uproszczenia załóżmy $ t(0)=0 $ (możemy dołożyć wyimaginowany punkt i odjąć od wyniku $ m $).

$$\sum_{i=1}^k m-t(i) = km - \sum_{i=1}^{k} t(i) = km - \sum_{i=1}^{k} (k-i+1)(t(i)-t(i-1) = $$
$$ = km - \sum_{i=1}^{k} (k-i+1)|x(i)-x(i-1)|$$
Pierwsze przejście jest oczywiste, drugie jest przekształceniem wyrażenia, trzecie wynika z prędkości chrząszcza.

Na podstawie tego wzoru łatwo zauważyć, że po wybraniu liczby kropli, które zamierzamy wypić, nasz wynik prawie przestaje zależeć od $ m $ oraz czasu - wystarczy dodać do wyniku $ km $ i zapomnieć o $ m $.

W nowym rozwiązaniu dynamicznym będziemy wciąż pamiętać początek i koniec przedziału już odwiedzonych punktów oraz flagę mówiącą po której stronie aktualnie jesteśmy. Tym razem jednak ostatnią wartością będzie liczba kropli, które planujemy jeszcze wypić.

Zależność dynamiczną możemy opisać wzorem:

$$t_1 = dist(cur, left-1) * k + dp[left-1][right][1][k-1]$$
$$t_2 = dist(cur, right+1) * k + dp[left][right+1][0][k-1]$$
$$dp[left][right][isleft][k] = min(t_1, t_2)$$
gdzie $ cur $ i $ dist $ są zdefiniowane jak w poprzednim paragrafie.

Daje to złożoność $ O(n^3) $ czyli w zupełności wystarczającą przy tych limitach.

Redakcja tekstu: Paweł Gawrychowski
4
Twoja ocena: Brak Ocena: 4 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com