Omówienie zadania Wielki Upadek (II etap XXVII OI)

W zadaniu wybieramy, w którą stronę przewracamy domino. Możemy więc osobno obliczyć wynik dla upadku w prawo i w lewo, a odpowiedzią będzie maksimum z tych wyników. Obie sytuacje są w pełni symetryczne, więc dalsza część omówienia będzie zakładała przewracanie w prawo.

Zastanówmy się, które domino chcemy popchnąć na początku. Na pewno musi to być domino, którego nie przewraca żadna inna kostka, gdyż popchnięcie jej prowadzi do lepszego wyniku. Wyznaczenie klocków, które będziemy rozważać jako kandydatów do popchnięcia, okazuje się łatwe. Przejdziemy po wszystkich dominach w kolejności rosnących pozycji, zapamiętując, gdzie najdalej upada jedno z już przewróconych domin. Jeśli dosięga aktualnie rozpatrywanego domina, to jest ono popychane, więc aktualizujemy tę wartość. W przeciwnym wypadku aktualnie rozważane domino jest nowym kandydatem do popchnięcia. Popychamy je, co wyznacza nową wartość najdalej upadającego domina. Tak naprawdę utrzymujemy więc maksymalną na prefiksie wartość \(h_j + x_j\), gdzie \(h_j\) i \(x_j\) to wysokość i położenie \(j\)-tego domina.

Ta metoda tworzy nam podział domin na grupy, dla których uzyskujemy następujące wartości:

• \(a_i\) - liczba klocków w grupie \(i\)
• \(d_i\) - odległość pomiędzy końcem (po przewróceniu) grupy \(i\) oraz pierwszym dominem z grupy \(i + 1\)

W tej interpretacji, aby grupa \(i\) przewróciła grupę \(i+1\), musimy oczywiście dostawić pomiędzy nimi domina o sumie długości co najmniej \(d_i\) - po dominie o wysokości \(y\) kolejne ustawiamy oddalone od niego o \(y\) jednostek. Zauważmy, że kolejność dostawianych domin jest dowolna.

Nasze zadanie sprowadza się teraz do znalezienia maksymalnego pod względem sumy \(a_i\) przedziału grup, który jesteśmy w stanie przewrócić dostawiając w przerwach między grupami nowe domina.

Aby rozwiązać zadanie użyjemy metody gąsienicy - będziemy kolejno rozważać grupy \(1, 2, \dots \) jako początek upadku i przy zmianie rozważanego początku z \(p\) do \(p+1\) zwiększać koniec \(k\) przedziału dopóki możemy tak ustawić dodatkowe domina, aby przy popchnięciu pierwszego domina z grupy \(p\), upadły wszystkie domina ze wszystkich grup aż do grupy \(k\).

Zastanówmy się jak szybko odpowiadać na pytania o możliwość rozstawienia domin tak, aby upadł cały przedział.

Podzadanie \(H_1 = H_2\)

Z faktu, że w przerwie pomiędzy grupami \(i\) oraz \(i+1\) chcemy ustawić domina o sumie wielkości większej niż \(d_i\) wynika, że w tym podzadaniu liczba domin, których musimy użyć do pokrycia \(d_i\) jest równa \(\lceil d_i / H_1 \rceil\). Musimy więc w gąsienicy utrzymywać na przedziale od \(p\) do \(k\) sumę tych wartości i przy rozszerzaniu lub zwężaniu przedziału sprawdzać czy ta suma jest odpowiednio mała. A więc rozwiązanie tego podzadania działa w złożoności \(O(n)\).

Podzadanie \(n \leq 2000\)

Oznaczmy dla wygody \(H = \max(H_1, H_2)\) i \(L = \min(H_1, H_2)\) oraz \(C_H\) i \(C_L\) jako liczby dostępnych domin \(H\) i \(L\). Ponieważ \(L\) dzieli \(H\), domino \(H\) możemy symulować używając \(H/L\) domin \(L\).

Ponieważ kolejność domin, które stawiamy, aby grupa \(i\) przewróciła grupę \(i+1\) nie ma znaczenia, to możemy założyć, że na początek ustawimy domina \(H\), a później domina \(L\). Czyli możemy podzielić wypełnianie \(d_i\) na dwa etapy:

