Omówienie zadania Laptopy (III etap XXX OI)

Treść zadania

W zadaniu mamy dane \(l\) ławek. Każda z nich jest prostokątem o szerokości równej \(w\) oraz długości \(s\). W ławkach początkowo siedzi \(n\) uczniów. Każdy z nich posiada laptopa, który możemy utożsamiać z prostokątem bez brzegu o szerokości \(d\) oraz długości \(s\). Wiemy, że \(i\)-ty uczeń (\(1\leq i \leq n\)) siedzi w ławce \(k_i\) oraz odległość lewego brzegu laptopa od lewego końca ławki wynosi \(p_i\). Gwarantowane jest, że początkowo laptopy nie nachodzą na siebie oraz nie wystają za brzeg ławki.

Następnie dostajemy \(q\) zapytań. Każde z zapytań jest liczbą \(m_i\) – jest to liczba uczniów, którzy chcieliby dodatkowo usiąść w ławkach. Należy odpowiedzieć na pytanie, jaka jest minimalna liczba już siedzących uczniów, którzy muszą się przesunąć, aby można było usadzić dodatkowych \(m_i\) uczniów tak, aby laptopy wciąż nie nachodziły na siebie oraz nie wystawały za brzeg ławki, lub stwierdzić, że nie jest to możliwe.

Wstępne uproszczenia

Wykonajmy kilka uproszczeń, które będą przydatne w dalszych częściach rozwiązania. Możemy wcześniej policzyć ławki, przy których początkowo nikt nie siedzi, i uwzględniać je przy liczeniu wolnego miejsca oddzielnie. Wtedy liczba niepustych ławek jest rzędu \(O(n)\). Od tej pory zakładamy, że wszystkie rozważane ławki są niepuste.

Zanim zaczniemy rozwiązywać problem, ponumerujmy (niepuste) ławki i posortujmy siedzących już \(n\) uczniów według ławki, przy której siedzą. Dodatkowo, posortujmy uczniów siedzących przy tej samej ławce względem pozycji ich laptopów rosnąco. Przenumerujmy uczniów zgodnie z powyższym sortowaniem. Niech \(i\)-ty uczeń siedzi w ławce \(r_i\). Wówczas prefiksem zbioru uczniów nazwijmy zbiór uczniów \(\{1, 2, \dots, i\}\). Odpowiada on prefiksowi ciągu pozycji laptopów na ławkach. Taki prefiks składa się z:

  • wszystkich pozycji przy ławkach o numerach mniejszych niż ławka, przy której siedzi uczeń \(i\), oraz
  • wszystkich pozycji znajdujących się w tej samej ławce, co \(i\)-ty uczeń, ale znajdujących się na lewo względem \(i\)-tego ucznia, oraz pozycji samego ucznia \(i\).
Ta definicja okaże się kluczowa przy rozwiązywaniu dalszych podzadań.

Podzadanie 1 – \(n \leq 20\)

Liczba siedzących uczniów jest na tyle mała, że możemy oddzielnie rozważyć wszystkie podzbiory uczniów, którzy zostaną na swoich miejscach. Niech \(A \subseteq \{1, 2, \dots, n\}\) będzie podzbiorem uczniów, którzy zostaną na swoich miejscach. Wtedy możemy dla każdej ławki oddzielnie policzyć, ile laptopów może dodatkowo zmieścić się po usunięciu uczniów nie należących do zbioru \(A\) (pamiętając o uwzględnieniu wolnej przestrzeni zarówno przed pierwszym siedzącym uczniem, jak i za ostatnim). Niech liczba wolnych miejsc będzie równa \(x_A\). Policzmy te wartości przed odpowiadaniem na zapytania w czasie \(O(2^n \cdot n)\).

