Omówienie zadania Nawiasowania (III etap XXVIII OI)

Dla danej permutacji \(p_1,\ldots,p_n\) mamy powiedzieć, czy istnieje poprawne nawiasowanie długości \(n\), które pozostaje poprawne, gdy spermutujemy ciąg nawiasów zgodnie z daną permutacją. Jeśli tak, to należy wypisać takie nawiasowanie.

Własności poprawnych nawiasowań

Nawiasom otwierającym przypiszmy wartość \(+1\), a nawiasom zamykającym wartość \(-1\). Przez \(s_i\) oznaczmy wartość dla \(i\)-tego nawiasu. Przypomnijmy, że nawiasowanie jest poprawne wtedy i tylko wtedy, gdy ciąg wartości ma sumę 0, a dowolny jego prefiks ma sumę nieujemną: \[\sum_{1\leq i\leq n} s_i = 0,\qquad \sum_{1\leq i\leq k} s_i \geq 0 \ \textrm{dla}\ k\leq n.\]

Jeżeli mamy dowolne poprawne nawiasowanie i wstawimy sobie gdzieś w jego środek nawias otwierający, gdzieś w innym miejscu nawias zamykający, ale tak by ten nowy otwierający był wcześniej niż ten nowy zamykający, to nowe nawiasowanie również będzie poprawne.

Podzadanie 1

Możemy przejrzeć wszystkie \(2^n\) nawiasowań o długości \(n\) i dla każdego z nich sprawdzić w czasie \(O(n)\), czy jest poprawne przed i po spermutowaniu. Zatem złożoność czasowa to \(O(2^n n)\).

Podzadanie 3

Zaznaczmy w układzie współrzędnych punkty \(P_i = (i,p_i)\) dla wszystkich \(1\leq i\leq n\) (wartość \(i\) nazwiemy kolumną punktu, a wartość \(p_i\) nazwiemy wierszem punktu). Każdemu punktowi musimy przypisać nawias otwierający lub zamykający tak, by czytane od lewej do prawej utworzyły poprawne nawiasowanie (nazwiemy je poziomym), ale także czytane od dołu do góry utworzyły poprawne nawiasowanie (nazwiemy je pionowym).

W alternatywnej interpretacji każdemu punktowi przepisujemy \(+1\) albo \(-1\), tak by suma dowolnych \(k\) punktów od lewej była nieujemna i suma dowolnych \(k\) punktów od dołu również była nieujemna, a suma po wszystkich punktach była równa \(0\).

Wprowadźmy porządek częściowy na punktach: powiemy, że \(P_i < P_j\), wtedy gdy zarówno \(i<j\) oraz \(p_i < p_j\). Zatem każdy odcinek pomiędzy dwoma punktami idący w górę i w prawo prowadzi od punktu mniejszego do punktu większego. Z kolei punkty połączone odcinkami prowadzącymi w prawo i w dół nie są porównywalne w naszym porządku.

Gdybyśmy umieli połączyć wszystkie punkty w porównywalne pary i w każdej parze punktowi mniejszemu przypisalibyśmy nawias otwierający, a punktowi większemu nawias zamykający, to uzyskalibyśmy poprawne rozwiązanie naszego zadania.

Rozważmy punkt w skrajnie dolnym wierszu oraz w skrajnie prawej kolumnie. Oczywiste jest, że jeżeli te punkty są różne, to są one porównywalne i pierwszy z nich jest mniejszy od drugiego, możemy więc te punkty sparować. W następnym kroku znowu wybieramy punkt położony najniżej oraz punkt położony najbardziej na prawo, tym razem jednak spośród punktów, które nie zostały jeszcze dotychczas wybrane. Jeśli jednak w pewnym momencie najniżej położony punkt i punkt położony najbardziej na prawo są identyczne, to na razie zostawiamy ten punkt niesparowany.

Na końcu uzyskujemy pewną liczbę sparowanych par oraz parzystą liczbę niesparowanych punktów, z których żadna para nie jest porównywalna. Wszystkim mniejszym punktom w parach przypiszemy \(+1\), a większym punktom \(-1\). Pytanie, co zrobić z niesparowanymi punktami?

Pomysł jest taki, żeby sparować je po kolei od lewej do prawej i również od lewej do prawej przypisać im na przemian \(+1\) i \(-1\). I o ile dla poziomego nawiasowania takie parowanie będzie poprawne, dlatego że w każdej nieporównywalnej parze nawias otwierający będzie występował przed nawiasem zamykającym, to w nawiasowaniu pionowym już tak nie musi być i może być ono niepoprawne.

