Omówienie zadania Les bitérables (III etap XXVIII OI)

Jasne jest, że praca, którą będziemy musieli wykonać podczas każdej przerwy jest zdeterminowana przez pozycje elementów scenografii przed przerwą i pozycje elementów scenografii po tej przerwie. Zatem przygotowanie planu zmian scenografii możemy zrobić niezależnie dla każdej z przerw, czyli potraktować dane wejściowe tak, jakby zawierały wiele przypadków testowych.

Wprowadźmy oznaczenie dla pojedynczego przypadku testowego. Rosnący ciąg \(a_0,a_1,\ldots,a_{s_a-1}\) będzie oznaczał pozycje elementów scenografii przed przerwą, natomiast ciąg \(b_0,b_1,\ldots,b_{s_b-1}\) będzie oznaczał pozycję elementów scenografii po przerwie. Przy podawaniu złożoności czasowych będziemy również używać zmiennej \(s\) jako górne ograniczenie na długości tych dwóch ciągów: \(s_a,s_b \leq s\).

Podzadanie 1

Jest to proste podzadanie poprawnościowe, w którym \(s = 1\). W tym przypadku możemy ręcznie przeanalizować wszystkie możliwe sytuacje. Zwykle będzie nam się po prostu opłacało przenieść jedyny element scenografii z pozycji wyznaczonej przez pierwszy ciąg na pozycję wyznaczoną przez drugi ciąg. Jednak może zdarzyć się tak, że te pozycje będą daleko od siebie, a jednocześnie stosunkowo blisko końców sceny, w takiej sytuacji bardziej opłacalne może być schowanie elementu za kulisy oraz przyniesienie drugiego elementu z przeciwnej strony. Musimy przy tym rozważyć przypadek, w którym element chowamy za lewą kulisę albo za prawą kulisę, jednak w obu tych przypadkach kosztem będzie długość sceny minus odległość pomiędzy pozycjami.

Tak więc ostateczny koszt to \(\min( |a_0-b_0|, \ d - |a_0-b_0| )\).

Oczywiście w tym podzadaniu musimy również rozważyć sytuację, kiedy jeden z ciągów jest pusty. Jeżeli pusty jest drugi ciąg, musimy jedyny element scenografii wrzucić albo za lewą, albo za prawą kulisę, co daje nam wzór \(\min( a_0, \ d-a_0 )\).

Z powyższej analizy wynika, że w rozwiązaniu nie tylko istotne będzie to, jak efektywnie przestawiać elementy na scenie, ale również, które elementy będą musiały wylądować za kulisami, a które elementy opłaca się za kulis przynieść.

Podzadanie 2

Dla \(s=3\) możemy zastosować jakieś rozwiązanie wykładnicze, które w mniej lub bardziej efektywny sposób będzie sprawdzało wszystkie możliwości przeorganizowania sceny. Jedno z takich rozwiązań może wyglądać następująco. Po kolei przeglądamy wszystkie elementy z górnego ciągu i dla każdego z nich decydujemy, czy parujemy ten element z kimś z dołu, czy też wysyłamy go za kulisy. W przypadku parowania z elementami z dołu musimy utrzymywać maskę bitową niesparowanych dolnych elementów, tak żeby każdy element z dołu był sparowany co najwyżej raz.

Gdy przeanalizujemy wszystkie górne elementy, elementy dolne pozostałe w masce musimy przynieść zza kulis. W przypadku operacji dotyczących kulis zawsze wynosimy lub przynosimy element z najbliższej kulisy. Zatem wygodnie nam tu będzie korzystać z funkcji, która dla danej pozycji elementu znajdzie nam odległość do najbliższej kulisy: \[kul(x) = \min(x, d-x).\] Nasze rozwiązanie będzie korzystać z programowania dynamicznego na maskach bitowych. Będziemy wypełniali kwadratową tabelkę \(dp[i,M] =\) najmniejszy koszt przydziału elementów \(\{a_0,\ldots,a_{i-1}\}\) oraz dolnych elementów z maski bitowej \(M\).

Dla \(i=0\) nie przydzielamy żadnych górnych elementów, natomiast wszystkie elementy dolne z maski \(M\) muszą być przyniesione zza kulis, zatem \[dp[0,M] = \sum_{j\in M} kul(b_j).\] Dla \(i>0\) mamy dwa przypadki w zależności od tego, co robimy z ostatnim górnym elementem: możemy go albo przenieść za kulisy, albo sparować z jakimś dolnym elementem \(j\) z maski \(M\): \[dp[i,M] = \min( dp[i-1,M] + kul(a_{i-1}), \ \min_{j\in M} dp[i-1,M\setminus\{j\}] + |a_{i-1} - b_j|)).\]