Wtedy, jeśli w zapytaniu \(j\) chcemy zrobić miejsce dla dodatkowych \(m_j\) uczniów, to sumarycznie musimy usadzić \(m_j + n - |A|\) uczniów (wliczając tych, którzy zmienili swoje pozycje). Możemy zatem przeiterować się po wszystkich podzbiorach \(n\) uczniów i sprawdzić czy istnieje podzbiór \(A\) spełniający \(x_A \geq m_j + n - |A|\). Otrzymujemy rozwiązanie działające w złożoności \(O(2^n \cdot n)\), jako że liczba zapytań w zadaniu (\(q\)) nie przekracza \(n\).

Podzadanie 2 – \(n \leq 500\)

Zauważmy, że o ile liczby \(m_j\) w zapytaniach mogą być bardzo duże, to wynik (czyli liczba uczniów, których przesuniemy) jest ograniczony z góry przez \(n\). Możemy najpierw sprawdzić, ile wynosi maksymalna liczba uczniów, którzy mogą dodatkowo usiąść w ławkach, gdy przesuniemy wszystkich \(n\) uczniów. Ta liczba jest równa \(M = \lfloor \frac{w}{d} \rfloor l - n\). W związku z tym, jeśli w pewnym zapytaniu \(j\) zachodzi \(m_j > M\), to odpowiedzią na to zapytanie jest \(-1\). Od tej pory załóżmy zatem, że \(m_j \leq M\) dla każdego \(j\).

Obserwację, że wynik jest mały, wykorzystamy, aby wymyślić rozwiązanie opierające się na programowaniu dynamicznym. Jakie stany będą nam potrzebne? Na pewno będziemy potrzebować liczbę przesuniętych uczniów (żeby móc odtworzyć wynik) oraz pozycję, do której rozważyliśmy już przesunięcia. Niech w takim razie \(\texttt{DP}[k][i]\) oznacza maksymalną liczbę laptopów, które można umieścić na prefiksie pozycji ławek odpowiadającym prefiksowi uczniów \(\{1, 2, \dots, i\}\) tak, by

  • dokładnie \(k\) osób pozostało na swoim miejscu.
  • \(i\)-ty uczeń nie zmienił swojej pozycji.

Stanami początkowymi będą stany postaci \(\texttt{DP}[1][i]\). Wtedy uczniowie \(\{1,2, \dots, i-1\}\) zmieniają swoje pozycje, a \(i\) pozostaje na swoim miejscu. Zatem \(\texttt{DP}[1][i]\) to liczba wolnych miejsc w ławce \(i\)-tego ucznia na lewo od niego oraz liczba wolnych miejsc w ławkach poprzedzających tę ławkę, co możemy obliczyć wzorem.

Rozważmy teraz stany dla \(k > 1\). Wówczas stan \(\texttt{DP}[k][i]\) z definicji oznacza, że ostatni spośród \(k\) nieprzesuniętych uczniów to \(i\)-ty uczeń. Zatem, żeby wyznaczyć wartość tego stanu, musimy przeiterować się po wszystkich możliwościach przedostatniego nieprzesuniętego ucznia \(j\) spełniającego \(j < i\). Rozważmy przypadki:

  • uczeń \(j\) jest w tej samej ławce co uczeń \(i\) (tzn. \(r_i = r_j\)). Wtedy liczba laptopów mieszczących się pomiędzy \(j\)-tym oraz \(i\)-tym uczniem wynosi \(\lfloor \frac{p_i - p_j - d}{d} \rfloor\), zatem \(\texttt{DP}[k][i]\) aktualizujemy następującym wzorem: \[\texttt{DP}[k][i] := \max\left(\texttt{DP}[k][i],\, \texttt{DP}[k-1][j] + \left\lfloor \frac{p_i - p_j - d}{d} \right\rfloor\right)\]
  • uczeń \(j\) jest we wcześniejszej ławce niż uczeń \(i\) (tzn. \(r_j < r_i\)). Wtedy w ławce \(i\)-tego ucznia na lewo od niego zmieści się \(\lfloor \frac{p_i}{d} \rfloor\) laptopów. Ponadto w ławce \(j\)-tego ucznia na prawo od niego zmieści się \(\lfloor \frac{l-p_j-d}{d} \rfloor\) laptopów. Ponadto, jest \(r_j-r_i-1\) ławek pomiędzy ławką \(j\)-tego i \(i\)-tego ucznia (nie wliczając ławek tych uczniów). Wtedy w takich ławkach możemy dodatkowo zmieścić \((r_j-r_i-1) \lfloor \frac{l}{d} \rfloor \) laptopów. Zatem w tym przypadku otrzymujemy wzór: \[\texttt{DP}[k][i] := \max\left(\texttt{DP}[k][i],\, \texttt{DP}[k-1][j] + \left\lfloor \frac{p_i}{d} \right\rfloor + \left\lfloor \frac{l-p_j-d}{d} \right\rfloor + (r_j-r_i-1) \left\lfloor \frac{l}{d} \right\rfloor\right) \]

