Trening z drzwiami I

Na rozpoczęcie sezonu proponuję zadanie o nawiasach z południowych eliminacji do NEERC 2015. Rozważamy nawiasy umieszczone na prostokątnej planszy. Interesuje nas zliczenie jej wszystkich (też prostokątnych) fragmentów, w których każdy wiersz jest prawidłowym nawiasowaniem.

Oryginalną treść można zobaczyć tutaj. Oprócz definicji prawidłowego ponawiasowania (standardowej) warto zwrócić uwagę na rozmiar rozważanej planszy n \times m: n,m \leq 50000 oraz (odrobinę mniej widoczne) n\cdot m \leq 10^6. Ten drugi prawdopodobnie ma na celu zagwarantowanie, że input nie jest zbyt duży.

Zanim zabierzemy się za rozwiązywanie, warto odświeżyć sobie wiedzę na temat prawidłowych nawiasowań. Rozważmy napis t[1]t[2] \ldots t[m], gdzie każde t[i] to nawias otwierający lub nawias zamykający. W wyobrażeniu sobie całej sytuacji pomaga zdefiniowanie sum częściowych s_0,s_1,\ldots,s_m, gdzie s_i to liczba nawiasów otwierających wśród t[1]t[2] \ldots t[i] minus liczba nawiasów zamykających (też wśród t[1]t[2] \ldots t[i]). Teraz t[i]t[i+1] \ldots t[j] jest prawidłowym nawiasowaniem dokładnie wtedy, gdy spełnione są następujące dwa warunki:

  1. s_{i-1}=s_j,
  2. s_i,s_{i+1},s_{i+2},\ldots,s_{j-1} \geq s_j.

Ten pierwszy mówi tylko tyle, że w całym fragmencie musi być tyle samo nawiasów otwierających co zamykających. Drugi zaś wymusza, że nigdy nie napotkamy nawiasu zamykającego, który nie ma odpowiadającego mu nawiasu otwierającego. Wygodnie wyobrażać sobie te dwa warunki tak jak na poniższej ilustracji.

drzwi01

Wrócmy do zadania. Interesuje nas policzenie prostokątnych fragmentów podanej planszy, których każdy wiersz jest prawidłowym nawiasowaniem. Nazwijmy kolejne wiersze całej planszy t_1,t_2,\ldots,t_n. Używając takich oznaczeń celujemy w policzenie r_1 \leq r_2 oraz c_1 \leq c_2, że t_i[c_1]t_i[c_1+1] \ldots t_i[c_2] jest prawidłowym nawiasowaniem dla każdego i=r_1,r_1+1,\ldots,r_2.

Jak mogłoby wyglądać rozwiązanie naiwne? Możemy na przykład ustalić c_1 i rozważać coraz większe c_2 = c_1,c_1+1,\ldots,m. W trakcie tych rozważań łatwo utrzymywać dla każdego wiersza i informację, czy t_i[c_1]t_i[c_1+1] \ldots t_i[c_2] jest prawidłowym nawiasowaniem: wystarczy przechowywać aktualny bilans i jeden bit informacji o tym, czy kiedykolwiek spadł już poniżej zera. Po zwiększeniu c_2 o jeden można wtedy uaktualnić informację dla każdego wiersza w czasie \mathcal{O}(1). Następnie musimy tylko zliczyć takie r_1 \leq r_2, że wiersze r_1,r_1+1,\ldots,r_2 są „dobre”. W tym celu wystarczy przeglądać kolejne r_2 utrzymując liczbę „dobrych” wierszy widzianych po ostatnim „złym”. Cała procedura pozwala nam na wyznaczenie wyniku w czasie \mathcal{O}(nm^2). Czyli niby fajnie, chyba że m jest duże. A przecież może być duże!

Ale chwila. Przecież wiemy, że n\cdot m \leq 10^6. Czyli jeśli m jest spore, to n musi być niezbyt duże. Wystarczyłoby więc skonstruować inną procedurę, która działa szybko dla małych n. Spróbujmy.

