Omówienie zadania Różnorodność (I etap XXV OI)

Wstęp

W zadaniu mamy daną tablicę \(A\) o wymiarach \(m \times n\). Podtablice tablicy \(A\) o wymiarach \(k \times k\) nazwiemy jej k-fragmentami. Różnorodnością k-fragmentu nazwiemy liczbę jego różnych elementów. Za zadanie mamy policzyć maksymalną różnorodność k-fragmentu występującego w tablicy \(A\) oraz sumę różnorodności wszystkich jej k-fragmentów. W omówieniu wartości tablicy będą również nazywane kolorami. Zakładamy, że wiersze i kolumny w tablicy są numerowane od \(0\).

Najprostsze podejście

Najprostszym sposobem na rozwiązanie zadania jest metoda brutalna, polegająca na przejściu po wszystkich k-fragmentach tablicy, a następnie w czasie \(O(k^2)\) dla jednego fragmentu wyliczyć jego różnorodność, osiągając sumaryczną złożoność \(O(nmk^2)\). Rozwiązanie to można przyspieszyć do \(O(nmk)\), używając metody gąsienicy.

Kluczowe podzadanie

Podzadania niekiedy potrafią bardzo pomóc w dojściu do rozwiązania wzorcowego i tak będzie również w tym przypadku. Mianowicie w podzadaniu 4. mamy do czynienia z ograniczeniem \(m \leq 2k\). Zajmijmy się najprostszym przypadkiem, w którym \(n = k\).

Zauważmy, że to, czy dany kolor \(c\) będzie wliczony do różnorodności danego fragmentu, zależy tylko od dwóch miejsc w tablicy, w których ten kolor występuje. Maksymalny numer wiersza \(i < k\), taki że \(i\)-ty wiersz zawiera kolor \(c\), nazwiemy \(\text{max}(c)\). Jeśli takiego \(i\) nie ma, to \(\text{max}(c) = -1\). Analogicznie, minimalny numer wiersza \(i \geq k\), taki że \(i\)-ty wiersz zawiera kolor \(c\), nazwiemy \(\text{min}(c)\). Jeżeli takie \(i\) nie istnieje, to \(\text{min}(c) = 2k\). Dany kolor \(c\) będzie wliczony do k-fragmentu zaczynającego się w wierszu \(x\), wtedy gdy \(x \leq \text{max}(c)\) lub \(\text{min}(c) - k < x\). Dla każdego koloru \(c\) obliczymy wartości \(\text{max}(c)\) oraz \(\text{min}(c)\) w czasie \(O(C + n \cdot m)\), a następnie za pomocą sumy prefiksowej odzyskamy różnorodność dla każdego k-fragmentu w czasie \(O(m)\).

Uogólnienie dla \(n > k\)

Możemy w ten sam sposób policzyć różnorodność dla k-fragmentów zaczynających się w \(0\)-wej kolumnie, a następnie chcielibyśmy zaktualizować wartości \(\text{max}\) i \(\text{min}\) dla poszczególnych kolorów, aby na ich podstawie obliczyć wynik dla k-fragmentów zaczynających się w \(1\)-wszej kolumnie. Zauważmy, że przy takim "przesunięciu okienka", dokładnie \(m\) wartości przestanie nas obchodzić, a dokładnie \(m\) nowych zacznie. Czyli przy każdym przejściu zaktualizujemy informacje dla \(O(m)\) kolorów.

W jaki więc sposób możemy szybko aktualizować informacje dla każdego koloru? Dla każdego koloru możemy utrzymywać dwie kolejki monotoniczne — odpowiednio na wartości \(\text{max}\) i \(\text{min}\). Dzięki nim możemy w czasie stałym dowiedzieć się o każdej z wartości po aktualizacji, a następnie zaktualizować naszą tablicę do sumy prefiksowej, wyrzucając stare wartości i wsadzając nowe. Takie rozwiązanie zapewni nam złożoność czasową oraz pamięciową \(O(n \cdot m)\), ponieważ każdy element zostanie dodany tylko do jednej kolejki oraz tylko jeden raz.

Rozwiązanie wzorcowe

Pozostało nam jedynie rozwiązać problem, w którym liczba wierszy przekracza \(2k\). Zauważmy jednak, że możemy podzielić naszą planszę na pasy o długości \(2k\), nachodzące na siebie w ten sposób, aby policzyć wynik dla każdego k-fragmentu. Kolejne pasy będą miały więc \(k\) wspólnych elementów. Dla każdego paska wynik obliczymy używając algorytmu z poprzedniego podzadania. Złożoność naszego algorytmu nie zmienia się względem poprzedniego podzadania i jest równa \(O(n \cdot k \cdot \frac{m}{k})\) = \(O(n \cdot m)\).