Jeżeli popatrzymy sobie na wartości prefiksów dla tego nawiasowania, to mogą one spaść poniżej 0, ale minimalnie do wartości \(-1\) (jest tak dlatego, że jeżeli do poprawnego nawiasowania dodamy sobie parę nawias zamykający przed nawiasem otwierającym, to wartość na odcinku pomiędzy tymi dwoma nawiasami może zmniejszyć się co najwyżej o \(1\)).

Teraz zainteresujmy się warunkiem z podzadania 3, tzn. \(p_1=1\) i \(p_n=n\). Oznacza to, że możemy rozwiązać nasze zadanie dla mniejszej permutacji \(p_2,\ldots,p_{n-1}\), korzystając z algorytmu opisanego wyżej, a następnie otoczyć to rozwiązanie dodatkową parą nawiasów (to spowoduje dodanie \(+1\) dla każdego prefiksu w mniejszej permutacji, zatem przestaną być one ujemne).

Pozostaje oszacować złożoność czasową tego algorytmu. Aby szybko znajdować skrajnie dolne i skrajnie prawe punkty, będziemy poruszać się po nich dwoma wskaźnikami: jeden będzie szedł po punktach w kolejności rosnących wierszy, a drugi w kolejności malejących kolumn. Będziemy też w osobnych tablicach zaznaczać sobie, z których wierszy punkty już zostały wybrane i z których kolumn. Dzięki czemu całe rozwiązanie zaimplementujemy w czasie \(O(n)\).

Tak naprawdę to rozwiązanie działa nawet przy nieco słabszym założeniu: wystarczy bowiem, żeby punkty \(P_1\) i \(P_n\) były porównywalne, to znaczy, żeby \(P_1 < P_n\). Jednak przy takim założeniu musimy być troszkę bardziej uważni. Z poziomem nawiasowaniem nie będziemy mieli problemów, ponieważ nadal te dodatkowe nawiasy wstawiać będziemy na początku i na końcu, to w pionowym nawiasowaniu nawiasy dla tych punktów mogą zostać wstawione gdzieś w środek, tak więc mogą one nie otoczyć wszystkich niewłaściwych wartości \(-1\). Łatwo jednak temu zaradzić, zamieniając plusy z minusami na niesparowanych punktach, dzięki czemu ewentualne \(-1\) pojawią się w poziomym, a nie w pionowym nawiasowaniu.

Warunek konieczny istnienia nawiasowań

Intuicja jest taka, że problematyczne są punkty, których nie da się sparować z innymi porównywalnymi punktami.

Rozważmy najmniejszy kwadrat o boku \(k\), zaczepiony w górnym lewym wierzchołku, taki że poniżej tego kwadratu i na prawo od niego nie ma żadnych punktów. Wtedy każdy punkt w kwadracie może być porównywalny jedynie z innymi punktami w tym kwadracie (ponieważ jakikolwiek punkt spoza kwadratu ma większą kolumnę, ale mniejszy wiersz). Ponadto, ponieważ poniżej kwadratu nie ma żadnych punktów, to wszystkie punkty z wartościami kolumn od \(1\) do \(k\) muszą wystąpić w kwadracie. Analogicznie, ponieważ na prawo od kwadratu nie ma żadnych punktów, to wszystkie punkty z wartościami wierszy od \(n - k + 1\) do \(n\) również muszą wystąpić w kwadracie. A ponieważ w kwadracie o boku \(k\) może być co najwyżej \(k\) punktów, więc muszą to być właśnie punkty, których kolumny stanowią permutację liczb od \(1\) do \(k\), a numery wierszy permutację od \(n - k + 1\) do \(n\).

Innymi słowy, prefiks długości \(k\) w poziomym nawiasowaniu odpowiada sufiksowi długości \(k\) w pionowym nawiasowaniu. Jeżeli poziome nawiasowanie miałoby być poprawne, to oczywiście suma jego prefiksu musi być nieujemna. Analogicznie, jeżeli pionowe nawiasowanie ma być poprawne, to suma jego sufiksu musi być niedodatnia. A ponieważ te dwie sumy są sobie równe, wynika z tego, że muszą być równe \(0\). Zatem w naszym kwadracie rozmiaru \(k\) musimy mieć niezależne rozwiązanie zawierające \(k\) nawiasów. W szczególności, żeby takie rozwiązanie istniało, liczba \(k\) musi być parzysta (nie jest bowiem możliwe stworzenie poprawnego nawiasowania, mając do dyspozycji nieparzystą liczbę nawiasów).