Biorąc pod uwagę docelową złożoność naturalnym pomysłem jest ustalenie r_1 i rozważanie kolejnych r_2=r_1,r_1+1,\ldots,n. W trakcie tych rozważań utrzymujemy dla każdej kolumny c_1 najmniejszą kolumnę \textrm{next}[c_1] \ge c_1 taką, że dla każdego i=r_1,r_1+1,\ldots,r_2 całe t_i[c_1]t_i[c_1+1] \ldots t_i[\textrm{next}[c_1]] jest prawidłowym nawiasowaniem. (Jeśli nie ma takiej kolumny, powiedzmy że \textrm{next}[c_1]=m+1.) Zauważmy, że w ten sposób tak naprawdę opisujemy wszystkie kolumny, które wraz z r_1,r_2,c_1 wyznaczają interesujący nas fragment. Wystarczy bowiem rozważyć \textrm{next}[c_1], \textrm{next}[\textrm{next}[c_1]+1], \textrm{next}[\textrm{next}[\textrm{next}[c_1]+1]+1], \ldots (tak długo, jak nie wyjedziemy poza m). Jeśli więc tylko uda nam się sprytnie przeliczyć wszystkie \textrm{next}[c_1] po zwiększeniu r_2 o jeden, łatwo uaktualnimy wynik przeglądając kolumny od prawej do lewej i akumulując odpowiednie liczniki. Ale jak uwzględnić ten nowy wiersz?

Przejrzyjmy go od prawej do lewej rozważając kolumny c_1=m,m-1,\ldots,1. Jednocześnie utrzymujmy na stosie już rozważone kolumny, przy czym po zmniejszeniu c_1 o jeden usuwamy ze szczytu wszystkie kolumny c_2, dla których bilans t_{r_2}[1]t_{r_2}[2] \ldots t_{r_2}[c_2] jest ściśle większy niż bilans t_{r_2}[1]t_{r_2}[2] \ldots t_{r_2}[c_1-1] (wcześniej tablicując sobie wszystkie takie bilanse), a następnie dorzucamy nową kolumnę c_1. Łatwo zauważyć, że bilanse odpowiadające kolejnym (patrząc od góry) elementom stosu są nierosnące. Ponadto kolumny c_2, dla których t_{r_2}[c_1]t_{r_2}[c_1+1] \ldots t_{r_2}[c_2] jest prawidłowym nawiasowaniem, tworzą górną część aktualnej zawartości stosu złożoną z kolumn, których bilanse są takie same jak bilans t_{r_2}[1]t_{r_2}[2] \ldots t_{r_2}[c_1-1]. Aby wyznaczyć nową wartość \textrm{next}[c_1] trzeba więc tylko znaleźć pierwszą kolumnę należącą do wspomnianej górnej części stosu, która jest także jedną z \textrm{next}[c_1], \textrm{next}[\textrm{next}[c_1]+1], \textrm{next}[\textrm{next}[\textrm{next}[c_1]+1]+1], \ldots (tutaj \textrm{next} oznacza wartości przed aktualizacją). W tym celu usuwamy kolejne elementy ze szczytu stosu lub podmieniamy \textrm{next}[c_1] na \textrm{next}[\textrm{next}[c_1]+1] tak długo jak jest to konieczne (eliminując zawsze mniejszą z dwóch kolumn odpowiadającym tym dwóm możliwościom). Po przetworzeniu wszystkich kolumn podmieniamy \textrm{next} na nowe wartości. Ile czasu potrzeba na przetworzenie jednego wiersza? Dorzucenie nowego elementu na stos to tylko zamortyzowany czas \mathcal{O}(1). Co trochę mniej oczywiste (i wymaga dowodu), tyle samo kosztuje wyznaczenie nowej wartości \textrm{next}[c_1]. Chwili zastanowienia wymaga także poprawność całej procedury: trzeba uzasadnić, że eliminowane kolumny nie mogą w przyszłości (to jest dla mniejszych c_1) utworzyć interesującego nas fragmentu.

Łącząc opisane dwie procedury w jeden algorytm otrzymujemy rozwiązanie, które działa w czasie \mathcal{O}(nm\min(n,m)). Po odrobinie gimnastyki wystarcza to do rozwiązania zadania, ale czy na pewno mamy ochotę na takie ćwiczenia? Pewnie nie. Za tydzień spróbujemy więc skonstruować rozwiązanie, które działa w czasie \mathcal{O}(nm).

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s