Wynikiem dla całego zadania będzie oczywiście \(dp[s_a,M]\), gdzie \(M\) jest maską złożoną ze wszystkich \(s_b\) bitów. Ponieważ tabelka ma rozmiar \(O(s 2^s)\), a obliczenie wartości każdego pola zajmuje nam czas \(O(s)\), wobec tego złożoność czasowa całego rozwiązania to \(O(2^s s^2)\).

Podzadanie 4

Aby przyspieszyć to rozwiązanie dokonamy pewnej istotnej obserwacji. Zauważmy, że jeżeli mamy pewne dwa górne elementy \(a_i < a_j\), które parujemy z pewnymi dwoma dolnymi elementami \(b_{i'} > b_{j'}\) (tzn. \(a_i \to b_{i'}\) oraz \(a_i \to b_{j'}\)), to zamieniając parowanie elementów na \(a_i \to b_{j'}\) oraz \(a_j \to b_{i'}\) nie zwiększymy kosztu. Innymi słowy, jeśli narysujemy sobie strzałki łączące sparowane elementy, to nie powinny się one przecinać.

To powoduje, że możemy zastosować w rozwiązaniu o wiele bardziej efektywne programowanie dynamiczne. A mianowicie, zarówno dla górnego jak i dolnego ciągu wystarczy nam pamiętać długość prefiksu sparowanych elementów: \(dp[i,j] =\) koszt przydziału elementów \(\{a_0,\ldots,a_{i-1}\}\) oraz \(\{b_0,\ldots,b_{j-1}\}\). Idea tego rozwiązania będzie bardzo podobna do standardowego rozwiązania problemu najdłuższego wspólnego podciągu. Jeżeli oba prefiksy są niepuste (\(i,j>0\)), to mamy wtedy trzy możliwości: albo ostatni górny element wrzucamy za kulisę, albo ostatni dolny element wyciągamy zza kulis, albo oba ostatnie elementy parujemy ze sobą: \[dp[i,j] = \min( dp[i-1,j] + kul(a_{i-1}),\ dp[i,j-1] + kul(b_{j-1}),\ dp[i-1,j-1] + |a_{i-1} - b_{j-1}|).\] Ponieważ tabelka ma wielkość \(O(s^2)\) i każdy jej element wypełniamy w czasie stałym, wobec tego całkowita złożoność czasowa tego rozwiązania to \(O(s^2)\).

Podzadanie 4 (inne rozwiązanie)

Chowanie lub wyciąganie elementu zza lewej kulisy możemy potraktować jak parowanie z wirtualnym elementem na pozycji 0. Analogicznie operacje na prawej kulisie to parowanie z wirtualnymi elementami na pozycji \(d\). Również tutaj w mocy jest obserwacja o nieprzecinaniu się strzałek.

Zatem optymalne parowanie musi składać się z trzech części. Pierwsza część będzie dotyczyła elementów związanych z lewą kulisą, przy czym może to być albo jakiś prefiks elementów z górnego ciągu, który będzie wysyłany za kulisę, albo jakiś prefiks elementów z dolnego ciągu, który będzie wyciągany zza kulis. Druga część to będą elementy parowane między sobą, przy czym parujemy kolejne elementy z górnego ciągu z kolejnymi elementami z dolnego ciągu. I w końcu trzecia część będzie dotyczyła elementów związanych z prawą kulisą, to znaczy albo pewnego sufiksu elementów górnego ciągu, które będą wrzucane za prawą kulisę, albo pewnego sufiksu elementów dolnego ciągu, które będą wyciągane zza prawej kulisy.

Do opisu takiego parowania wystarczy tylko jedna liczba całkowita \(t\), która oznacza długość prefiksu elementów z dolnego ciągu, które wyciągane są z lewej kulisy, minus długość prefiksu elementów górnego ciągu, które są wrzucane za lewą kulisę. Oczywiście co najwyżej jeden z tych prefiksów może mieć niezerową długość (jeżeli jest to dolny prefiks, to wtedy \(t > 0\), jeżeli górny prefiks to \(t<0\), a jeżeli żaden z elementów nie jest związany z lewą kulisą, to \(t=0\)).

Przejrzymy teraz wszystkie możliwe optymalne rozwiązania i dla każdego z nich obliczymy jego koszt. Iterujemy się po wszystkich sensownych wartościach parametru \(t\), czyli od \(-s_a\) do \(s_b\). Zatem kandydatów na wartość \(t\) jest rzędu \(O(s)\) i dla każdej takiej wartości, również w czasie \(O(s)\), możemy obliczyć koszt rozwiązania.

