PROBLEM LINK:Author: Zi Song Yeoh DIFFICULTY:EASYMEDIUM PREREQUISITES:Dynamic Programming PROBLEM:Given a string $S$ which denotes a bracket sequence with brackets () and []. Some of the brackets are missing. Find the number of correct bracket sequences that can be formed. QUICK EXPLANATION:Let $dp[l][r]$ be the answer for the substring $[l..r)$. Then, we can compute the answer using a recursive dp. EXPLANATION:For the first subtask, there are no question marks. Thus, the task reduces to determining whether the given bracket sequence is valid. This is a simple task that can be achieved using a stack. If the current element is ( or [, we push it to the stack. If it is a ), we check if the character on top of the stack is (. If it is (, we pop it from the stack, otherwise, the sequence is not correct, and we output $0$. We can do a similar check for when the current letter is ]. This will pass subtask $1$. For the second subtask, $n$ (the length of $S$) is at most $10$. This makes the $O(4^{n} \cdot n)$ solution viable. We can iterate through all possible strings of length $10$ and for each string check whether it's possible. This is sufficient to solve subtask $2$. For the last subtask, $n \le 500$, so a polynomialtime solution is required. We'll again resort to Dynamic Programming. Let $dp[l][r]$ be the answer for the substring $[l, r)$ (this means we're considering the substring formed from the $l$th character to the $(r  1)$th character). We have $dp[l][l] = 1$ as the base case. Now, suppose we want to compute $dp[l][r]$. Consider the $l$th letter. We loop through all $l + 1 \le i < r$ and count the number of ways to match the $l$th bracket with the $i$th bracket. Then, we're left with two subproblems, the string $[l + 1, i)$ and $[i + 1, r)$, and we can multiply the result by $dp[l+1][i] \cdot dp[i+1][r]$ and sum the result for all $i$. Since we have $O(n^{2})$ states and each state takes $O(n)$ to compute, the complexity is $O(n^3)$, which works in the time limit. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's solution can be found here. RELATED PROBLEMS:asked 13 Nov '16, 21:38