Dla każdego przejścia między stanami naszego programowania dynamicznego jesteśmy w stanie zliczyć miejsca na nowe laptopy w czasie stałym, zatem wartość \(\texttt{DP}[k][i]\) jesteśmy w stanie obliczyć w czasie \(O(n)\). Stąd, skoro stanów jest \(O(n^2)\), to obliczenie wartości całej tablicy programowania dynamicznego zajmuje \(O(n^3)\).

Jak odtworzyć z tego wynik zapytania? Wystarczy przeiterować się po wszystkich możliwych wartościach \(k\) oraz \(i\). Zakładamy wówczas, że dokładnie \(k\) uczniów pozostało na swoim miejscu (czyli potencjalnym wynikiem będzie \(n-k\)) oraz, że ostatnim z nich jest uczeń \(i\). Aby policzyć sumaryczną liczbę wolnych miejsc, musimy zsumować:

  • wartość \(\texttt{DP}[k][i]\), reprezentującą liczbę wolnych miejsc na prefiksie \(i\),
  • liczbę wolnych miejsc w ławce \(r_i\) na prawo względem \(i\)-tego ucznia,
  • liczbę wolnych miejsc w ławkach o numerach większych niż \(r_i\) (ponieważ \(i\) jest ostatnią osobą, która nie zmienia swojej pozycji, to pozycje wszystkich uczniów w następujących ławkach możemy zmieniać dowolnie),
  • należy również uwzględnić puste ławki, które zostały pominięte przy obliczaniu programowania dynamicznego.
Jeśli suma tych wartości jest większa lub równa \(m_j + n - k\), to \(n-k\) jest kandydatem na odpowiedź na zapytanie. Odpowiedzią jest minimum spośród wszystkich takich opcji. Obliczanie takiej sumy dla każdego stanu zajmuje \(O(1)\) czasu, zatem ostateczna złożoność rozwiązania wynosi \(O(n^2(n + q))\).

Pełne rozwiązanie

Spróbujmy przyspieszyć rozwiązanie poprzedniego podzadania. Drugi przypadek jest dużo prostszy do przyspieszenia, więc zacznijmy od niego. Zauważmy, że możemy wzór na \(\texttt{DP}[k][i]\) podzielić na dwa składniki - jeden zależny jedynie od wartości \(i\), a drugi zależny jedynie od indeksu poprzedniego ucznia \(j\): \[ \left(\left\lfloor \frac{p_i}{d} \right\rfloor - (r_i+1) \left\lfloor \frac{l}{d} \right\rfloor \right)+ \left(\texttt{DP}[k-1][j] + \left\lfloor \frac{l-p_j-d}{d} \right\rfloor + r_j\left\lfloor \frac{l}{d} \right\rfloor \right) \] Możemy zatem zapamiętać pomocniczą wartość utrzymującą maksymalną możliwą wartość drugiego składnika powyższej sumy dla ustalonego \(k\) oraz \(j\) siedzącego we wcześniejszej ławce niż obecnie rozpatrywany uczeń \(i\) i aktualizować ją w trakcie zmiany rozpatrywanej ławki.

