Omówienie zadania Kontenery (II etap XXIV OI)

Symulacja

Najprostszym pomysłem jest naiwna symulacja procesu z zadania. Dla każdej operacji wyznaczamy wszystkie pozycje, w których zostanie postawiony kontener, i zwiększamy wartość w wynikowej tablicy, jak w poniższym pseudokodzie.

Rozwiązanie to ma złożoność \(O(nk)\), co wystarcza na rozwiązanie pierwszego podzadania.

Regularny dźwig

Zastanówmy się, jak rozwiązać dużo prostszą wersję problemu, daną w drugim podzadaniu, tj. kiedy wszystkie odległości między kontenerami \(d\) są równe.

Niech \(d = 1\). Mamy wtedy do rozwiązania dość znany problem. Dla każdej operacji możemy policzyć sobie ostatni kontener \(b_i = a_i + (\ell_i - 1) d_i\). Zauważmy, że \(i\)-ta operacja dodaje nam kontenery w miejscach od \(a_i\) do \(b_i\). Mamy zatem teraz dane odcinki \([a_i, b_i]\) i pytamy dla każdego pola, ile odcinków przecina dane pole.

Rozwiążemy ten problem używając sum częściowych. Zamiast dla każdej operacji przechodzić po całym odcinku, możemy dodawać znaczniki określające początek i koniec rozpatrywanego odcinka. Dla ustalenia uwagi tablicę znaczników nazwiemy \(znacz\). Dla \(i\)-tego odcinka możemy dodać jedynkę na polu \(znacz[a_i]\) (która oznacza, że od tego miejsca rozpoczyna się \(i\)-ty odcinek) oraz minus jedynkę na polu \(znacz[b_i+1]\) (która oznacza, że w tym miejscu \(i\)-ty odcinek już się skończył). Wystarczy wtedy po rozpatrzeniu wszystkich operacji policzyć sumy prefiksowe na tablicy \(znacz\), aby otrzymać szukany wynik.

Przykład działania algorytmu dla pewnego przykładowego testu z czterema operacjami, w których \(d_i = 1\). Górna część pokazuje rozkład kontenerów w teście, środkowa odpowiadające im odcinki oraz znaczniki dodawane do tablicy \(znacz\) znajdującej się w pierwszym wierszu dolnej części. Ostatni wiersz pokazuje tablicę \(wynik\), która jest tablicą sum prefiksowych tablicy \(znacz\).

Rozwiązanie to działa w czasie \(O(n + k)\).

Rozważmy zatem przypadek, że \(d > 1\). Zauważmy teraz, że możemy podzielić całą rampę na \(d\) obszarów, w taki sposób, że w jednym obszarze znajdują się wszystkie pola, których numer daje tą samą resztę z dzielenia modulo \(d\).

Podział na obszary dla \(n = 11\) oraz \(d = 3\).

Zauważmy teraz, że wszystkie obszary możemy rozpatrywać osobno (każda operacja dotyczy dokładnie jednego obszaru). Co więcej, dla każdego obszaru (których jest co najwyżej \(d\)) możemy zastosować powyższe rozważania, jak do \(d\) niezależnych podzadań.

Rozwiązanie działa w czasie \(O\!\left(\frac{n}{d} \cdot d + k\right) = O(n + k)\) i przechodzi drugie podzadanie.

Rozwiązanie wzorcowe

Idźmy dalej tym tropem i przypiszmy każdej operacji \((a_i, \ell_i, d_i)\) parę liczb \((d_i,\ a_i \bmod d_i)\). Intuicyjnie przypisujemy parę postaci: odległość pomiędzy kolejno stawianymi kontenerami i numer obszaru. Następnie pogrupujmy te operacje według powyższej charakteryzacji (do pogrupowania możemy skorzystać np. ze standardowej struktury danych w C++, jaką jest map). Koszt takiego pogrupowania to \(O(k \log k)\). Zauważmy teraz, że dla każdej grupy \((d, a)\), która ma \(k'\) elementów, jesteśmy w stanie rozwiązać ją algorytmem opisanym w poprzedniej sekcji w czasie \(O\!\left(\frac{n}{d} + k'\right)\).

Zastanówmy się teraz, jaka jest złożoność tego algorytmu. W obliczeniach pomińmy operacje dodawania początków i końców przedziałów w odpowiednich grupach, gdyż sumarycznie ten koszt wynosi \(O(k)\) i jest istotnie mniejszy niż ostateczna złożoność. Najpierw rozważmy takie grupy, dla których \(d > \sqrt{n}\), zatem \(\frac{n}{d} < \sqrt{n}\), czyli koszt przeanalizowania jednej grupy w tym przypadku wynosi co najwyżej \(\sqrt{n}\). Takich grup może być co najwyżej \(k\), zatem koszt ich rozpatrzenia wynosi \(O(k\sqrt{n})\).

Rozważmy teraz pozostałe grupy, czyli \(d \leq \sqrt{n}\). Ich sumaryczny koszt przeanalizowania szacujemy przez: \[ \sum_{i=1}^{\sqrt{n}} \sum_{j=0}^{i-1} \frac{n}{i} \leq \sum_{i=1}^{\sqrt{n}} n = n\sqrt{n}. \]

Zatem otrzymaliśmy algorytm działający w czasie \(O\!\left(k \log k + (n + k)\sqrt{n}\right)\).

Możemy także połączyć to rozwiązanie z rozwiązaniem wolnym. Podobną złożoność możemy osiągnąć, jeśli dla operacji z \(d_i > \sqrt{n}\) zastosujemy zwykłą symulację.