Ponieważ kwadrat rozmiaru \(k\) zaczepiony w górnym lewym rogu musi zawierać niezależne rozwiązanie dla \(k\) nawiasów, to kwadrat rozmiaru \(n - k\) zaczepiony w dolnym prawym rogu musi zawierać niezależne rozwiązanie dla \(n - k\) nawiasów. Możemy zatem rekurencyjnie wykonać całe rozumowanie na tym mniejszym kwadracie.

Tak więc mamy warunek dostateczny na nieistnienie rozwiązania. Jeżeli w takim podziale na kwadraty, któryś z kwadratów będzie miał rozmiar nieparzysty, to rozwiązanie nie istnieje.

Jak efektywnie znaleźć taki podział? Dla ustalonej szerokości \(k\) możemy zapytać się, jaka jest wysokość \(h_k\) najmniejszego prostokąta, poniżej którego nie ma żadnych punktów. Nietrudno zauważyć, że \(h_k = n+1 - \min(p_1,\ldots,p_k)\). Jeśli zatem \(h_k= k\), to znaczy, że znaleźliśmy kwadrat.

Tę obserwację możemy uogólnić: jeżeli po znalezieniu pierwszego kwadratu będziemy dodawać nowe punkty, to za każdym razem, kiedy znowu \(h_k=k\), znaleźliśmy brzeg kolejnego kwadratu. Iterując się po kolejnych wartościach, jesteśmy w stanie uaktualniać minimum w czasie stałym. Wobec tego, procedura wyznaczania wszystkich kwadratów będzie działać w czasie \(O(n)\).

Pełne rozwiązanie

Jeśli w wyniku podziału wszystkie kwadraty będą miały parzystą wielkość, to możemy w każdym z nich znaleźć rozwiązanie niezależnie.

Rozważmy graf, w którym wierzchołki odpowiadają punktom, natomiast dwa wierzchołki są połączone krawędzią, jeżeli odpowiadające im punkty są porównywalne. Przypomnijmy, że zauważyliśmy, że punkty leżące w różnych kwadratach na pewno nie są ze sobą porównywalne, więc wierzchołki grafu leżące w różnych kwadratach muszą leżeć w różnych spójnych składowych. Okazuje się jednak, że jeżeli wierzchołki należą do tego samego kwadratu, to są połączone pewną ścieżką. Z tego będzie wynikać, że kwadraty są to tak naprawdę spójne składowe naszego grafu.

Pokażemy zatem, że dla dowolnych dwóch punktów w kwadracie istnieje między nimi ścieżka. Rozważmy dwa punkty w kwadracie. Jeżeli są one porównywalne, to wtedy istnieje między nimi trywialna ścieżka jednokrawędziowa. Załóżmy więc, że nie są porównywalne. Oznaczmy lewy punkt przez \(A\), a prawy punkt przez \(B\). Weźmy teraz minimalny kwadrat zaczepiony w lewym górnym rogu, który zawiera punkt \(A\) i oznaczmy jego rozmiar przez \(s\). Ponieważ założyliśmy, że nasz oryginalny kwadrat rozmiaru \(k\) nie zawiera w sobie żadnych mniejszych kwadratów, dla których nie ma punktów ani po prawo, ani poniżej, tak więc musi istnieć jakiś punkt po prawo od kwadratu \(s\) albo poniżej kwadratu \(s\).

Ale jeżeli będzie istniał jakiś punkt po prawo, to znaczy, że pewien wiersz w kwadracie \(s\) będzie nie zajęty, zatem będzie się w nim znajdować co najwyżej \(s-1\) punktów, czyli również jakiś punkt będzie musiał znajdować się poniżej tego kwadratu. Załóżmy bez straty ogólności, że punkt \(A\) dotyka prawego brzegu kwadratu, tzn. jego kolumna ma numer \(s\). Zatem ten punkt poniżej kwadratu (który oznaczymy \(Q\)) ma numer kolumny mniejszy niż \(s\), wobec tego \(Q<A\), zatem odpowiadające im wierzchołki są połączone krawędzią.

