Omówienie zadania Gwiazdy (II etap XXVI OI)

Dane jest \(n\) gwiazd na linii prostej, ponumerowanych od \(1\) do \(n\). Zaczynamy w gwieździe \(s\) i chcemy wykonać \(n-1\) skoków, by odwiedzić wszystkie gwiazdy; \(i\)-ty skok może być w lewo (i płacimy wtedy koszt \(l_i\)) lub w prawo (i płacimy \(r_i\)). Należy znaleźć ciąg odwiedzeń gwiazd minimalizujący sumę kosztów skoków.

Podzadanie 1

Najprostsze rozwiązanie sprawdza wszystkie możliwe permutacje odwiedzonych gwiazd, których jest \((n - 1)!\) i działa w złożoności czasowej \(O(n!)\).

Podzadanie 2

Można też skonstruować programowanie dynamiczne, którego stan definiowany jest przez zbiór odwiedzonych gwiazd oraz obecną gwiazdę, jest ich więc \(O(2^n n)\). Wynik dla konkretnego stanu da się obliczyć w czasie liniowym od liczby gwiazd, rozpatrując zbiór gwiazd pomniejszony o teraz odwiedzoną. Rozwiązanie to działa w złożoności czasowej \(O(2^n n^2)\).

Podzadanie 3

Szybko nasuwa się też rozwiązanie wielomianowe o złożoności \(O(n^3)\). Gwiazdy są nierozróżnialne, jedyne, co ogranicza nasze skoki, to liczba nieodwiedzonych gwiazd po lewej i po prawej stronie aktualnej gwiazdy. Mamy więc \(O(n^2)\) stanów i do każdego z nich możemy dostać się z dowolnego innego stanu o sumie liczb gwiazd po obu stronach większej o jeden, a takich stanów jest \(O(n)\).

Podzadanie 4

Poprzednie rozwiązanie da się jeszcze ulepszyć – załóżmy, że mamy uzupełnione wszystkie stany, w których suma liczb gwiazd po obu stronach jest równa \(i + 1\). Niech stan \((l, p)\) oznacza taki, w którym po lewej mamy \(l\) nieodwiedzonych gwiazd, a po prawej \(p\) oraz \(l + p = i\). Do danego stanu \((l, p)\) możemy dostać się, skacząc w prawo z dowolnego stanu \((l - x, p + x + 1)\), gdzie \(x \leq l\). Analogicznie, możemy się tam dostać, skacząc w lewo z dowolnego stanu \((l + x + 1, p - x)\), gdzie \(x \leq p\). W obu przypadkach interesuje nas stan najlepszy, czyli o najmniejszym koszcie.

Możemy więc skonstruować rozwiązanie, które dla danego poziomu \(i\) uzupełni wszystkie stany na tym poziomie w czasie liniowym. Zastosujemy dwa przejścia, od \((0, i)\) do \((i, 0)\), a później w drugą stronę. W pierwszym będziemy trzymać w każdym kroku najlepszy możliwy stan, z którego mogliśmy skoczyć w prawo do naszego stanu, a w drugim analogicznie dla skoku w lewo. To rozwiązanie działa w czasie \(O(n^2)\).

Podzadanie 5

Ponieważ \(l_i \leq r_i\) dla każdego skoku, więc najchętniej zrobilibyśmy jedynie skoki w lewo. To jest możliwe, jeśli \(s=n\). Dla \(s\neq n\) musimy zrobić jakiś skok w prawo (jako jeden z \(s\) pierwszych skoków), ale jeden skok w prawo wystarczy. Zatem wybieramy taki, który minimalizuje \(r_i - l_i\) dla \(i \leq s\).

Czas działania to \(O(n)\).

Podzadanie 6

Skoro koszt całkowity wynosi 0 i dla każdego skoku albo \(l_i=0\), albo \(r_i=0\), to dokładnie wiemy, w których kierunkach musimy skakać (zawsze skokiem o koszcie 0).

Dzielimy skoki na bloki o tych samych kierunkach. Będziemy zachowywać niezmiennik, że zbiór nieodwiedzonych gwiazd stanowi spójny przedział (pomijamy przy tym początkową gwiazdę \(s\)). Jeśli mamy wykonać \(a\) skoków w lewo, to po lewo od aktualnej gwiazdy musi być co najmniej \(a\) gwiazd. Skaczemy po kolei do \(a\)-tej, \((a-1)\)-szej, …, drugiej, pierwszej nieodwiedzonej gwiazdy. Jeśli mamy wykonać \(b\) skoków w prawo, to odwiedzamy po kolei gwiazdy z sufiksu długości \(b\).

Złożoność czasowa również \(O(n)\).

Podzadanie 7

Jeśli \(s=1\), to pierwszy skok będziemy musieli wykonać w prawo. Ale później będziemy już mogli zawsze wybierać skok w kierunku mniejszego kosztu (aby zapłacić \(\min(l_i,r_i)\)), metodą jak w poprzednim podzadaniu. Złożoność czasowa \(O(n)\).

Pełne rozwiązanie

Dzielimy skoki na bloki o tych samych kierunkach, wybierając zawsze skok do mniejszego kosztu. Dla uproszczenia analizy załóżmy, że pierwszy blok skoków jest w lewo. Jeśli jego długość jest mniejsza niż \(s\), to wykonujemy wszystkie skoki jak w podzadaniu 6. W przeciwnym wypadku jeden z \(s\) pierwszych skoków musimy zamienić na skok w prawo (jak w podzadaniu 5 – wybieramy ten minimalizujący \(r_i - l_i\) dla \(i \leq s\)).

Przypadek pierwszego bloku skoków w prawo jest symetryczny. Czas działania to \(O(n)\).