Editorial for ICPC NAQ 2016 D - Brackets - DMOJ: Modern Online Judge

Editorial for ICPC NAQ 2016 D - Brackets

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let $s_1, \dots, s_n$ ~s_1, \dots, s_n~ denote the sequence of brackets.
An alternative way to characterize a valid bracket sequence:
1. For each prefix of the sequence, there are at least as many left brackets as there are right brackets, and
2. there are equally many left and right brackets in the entire sequence.
Basic idea:
- Step through the sequence from left to right, keeping track of the number of left and right brackets.
- At some point start inverting brackets. At some later point, stop inverting brackets.
- At each step, make sure there are at least as many left brackets as there are right brackets (condition 1).
- When at the end, make sure there are equally many left and right brackets (condition 2).
How to decide when to start/stop inverting? Dynamic programming.
Let $dp(i, l, t)$ ~dp(i, l, t)~ be true iff it's possible to step through $s_i, \dots, s_n$ ~s_i, \dots, s_n~ such that conditions 1 and 2 are satisfied, assuming that $l$ ~l~ is the number of left brackets we've seen so far, and
- $t = \texttt{Before}$ ~t = \texttt{Before}~ if we have not started inverting brackets yet,
- $t = \texttt{Invert}$ ~t = \texttt{Invert}~ if we are currently inverting brackets, and
- $t = \texttt{After}$ ~t = \texttt{After}~ if we have stopped inverting brackets.
Note that $i-1-l$ ~i-1-l~ is the number of right brackets we've seen so far.
Base case: $dp(n+1, l, t) = \texttt{true}$ ~dp(n+1, l, t) = \texttt{true}~ iff $l = (n+1)-1-l$ ~l = (n+1)-1-l~.
Recurrence: $\displaystyle dp(i, l, t) = \begin{cases} \texttt{false} & \text{if }l < i-1-l \\ \\ \begin{align*}&(t = \texttt{Before} \land dp(i, l, \texttt{Invert})) \\ &\lor (t = \texttt{Invert} \land dp(i, l, \texttt{After})) \\ &\lor dp(i+1, l+L(i, t), t)\end{align*} & \text{otherwise} \end{cases}$ where $\displaystyle L(i, t) = \begin{cases} 1 & \text{if }s_i = \texttt{(}\text{ and }t \ne \texttt{Invert} \\ 1 & \text{if }s_i = \texttt{)}\text{ and }t = \texttt{Invert} \\ 0 & \text{otherwise} \end{cases}$
Answer is $dp(1, 0, \texttt{Before})$ ~dp(1, 0, \texttt{Before})~.
Can be computed in $\mathcal O(n^2)$ ~\mathcal O(n^2)~ using dynamic programming.

Comments

There are no comments at the moment.