Teraz wróćmy do pierwszego przypadku. Tutaj sytuacja jest trochę bardziej skomplikowana, ponieważ nie możemy tak łatwo rozdzielić wzoru na dwa składniki niezależne od siebie, jak powyżej, ze względu na podłogę występującą we wzorze. Ale czy na pewno nie możemy? Zauważmy, że jeśli \(p_i \bmod d \geq p_j \bmod d\), to \(\lfloor \frac{p_i-p_j-d}{d} \rfloor = \lfloor \frac{p_i}{d} \rfloor - \lfloor \frac{p_j}{d} \rfloor -1 \). W przeciwnym przypadku, jeśli \(p_i \bmod d < p_j \bmod d\), to \(\lfloor \frac{p_i-p_j-d}{d} \rfloor = \lfloor \frac{p_i}{d} \rfloor - \lfloor \frac{p_j}{d} \rfloor -2 \).

Dlaczego nam to pomaga? Ponieważ teraz w zależności od prostego warunku znów jesteśmy w stanie podzielić wzór naszego programowania dynamicznego na dwa oddzielne składniki, jak w poprzednim przypadku. Gdybyśmy mieli jakąś strukturę danych, na której wartości \(\texttt{DP}[k-1][j] - \lfloor \frac{p_j}{d} \rfloor \) będą posortowane względem reszty z dzielenia \(p_j\) przez \(d\), to znalezienie optymalnej takiej wartości byłoby znalezieniem maksimum na pewnym prefiksie \([0, p_i]\) oraz sufiksie \([p_j+1, d-1]\). Strukturą danych, która pozwala szybko wykonywać takie operacje, jest np. drzewo przedziałowe. Możemy również utrzymywać strukturę danych \(\texttt{set}\) przechowującą jedynie maksima prefiksowe (sufiksowe).

Możemy zatem wyznaczyć wartość jednego stanu \(\texttt{DP}[k][i]\) w czasie \(O(\log d)\) lub \(O(\log n)\), w zależności od użytej struktury danych (dynamicznie rozwijane drzewo przedziałowe lub \(\texttt{set}\)).

Możemy również przyspieszyć obliczanie odpowiedzi na zapytania - po obliczeniu wartości \(\texttt{DP}\) dla wszystkich stanów, możemy spreprocesować wartości wolnych miejsc (zgodnie z wzorem z poprzedniego podzadania), a następnie wystarczy dla każdej liczby nieprzesuniętych uczniów \(k\) zapamiętać opcję, która maksymalizuje liczbę wolnych miejsc. W ten sposób odpowiadamy na zapytania w czasie \(O(nq)\), lub w \(O(q\log n)\), jeśli skorzystamy z monotoniczności liczby wolnych miejsc względem liczby nieprzesuniętych uczniów.

Otrzymujemy zatem całe rozwiązanie działające w złożoności \(O(n^2\log n)\).

Alternatywne rozwiązanie

Możemy również rozważyć nieco inne programowanie dynamiczne. Dla każdej ławki oddzielnie obliczmy \(\texttt{DP}[i][j]\), który utrzymuje parę liczb:

  • maksymalną liczbę uczniów, którzy mogą usiąść przy założeniu, że przesuwamy dokładnie \(j\) uczniów siedzących w tej ławce oraz obecnie rozpatrujemy \(i\)-tego ucznia od lewej. Niech \(p_i\) oznacza pozycję lewego końca laptopa \(i\)-tego ucznia.
  • najmniejszą pozycję lewego końca ostatnio położonego laptopa, w przesunięciu, w którym ta maksymalna liczba uczniów może usiąść, przy czym pozycja lewego końca ostatnio położonego laptopa jest równa co najwyżej \(p_i\).

