Wielka Przesmycka Reloaded 2011 - omówienie zadań

22.11.2011

A Mona Lisa

Na wejściu dostajemy tablicę $ n \times n $ wypełnioną literami. Dla każdego spójnego fragmentu $ k \times k $ chcemy policzyć ile różnych liter można w nim znaleźć. Będziemy nazywali tą wartość jakością fragmentu.

W wersji basic $ n \leq 1000 $, ale $ k\leq 50 $, co od razu nasuwa myśl, że wystarczyłoby rozwiązanie o złożoności $ \mathcal{O}(n^{2}k) $. Taki pierwszy najprostszy (a może nawet prymitywny) pomysł od razu daje algorytm o czasie działania $ \mathcal{O}(n^{2}k^{2}) $: dla każdego z $ (n-k+1)^{2} $ możliwych fragmentów przeglądamy wszystkie $ k^{2} $ pola. Jak pozbyć się tego jednego $ k $ z czasu działania? Wystarczy tylko zauważyć, że dla sąsiednich fragmentów zdecydowana większość przeglądanych pól będzie dokładnie taka sama. Zakładając, że policzyliśmy ile jest pól każdego koloru w danym fragmencie, wyznaczenie takich statystyk dla fragmentu przesuniętego o jeden w pionie lub poziomie wymaga tylko dodania i odjęcia jednego rzędu lub kolumny. Taką operację możemy łatwo wykonać w czasie $ \mathcal{O}(k) $. Podczas wyznaczania statystyk dla kolejnego fragmentu możemy także łatwo uaktualniać liczbę kolorów, które występują przynajmniej raz, a więc uzyskujemy rozwiązanie całego problemu w wersji basic.

W wersji professional wiemy tylko, że $ k\leq n $. Co samo w sobie nie jest szczególnie interesującą informacją... Naszym celem będzie uzyskanie rozwiązania o złożoności $ \mathcal{O}(n^{2}\log n) $. Idea jest dość prosta: będziemy przetwarzali jednocześnie wszystkie fragmenty rozpoczynające się w tym samym wierszu. Przyjrzyjmy się bliżej jak wygląda sytuacja dla takich fragmentów. Każdy kolor (dla ustalenia uwagi: zielony) występujący w jednym z $ k $ kolejnych wierszy powoduje zwiększenie jakości niektórych fragmentów o jeden. A dokładniej, jeśli mamy zielone pola w kolumnach $ x_{1} < x_{2} < \ldots < x_{t} $, gdzie $ x_{i+1} \leq x_{i} + k $ oraz $ x_{1},...,x_{t} $ jest maksymalnym zbiorem kolumn o tej własności, to powinniśmy zwiększyć (o jeden) jakość wszystkich  fragmentów zaczynających się w kolumnach od  $ \max(1,x_{1}-k+1) $-tej do $ x_{t} $-tej, patrz rysunek 1.

Rysunek 1: Zwiększanie jakości w wierszu ze względu na wystąpienia zielonego, $ k=4 $.

 

Pierwsza ważna obserwacja jest następująca: zamiast przechowywać te wszystkie $ +1 $, lepiej dla każdej kolumny pamiętać dla ilu kolorów właśnie w tej kolumnie zaczyna pojawiać się $ +1 $, a dla ilu kończy (lub, inaczej mówiąc, jaka jest suma po wszystkich kolorach czerwonych liczb z rysunku). Mając taką informację możemy łatwo wyznaczyć jakość każdego fragmentu zaczynającego się w danym wierszu idąc od lewej do prawej w czasie $ \mathcal{O}(n) $. Ale to oczywiście nie załatwia sprawy, musimy jeszcze umieć przejść do fragmentów zaczynających się o jeden wiersz niżej. Powiedzmy, że dana kolumna jest zielona jeśli występuje w niej przynajmniej jedno zielone pole. Jeżeli kolumna przestaje być zielona, być może musimy pozbyć się jakichś $ +1 $. Podobnie, jeżeli kolumna zaczyna być zielona, być może musimy dołożyć jakieś $ +1 $. Łatwo zauważyć, że zależy to tylko od pozycji poprzedniej i następnej zielonej kolumny! W szczególności, jeśli kolumna $ x $ przestaje być zielona, ale odległość między poprzednią i następną nie przekracza $ k $, nie musimy niczego zmieniać. W innych sytuacjach być może musimy dołożyć jeden blok złożony z $ +1 $ lub podzielić istniejący na dwa (być może zdegenerowane). Na rysunku~\rref{figure:quality_modify} można zobaczyć przykład tej drugiej sytuacji. W tym momencie widać dlaczego zamiast jawnie przechowywać wszystkie $ +1 $ zdecydowaliśmy się pamiętać początki i końce bloków. Pozostaje tylko jeden problem: jak szybko znaleźć poprzednią/następną zieloną kolumnę? Wystarczy dla każdego koloru pamiętać w drzewie zrównoważonym (na przykład w set<int>) wszystkie aktywne kolumny...

Rysunek 2: Po przesunięciu o jeden wiersz kolumna przestaje być zielona.

 

Oczywiście nie sposób przejść obojętnie obok pytania czy możliwe jest rozwiązanie liniowe (czyli w tym przypadku $ \mathcal{O}(n^{2}) $). Co dość zaskakujące, jest to możliwe. Załóżmy, że $ n=2k $ i podzielmy całą tablicę na 4 fragmenty $ k\times k $. Popatrzmy na zielone pola w lewym górnym kwadracie. Jeśli są tam pola $ x $ i $ y $ takie, że $ y $ jest na prawo i poniżej $ x $, to po chwili zastanowienia można dojść do wniosku, że $ x $ wcale nie jest nam potrzebne do szczęścia: każdy fragment, który zawiera $ x $, zawiera także $ y $, patrz rysunek 2. Tak naprawdę wystarczy więc pozostawić w lewym górnym kwadracie tylko te pola, które nie są zdominowane przez żadne inne. Podobną operację możemy wykonać dla pozostałych kwadratów. Gdyby okazało się, że wszystkie zielone pola znajdują w lewym górnym kwadracie, takie uproszczenie wejścia dość łatwo pozwoliłoby nam na wyznaczenie wszystkich fragmentów w czasie proporcjonalnym do liczby zielonych pól, których jakość należy zwiększyć (wystarczy na przykład zauważyć, że po przesunięciu się o jeden wiersz w dół ich zbiór na pewno nie ulegnie zmniejszeniu).

Rysunek 3: Tablica po usunieciu wszystkich niepotrzebnych zielonych pól.

 

Do rozwiązania pozostają dwie (nietrywialne) kwestie:

  1. sytuacja w jednym kwadracie jest prosta, ale fragment przecina cztery kwadraty jednocześnie...
  2. jak pozbyć się założenia, że $ n=2k $?

Przyjemność zmierzenia się z nimi pozostawiamy Czytelnikowi.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com