Jeśli rozszerzymy indeksowanie ciągów o elementy wirtualne, tzn. \(a_i = 0\) dla \(i<0\) oraz \(a_i = d\) dla \(i\geq s_a\) (analogicznie dla dolnego ciągu), to koszt dany jest następującym wzorem: \[C(t) = \sum_{i \in \mathbb{Z}} |a_i - b_{i+t}| = \sum_{\min(0,-t) \leq i < \max(s_a,s_b-t)} |a_i - b_{i+t}|.\]

Dostajemy kolejny algorytm o złożoności \(O(s^2)\).

Pełne rozwiązanie

Pomysł będzie polegał na tym, żeby dla kolejnych wartości \(t\) nie obliczać funkcji \(C(t)\) niezależnie, ale skorzystać z obliczonej funkcji dla mniejszego \(t\). W tym celu rozpiszmy sobie wartość bezwzględną znajdującą się pod sumą: \[|a_i - b_{i+t}| = \left\{ \begin{array}{ll} a_i - b_{i+t} & \textrm{dla}\ a_i \geq b_{i+t}, \\ -a_i + b_{i+t} & \textrm{dla}\ a_i < b_{i+t}. \end{array}\right.\]

Ustalmy sobie pewien górny element \(a_i\) i popatrzmy, jak wygląda wkład tego elementu do kosztu \(C(t)\). Dla tych wartości \(t\), w których \(a_i \geq b_{i+t}\), ten wkład wynosi \(a_i\), natomiast dla tych wartości \(t\), w których \(a_i < b_{i+t}\), wkład będzie wynosił \(-a_i\). Dla \(t = -s_a\), element \(a_i\) będzie sparowany z elementem \(b_{i+t}=0\), więc początkowo wkład będzie wynosił \(a_i\). Gdy będziemy zwiększać wartość \(t\), element \(a_i\) będzie parowany z kolejnymi elementami \(b_{i+t}\). Z początku wszystkie one będą wirtualne, ale w pewnym momencie zostanie on sparowany z pierwszym rzeczywistym elementem z dolnego ciągu. Dopóki ten element będzie mniejszy równy od \(a_i\), wkład do kosztu pozostanie dodatni. Jednak w pewnym momencie nastąpi sparowanie elementu \(a_i\) z elementem od niego większym, co spowoduje, że wkład elementu \(a_i\) zmieni się na ujemny. I pozostanie taki już do końca, ponieważ kolejne elementy \(b_{i+t}\) będą już tylko większe.

Widać zatem, że przy zwiększaniu wartości \(t\) do pewnego momentu wkład od elementu \(a_i\) jest równy \(a_i\), a od pewnego momentu jest równy \(-a_i\). Zatem podczas iterowania po wartości \(t\) wkład od tego elementu będzie musiał być tylko raz uaktualniony. Jeżeli przez \(j\) oznaczymy sobie indeks najwcześniejszego elementu \(b_j > a_i\), to wtedy uaktualnienie kosztu będziemy musieli zrobić dla \(t = j - i\) (zmieniamy wtedy koszt o \(-2a_i\)).

Wyznaczenie wartości \(j\) dla każdego górnego elementu możemy zrobić jednocześnie podczas scalania od tyłu listy górnych i dolnych elementów. W momencie, gdy będziemy dorzucać górny element, wartość \(j\) dla niego to będzie indeks ostatnio dorzuconego dolnego elementu. Ponieważ listy są posortowane, całość będziemy mogli zrobić w czasie \(O(s)\).

Następnie dla \(t = -s_a\) zainicjujemy początkowy koszt jako \(\sum_{i} a_i\), a następnie przejdziemy po wszystkich wartościach \(t\) w odpowiednich momentach uaktualniając koszt i sumarycznie będziemy mieli od \(O(s)\) uaktualnień.

To spowoduje, że w czasie \(O(s)\) wyznaczymy dla wszystkich wartości \(t\) wkłady do kosztów z wszystkich rzeczywistych górnych elementów. Symetrycznie możemy wyznaczyć wkłady od rzeczywistych elementów z dolnego ciągu.

Wirtualnymi elementami zza lewej kulisy nie przejmujemy się, ponieważ ich wkłady zawsze będą równe \(0\). Co do elementów zza prawej kulisy, to wystarczy policzyć, ile z nich będzie sparowanych z jakimiś rzeczywistymi elementami, bo ich wkład dla każdego takiego sparowania będzie równy \(d\). Nietrudno się przekonać, że liczba tych sparowań to \(|s_b - s_a - t|\).

Ostatecznie w czasie \(O(s)\) policzyliśmy wszystkie wartości \(C(t)\) i wystarczy jako odpowiedź do zadania wybrać spośród nich minimalną.