Ustalmy ławkę \(k\) oraz niech \(s_k\) oznacza liczbę uczniów siedzących w tej ławce. Zauważmy, że jedyne wartości, jakich potrzebujemy, aby obliczyć \(\texttt{DP}[i][j]\), to \(\texttt{DP}[i-1][j-1]\) oraz \(\texttt{DP}[i-1][j]\), skąd otrzymujemy następujące przejścia:

  • \(i\)-ty uczeń się nie przesuwa. Wówczas pomiędzy optymalnym ułożeniem lewego końca po rozpatrzeniu \(i-1\) uczniów, z których \(j\) się przesuwa, a pozycją \(i\)-tego ucznia zmieści się dodatkowe \[\left\lfloor \frac{p_i - \texttt{DP}[i-1][j].second-d}{d} \right\rfloor \] laptopów, a drugą wartością w parze jest po prostu pozycja laptopa \(i\)-tego ucznia.
  • \(i\)-ty uczeń się przesuwa. Wówczas analogicznie, zmieścimy dodatkowo \[\left\lfloor \frac{p_i - \texttt{DP}[i-1][j-1].second-d}{d} \right\rfloor \] laptopów i zgodnie z tą wartością możemy obliczyć pozycję ostatnio położonego laptopa.
Należy przy tym oddzielnie rozważyć miejsca na laptopy znajdujące się na lewo od pierwszego siedzącego ucznia w ławce oraz na prawo od ostatniego siedzącego ucznia w ławce. Możemy to zrobić przykładowo dodając "fikcyjnych" uczniów, których laptopy posiadają lewe końce odpowiednio w pozycjach \(-d\) oraz \(w\).

Powyższe programowanie dynamiczne działa w złożoności \(O(s_k^2)\). Ponieważ \(\sum_{i=1}^l s_i = n\), to sumaryczny czas działania dla wszystkich ławek wynosi \(O(n^2)\). W celu optymalizacji pamięci możemy zauważyć, że licząc \(\texttt{DP}[i][j]\) potrzebujemy jedynie wartości z poprzedniego wiersza, zatem możemy przechowywać jedynie ostatnie dwa wiersze.

Musimy następnie połączyć optymalne wyniki z wszystkich ławek. Możemy w tym celu rozważać \(\texttt{DP2}[i]\) dla \(0 \leq i \leq n\) utrzymujące maksymalną liczbę dodatkowych miejsc dla uczniów przy założeniu, że dokładnie \(j\) zmieniło swoją pozycję. Po skończeniu obliczania \(\texttt{DP}\) dla danej ławki możemy zaktualizować dla każdego \(0\leq i \leq n, 0 \leq j \leq s\) wartość \(\texttt{DP2}[i]\) poprzez wartość \(\texttt{DP2}[i-j] + \texttt{DP}[s][j]\) w czasie \(O(ns_k)\). Należy również pamiętać o uwzględnieniu pustych ławek.

Zatem łączna złożoność obliczania tablicy \(\texttt{DP2}\) wynosi \(O(\sum_{i=1}^ls_k n) = O(n^2)\). Mając tą tablicę jesteśmy w stanie odpowiedzieć na zapytania w czasie \(O(q \log n)\), ponieważ wartości w tablicy \(\texttt{DP2}\) są niemalejące, zatem wystarczy znaleźć najmniejszy indeks \(i\) taki, że \(\texttt{DP2}[i] \geq m_j\).

Sumaryczna złożoność czasowa tego rozwiązania wynosi \(O(n^2)\) oraz pamięciowa &ndash; \(O(n)\), co pozwalało uzyskać 100 punktów na zawodach.

 

Opis przygotowano w ramach projektu "Mistrzostwa w Algorytmice i Programowaniu - Uczniowie" - zadania finansowanego ze środków Ministerstwa Cyfryzacji.