Metro

Tym razem chciałbym Wam przedstawić zadanie, które pojawiło się ledwie kilka tygodni temu jako problem B na moskiewskich eliminacjach do ACM ICPC Northeastern European Programming Contest 2012. Cały zestaw można zobaczyć tu, warto też zajrzeć na ranking. W rzeczonym rankingu widać, że choć zadanie B cieszyło się wśród uczestników dość dużą popularnością, to jednak nikomu nie udało się go rozwiązać. Sugeruje to (słusznie), że jest ono dość podstępne. Przez chwilę chciałem nawet napisać, że w najlepszym rosyjskim stylu, przy czym jest to, być może wbrew pozorom, komplement. W każdym bądź razie przed dalszą lekturą zachęcam do chwili zastanowienia.

Naszym celem jest zaplanowanie zakupu biletów, z których będziemy następnie korzystać w trakcie n kolejnych dni. Wiemy, że i-tego dnia powinniśmy dysponować a_i \in \{0,1,2\} różnymi biletami. Jeden bilet może być wykorzystany podczas dowolnie wybranych A dni należących do pewnego przedziału długości B, czyli S\subseteq \{i,i+1,\ldots,i+B-1\}, |S|=A. Będziemy mówić, że jest to przedział aktywności danego biletu, a zbiór S to dni, w których został on użyty. Najbardziej ucieszy nas oczywiście znalezienie planu, który minimalizuje liczbę potrzebnych biletów.

Zastanówmy się najpierw nad prostszą sytuacją, w której a_i \in \{0,1\}. Dość naturalne wydaje się, że nie ma sensu mieć w jakimkolwiek momencie więcej niż jednego biletu, który mógłby być jeszcze użyty. Czyli jedziemy na tym samym bilecie tak długo jak jest to możliwe, a potem kupujemy (bo, rzecz jasna, jesteśmy uczciwi) kolejny. Przy czym z zakupem czekamy oczywiście do kolejnego i, dla którego a_i > 0.

No dobrze, ale w zadaniu może się przecież zdarzyć, że a_i = 2. Co wtedy? Mogłoby się wydawać, że w takiej sytuacji nie ma sensu mieć w jakimkolwiek momencie więcej niż dwóch biletów, które mogłyby być jeszcze użyte. Jest to o tyle kuszące, że zakładając prawdziwość takiego stwierdzenia dość łatwo skonstruować rozwiązanie dynamiczne o czasie działania \mathcal{O}(n A^2 B^2). Niestety, wcale nie jest ono prawdziwe. Popatrzmy się na dane wejściowe, które przypominają 2 2 2 z B = 3 i A = 2. Pierwszego dnia musimy kupić dwa nowe bilety. Jeśli użyjemy ich ponownie drugiego dnia, dzień później będziemy zmuszeni do kupna kolejnych dwóch, a więc nasz sumaryczny koszt to 4. Jeśli jednak drugiego dnia użyjemy jednego z częściowo wykorzystanych biletów oraz kupimy jeden nowy, trzeciego będziemy mogli wykorzystać dwa już posiadane bilety, czyli całkowity koszt to 3. Można by próbować zmodyfikować naszą śmiałą tezę mówiąc, że nie ma sensu mieć więcej niż trzech biletów, które mogłyby być jeszcze użyte. Lub czterech. Lub… Być może prowadzi to (w jakiejś wersji) do poprawnego rozwiązania, ale spróbujmy poszukać innego sposobu. W zadaniach, które w jakiś sposób dotyczą przydziału zasobów, zawsze warto choć przez chwilę zastanowić się, czy można sformułować pytanie używając (ważonych lub nie) przepływów (lub cyrkulacji)…

 

 

…co w tym przypadku nie prowadzi do niczego przydatnego, ale warto było spróbować. Spróbujmy inaczej: na czym tak właściwie opierało się nasze rozwiązanie wersji z a_i\in\{0,1\}?

Lemat 1. Jeśli a_i=1 i a_j=1 dla pewnych i<j, to bez straty ogólności możemy założyć, że początek przedziału aktywności przynajmniej jednego biletu używanego i-tego dnia nie leży na prawo od początku przedziału aktywności obydwu biletów używanego j-tego dnia.

Dowód. Bez straty ogólności w powyższym rozumowania oznacza, że takie założenie nie pogarsza kosztu najlepszego możliwego rozwiązania. Weźmy jakiekolwiek rozwiązanie, w którym jest inaczej, czyli przedział aktywności biletu używanego i-tego dnia jest na prawo od przedziału aktywności biletu używanego j-tego dnia, więc sytuacja wygląda tak jak na poniższym rysunku.

metro-swap

W takiej sytuacji możemy po prostu zamienić ze sobą bilety używane w tych dwóch dniach! Kluczowe jest tutaj założenie, że wszystkie przedziały aktywności mają taką samą długość.