Rozważmy teraz minimalny kwadrat \(s'>s\) zawierający punkt \(Q\). Jeżeli punkt \(B\) znajduje się w tym kwadracie, to wtedy \(Q<B\) i możemy zakończyć dowód. W przeciwnym wypadku powtarzamy całe rozumowanie, biorąc punkt \(Q\) w miejsce punktu \(A\). W końcu znajdziemy ścieżkę łączącą punkty \(A\) i \(B\). To kończy dowód faktu, że kwadraty z podziału rzeczywiście odpowiadają spójnym składowym naszego grafu. A to da nam przydatną własność, która pozwoli nam znaleźć rozwiązanie w każdym kwadracie parzystej wielkości.

Rozwiązanie zaczniemy bowiem od znalezienia ścieżki pomiędzy wierzchołkami \(P_1\) i \(P_n\). Nie będzie nas jednak interesowała zupełnie dowolna ścieżka, ale taka, która idzie na przemian krawędziami w górę i w dół. Jeżeli znaleziona przez nas ścieżka nie ma tej własności, to łatwo ją poprawić, zamieniając każde dwie kolejne krawędzie w górę na jedną taką krawędź (z przechodniości częściowego porządku). Tak skrócona ścieżka będzie miała nieparzyście wiele krawędzi, ponieważ zarówno z wierzchołka \(P_1\) wychodzimy krawędzią w górę, jak i do wierzchołka \(P_n\) musimy wejść krawędzią w górę.

I teraz czas na kluczowy pomysł. Zaczynając w wierzchołku \(P_1\), co drugiemu wierzchołkowi ścieżki przypisujemy nawias otwierający, a pozostałym wierzchołkom przypisujemy nawiasy zamykające. Jeśli spojrzymy na ścieżkę jako zbiór krawędzi w górę, to wtedy jasne jest, że nawiasy w tych punktach utworzą prawidłowe pionowe nawiasowanie. Z kolei, jeżeli popatrzymy na ścieżkę jako zbiór krawędzi w dół, plus dodatkowo punkty \(P_1\) i \(P_n\), to nawiasy utworzą poprawne poziome nawiasowanie, przy czym w każdym prefiksie krótszym niż długość całego słowa liczba nawiasów otwierających będzie ostro większa niż liczba nawiasów zamykających. Wobec tego dla pozostałych punktów możemy użyć poprzedniego algorytmu, w którym łączyliśmy skrajnie dolny i skrajny prawy punkt w pary.

Pozostaje pytanie, jak efektywnie znaleźć ścieżkę pomiędzy punktami \(P_1\) i \(P_n\).

Najwygodniej jest zauważyć, że w dowodzie tego, że kwadrat jest spójną składową, konstruowana ścieżka była właśnie postaci naprzemienne krawędzie w górę i w dół. Zaczynamy więc od punktu \(P_1\) i ponieważ musi on leżeć na dolnym brzegu najmniejszego kwadratu, który go zawiera, będziemy dla niego szukali jakiegoś punktu na prawo od tego kwadratu. Wygodnie będzie w tym celu wybrać ten spośród punktów o większym wierszu niż punkt \(P_1\), który ma największą kolumnę, bo skoro jakiś punkt musi leżeć na prawo od kwadratu, to na pewno będzie to ten o największej kolumnie. Następnie szukamy punktu poniżej nowego kwadratu – wobec tego możemy wybrać punkt o najmniejszym wierszu leżący na lewo od ostatniego punktu. I dalej robimy analogicznie, aż dojdziemy do punktu \(P_n\).

Tę procedurę również możemy wykonać efektywnie za pomocą dwóch wskaźników: jednego idącego po wierszach w dół i pamiętającego punkt o największej kolumnie spośród dotychczas przebadanych i drugiego idącego po kolumnach w prawo i pamiętającego najbardziej dolny punkt z dotychczas przebadanych. Dzięki temu znajdziemy ścieżkę w czasie \(O(n)\).

Podsumowując całe rozwiązanie: najpierw wykonujemy podział na kwadraty. Jeżeli któryś z kwadratów ma rozmiar nieparzysty, to wtedy odpowiedź nie istnieje, a w przeciwnym wypadku odpowiedź składamy z niezależnych odpowiedzi dla kwadratów. W każdym kwadracie znajdujemy ścieżkę pomiędzy punktami w pierwszej i ostatniej kolumnie, a następnie pozostałe punkty próbujemy parować procedurą najbardziej dolny do najbardziej prawego. Cały algorytm będzie działał w czasie \(O(n)\).