PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
EASY-MEDIUM
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 polynomial-time 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.