Daje nam to pewną wiedzę na temat struktury optymalnych rozwiązań. Powiedzmy, że 1-pojemność biletu to liczba dni i z a_i=1, w których został on użyty. Jeśli wyobrazimy sobie, że wszystkie bilety zostały posortowane (niemalejąco) względem początków swoich przedziałów aktywności, bez straty ogólności w każdym kolejnym dniu i, w którym a_i=1, używamy pierwszego biletu na naszej liście, którego 1-pojemność nie spadła jeszcze do zera. Czyli, zakładając, że znamy zarówno przedziały aktywności jak i 1-pojemności, proces przydziału biletów do dni i z a_i=1 jest w pełni deterministyczny. Do pełni szczęścia przydałoby się powiedzieć coś także na temat dni i z a_i=2.

Lemat 2. Jeśli a_i=2 i a_j=2 dla pewnych i<j, to bez straty ogólności możemy założyć, że początek przedział aktywności biletu używanego i-tego dnia nie leży na prawo od początku przedziału aktywności biletu używanego j-tego dnia.

Dowód. Tak jak w poprzednim dowodzie, popatrzmy na rozwiązanie, w którym jest inaczej, czyli początki przedziałów aktywności obydwu biletów używanych i-tego dnia są na prawo od początku przedziału aktywności (jakiegoś) biletu używanego j-tego dnia. Skoro a_j=2, tego dnia używamy jeszcze jakiegoś biletu. Być może jest to jeden z biletów używanych i-tego dnia, w takim przypadku popatrzmy na ten drugi (a jeśli nie, na dowolny z z dwóch biletów używanych i-tego dnia). Mamy więc bilet, którego używamy j-tego dnia, ale nie używamy i-tego, oraz bilet, którego używamy i-tego dnia, ale nie używamy j-tego. Sytuacja wygląda więc tak jak na poniższym rysunku.

metro-swap2

Dokładnie tak jak poprzednio, po chwili namysłu można dojść do (słusznego) wniosku, że można dokonać zamiany!

Czyli możemy powiedzieć, że jeśli 2-pojemność biletu to liczba dni i z a_i=2, w których został on użyty, to bez straty ogólności w każdym kolejnym dniu i, w którym a_i=2, używamy pierwszego biletu na naszej liście, którego 2-pojemność nie spadła jeszcze do zera.

No i pięknie, ale jak właściwie może nam to pomóc w rozwiązaniu zadania? Otóż okazuje się, że możemy użyć programowania dynamicznego. Skonstruujmy listę L_1 dni i, w których a_i=1 i listę L_2 dni i, w których a_i=2 i przyjrzymy się biletowi o najwcześniejszym początku przedziału aktywności. Gdybyśmy tylko znali jego 1– i 2-pojemność (no i ten początek przedziału), życie byłoby proste: wiedzielibyśmy, w których dniach powinien być on użyty. Wystarczyłoby więc usunąć je z list L_1 i L_2, i (jak w starym żarcie o informatyku) czynność powtórzyć. No, prawie: wypadałoby jeszcze dorzucić do L_1 wszystkie dni wyrzucone z L_2. Jest to o tyle niewygodne, że nie do końca wiadomo jak aktualne L_1 ma się do tego oryginalnego. Zróbmy więc inaczej: stwórzmy nową listę L_{1'}, na której będziemy przechowywać dni i, w których (oryginalnie) a_i=2, ale wybraliśmy już (dokładnie) jeden z biletów, których chcemy wtedy użyć. Korzystając z Lematu 1 i Lematu 2 otrzymujemy, że bilet o najwcześniejszym początku przedziału aktywności bez straty ogólności jest używany w pewnej liczbie pierwszych elementów list L_1, L_2 i L_{1'}. Co prawda nie wiemy w ilu, ale możemy sobie pozwolić na zgadnięcie tych trzech liczb (oraz sprawdzenie, czy ich suma nie przekracza A, oraz czy wszystkie zgadnięte dni mieszczą się w przedziale długości B). Następnie usuwamy te elementy z odpowiadających list i powtarzamy rozumowanie.

Mogłoby się wydawać, że opisane wyżej rozwiązanie jest dość brutalne, a nawet wykładnicze. Można jednak dość łatwo temu zaradzić: aktualne listy L_1 i L_2 są sufiksami tych oryginalnych. Zaś aktualna lista L_{1'} to nic innego jak sufiks już „zużytego” prefiksu L_2! Co oznacza nic innego niż to, że liczba podproblemów, które musimy rozwiązać, jest rzędu n^3. Dla każdego z nich musimy zgadnąć trzy liczby, które nie przekraczają A, a więc cała złożoność to \mathcal{O}(n^3A^3).

Taka złożoność wystarczała do rozwiązania zadania, ale.. można trochę lepiej. Przede wszystkim, w zasadzie nie opłaca się używać biletu mniej niż A razy, co dość łatwo pozwala na zmniejszenie czasu działania do \mathcal{O}(n^3A^2). Przy odrobinie staranności można jeszcze lepiej: wystarczy zgadnąć tylko w ilu pierwszych elementach z L_1 \cup L_{1'} chcielibyśmy wykorzystać rozważany bilet, co pozwala na zbicie złożoności do \mathcal{O}(n^3A). A może da się nawet lepiej?

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s