Omówienie zadania Płytkie nawiasowania (I etap XXX OI)

Poprawność nawiasowania

Problem sprawdzenia, czy dane nawiasowanie jest poprawne, jest dość znanym i ważnym z perspektywy algorytmiki problemem. Typowe rozwiązanie polega na utrzymywaniu licznika początkowo ustawionego na \(0\) (o którym można myśleć jak o aktualnej głębokości nawiasowania, czy też poziomie zagnieżdżenia) i przejściu kolejno po wszystkich nawiasach:

• dodając \(1\) do licznika, jeśli napotkamy nawias otwierający,
• odejmując \(1\) od licznika, jeśli napotkamy nawias zamykający.

Jeśli po każdej aktualizacji licznika jest on nieujemny i na końcu wynosi 0, to nawiasowanie jest poprawne. W przeciwnym wypadku jest niepoprawne. Możemy o tym myśleć tak: nawiasowanie jest poprawne dokładnie wtedy, gdy na każdym jego prefiksie liczba nawiasów otwierających jest niemniejsza niż liczba nawiasów zamykających oraz na samym końcu zamknęliśmy wszystkie nawiasy. Ten algorytm działa w czasie liniowym względem długości ciągu oraz ma jeszcze jedną zaletę — pozwala łatwo sprawdzić głębokość nawiasowania. Jest nią bowiem maksymalna wartość licznika w trakcie przetwarzania ciągu.

Podzadanie 1. (\(n \leq 20\))

W tym podzadaniu wystarczy, dla każdego możliwego nawiasowania długości n, sprawdzić:

1. czy jest ono poprawne,
2. czy jego głębokość jest niewiększa niż \(H\),
3. ile nawiasów zostało odwróconych względem wyjściowego ciągu.

Następnie, spośród ciągów spełniających warunki 1. i 2., należy wybrać ten, który wymagał najmniejszej liczby odwróceń nawiasów (3.) i wypisać tę liczbę.

Sprawdzenie 1., 2. i 3. można wykonać w czasie liniowym względem długości nawiasowania, a wszystkich możliwych nawiasowań długości \(n\) jest \(2^n\), bo dla każdego indeksu \(1,\ldots,n\) są 2 możliwości: \(\text{'('}\) lub \(\text{')'}\). Rozwiązanie to działa więc w czasie \(O(2^nn)\).

Ciągi nawiasów a ciągi liczb

Poniższa obserwacja nie jest konieczna do rozwiązania tego zadania, ale może być pomocna w zrozumieniu problemu. W szczególności dalej w tekście będziemy korzystać z tej interpretacji.

Zauważmy, że nasz ciąg nawiasów możemy interpretować jako ciąg liczb całkowitych, gdzie \(\text{'('}\) odpowiada \(1\), a \(\text{')'}\) odpowiada \(-1\). Wówczas poprawność naszego ciągu oznacza dokładnie tyle, że każda suma prefiksowa tego ciągu jest nieujemna oraz suma całego ciągu wynosi 0. Ograniczenie głębokości nawiasowania przez \(H\) oznacza, że żadna z sum prefiksowych nie przekracza \(H\).

Podzadanie 2. (\(n \leq 3000\))

W tym podzadaniu można zastosować algorytm dynamiczny. Niech \(dp[i][j]\) oznacza minimalną liczbę zamian \(1 \rightarrow -1\) lub \(-1 \rightarrow 1\) (odwróceń nawiasów) na prefiksie długości \(i\) naszego ciągu potrzebnych, aby suma tego prefiksu wynosiła \(j\), a sam prefiks był poprawny, tj. każda wcześniejsza suma prefiksowa należała do przedziału \([0, H]\). Wówczas odpowiedzią do zadania będzie \(dp[n][0]\).