1. Dostawienie \(\lfloor d_i / H \rfloor\) domin \(H\) (z których każde możemy potencjalnie "symulować" używając \(H/L\) klocków \(L\))
2. Ustawienie jednego domina \(H\) lub \(\lceil (d_i \mod H) / L \rceil\) domin \(L\)

Oczywiście w pierwszej części bardziej opłaca nam się stawiać domina \(H\) niż symulowanie ich \(L\)-kami. Jeśli mamy rozwiązanie, w którym klocek \(H\) jest używany do pokrycia drugiego etapu pewnego przedziału, a domina \(L\) symulują w jakimś miejscu domino \(H\), to poprzez ich zamianę dostaniemy nie gorszy wynik (i prawdopodobnie zaoszczędzimy trochę domin \(L\)).

W gąsienicy rozpatrując przedział \([p, k)\) będziemy więc utrzymywać:

1. \( S_H = \sum_{i \in [p, k)} \lfloor \frac{d_i}{H} \rfloor \)
2. \( S_L = \sum_{i \in [p, k)} \lceil \frac{d_i \mod H}{L} \rceil \)
3. Posortowaną listę reszt z dzielenia \(d_i\) przez \(H\).

Aktualizacja końca przedziału jest więc bardzo prosta - dodanie/odjęcie od sum oraz dorzucenie/usunięcie elementu listy.

Przy stwierdzaniu możliwości pokrycia przedziału musimy rozważyć dwa przypadki:

1. \(C_H \leq S_H\)
   Musimy użyć trochę klocków \(L\) do symulowania klocków \(H\). Odejmiemy ich liczbę od \(C_L\), a następnie sprawdzimy czy pozostałe klocki \(L\) wystarczą na pokrycie \(S_L\).
2. \(C_H > S_H\)
   Zostało nam trochę klocków \(H\). Zauważmy, że skoro wystarczy jeden taki klocek aby pokryć dowolny element listy, to użyjemy ich do pokrycia jej największych elementów. Musimy wtedy sprawdzić czy klocków \(L\) wystarczy do pokrycia pozostałych reszt z dzielenia \(d_i\) przez H.

Złożonością rozwiązania będzie więc \(O(n^2)\), ponieważ każda aktualizacja końca przedziału gąsienicy zajmuje nam \(O(n)\) ze względu na aktualizację posortowanej listy i sprawdzanie największych elementów z listy w przypadku posiadania dodatkowych klocków \(H\).

Pełne rozwiązanie

Częścią poprzedniego rozwiązania, która nas ogranicza jest lista. Aby ulepszyć rozwiązanie, zastąpimy ją inną strukturą. Nasze rozwiązanie pozostanie więc bez zmian z wyjątkiem części ze znajdowaniem końcówek przedziałów, które pokrywamy pojedynczymi elementami \(H\).

Znajdowanie to zrealizujemy za pomocą drzewa przedziałowego punkt-przedział. Wartości utrzymywane w wierzchołku o przedziale bazowym \([a, b]\) to:

1. ile jest takich \(j\), że reszta z dzielenia \(d_j\) przez \(H\) zawiera się w przedziale \([a, b]\),
2. jaka jest suma reszt z dzielenia \(d_j\) przez \(H\), zawierających się w przedziale \([a, b]\).

Klockami \(H\) będziemy pokrywać największe wartości, czyli sufiks przedziału obsługiwanego drzewem. Ten sufiks można znaleźć, schodząc od korzenia i analizując pierwsze wartości utrzymywane w wierzchołkach. Po znalezieniu tego sufiksu musimy już tylko sprawdzić, czy suma wartości \(d_j\) spoza niego jest nie większa od \(C_L\).

Aktualizacja końca przedziału gąsienicy to aktualizacja ścieżki od liścia do korzenia w drzewie przedziałowym.

Dla każdego przedziału gąsienicy musimy więc wykonać \(O(\log H)\) operacji. Łączną złożonością obliczeniową rozwiązania jest więc \(O(n \log H)\).