Stanem początkowym będą wartości \(dp[0][0] = 0\) oraz \(dp[0][j] = \infty\) dla \(j \neq 0\) (pusty ciąg ma zawsze sumę 0). A jak wyznaczamy wartość \(dp[i][j]\) na podstawie poprzednich wartości? Załóżmy, że na \(i\)-tej pozycji jest \(1\) (nawias otwierający). Mamy dwie opcje — możemy zamienić go na \(-1\) albo zostawić. Jeśli zamienimy, a chcemy uzyskać sumę \(j\), to poprzednim stanem naszego zamienionego ciągu był ten o sumie \(j+1\) z prefiksu \(i-1\). Musimy więc wybrać \(dp[i-1][j+1]\) i dodać \(1\), gdyż dokonaliśmy zamiany. Jeśli nie zamienimy, a chcemy uzyskać sumę \(j\), to poprzednim stanem naszego zamienionego ciągu był ten o sumie \(j-1\) z prefiksu \(i-1\). Musimy więc wybrać \(dp[i-1][j-1]\), ale już bez dodawania \(1\), gdyż nie dokonaliśmy zamiany. Zatem \(dp[i][j] = \min \left( dp[i-1][j+1] + 1, dp[i-1][j-1] \right)\). Analogicznie, w przypadku gdy na \(i\)-tej pozycji jest \(-1\) (nawias zamykający), to \(dp[i][j] = \min \left( dp[i-1][j-1] + 1, dp[i-1][j+1] \right)\).

Wartość \(dp[i][j]\) można obliczyć w czasie stałym na podstawie poprzednich wartości, więc przedstawiony algorytm działa w czasie \(O(nH)\).

Rozwiązanie wzorcowe (\(n \leq 10^6\))

Rozważmy dowolny ciąg nawiasów (liczb 1, -1) i pierwszą w nim pozycję \(i\) taką, że suma prefiksowa do \(i\)-tego elementu nie należy do przedziału \([0, H]\). To oznacza, że musimy odwrócić któryś z nawiasów na pozycjach \(1, 2, \ldots, i\), aby warunki zadania były spełnione. Zauważmy, że dla kolejnych prefiksów nie ma znaczenia, na których pozycjach były wykonywane zamiany, a jedynie ile ich było (i rodzaje nawiasów, które zamieniliśmy). Zatem możemy zmiany odkładać tak długo, jak to możliwe i to zapewni nam minimalną liczbę zmian nawiasów oraz należenie wszystkich sum prefiksowych do przedziału \([0, H]\).

Ta obserwacja pociąga za sobą następujące rozwiązanie zachłanne:

• Przechodzimy kolejno po nawiasach naszego nawiasowania i utrzymujemy licznik głębokości (sumę \(1\) i \(-1\) przy interpretacji jako ciąg liczb całkowitych).
• Jeśli kolejny nawias sprawiłby, że głębokość wyjdzie poza przedział \([0, H]\), to odwracamy go, a w przeciwnym wypadku zostawiamy taki, jaki był.

Dokonana liczba zamian jest odpowiedzią do zadania, a rozwiązanie działa w czasie \(O(n)\).

Uważny czytelnik zapyta jeszcze, czy na pewno po takich operacjach suma całego ciągu wyniesie 0. Zatem przeprowadźmy dowód.

Niech \(n\) będzie liczbą zmian typu \(1 \rightarrow -1\), a \(m\) będzie liczbą zmian typu \(-1 \rightarrow 1\). Pokażemy, że \(n=m\), a więc, skoro suma ciągu wyjściowego wynosiła 0, to suma ciągu po zastosowaniu algorytmu również wyniesie 0.

Przypuśćmy, że \(n < m\). Niech \(i\) oznacza pozycję ostatniej zmiany typu \(-1 \rightarrow 1\). Wówczas na prefiksie \([1, i-1]\) było \(m-1\) zmian typu \(-1 \rightarrow 1\) oraz nie więcej niż \(n\leq m-1\) zmian typu \(1 \rightarrow -1\). To z kolei oznacza, że suma prefiksowa do (\(i-1\))-tego elementu względem oryginalnego ciągu mogła się tylko zwiększyć. Skoro na \(i\)-tej pozycji w oryginalnym ciągu była \(-1\), to suma prefiksowa do (\(i-1\))-tego elementu wynosiła w oryginalnym ciągu co najmniej \(1\), a więc po zmianach wciąż wynosi co najmniej \(1\). To z kolei oznacza, że zmiana na \(i\)-tej pozycji nie była konieczna, czyli algorytm jej nie wykonał, co prowadzi do sprzeczności, a zatem \(n \geq m\). Podobnie pokazuje się, że \(n \leq m\) (tam suma prefiksowa do (\(i-1\))-tej pozycji wynosi maksymalnie \(H-1\)), co kończy dowód.