×

# MCO16106 - Editorial

Author: Zi Song Yeoh

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.

# RELATED PROBLEMS:

6★zscoder
62813
accept rate: 6%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,639
×2,167
×1,672
×2

question asked: 13 Nov '16, 21:38

question was seen: 721 times

last updated: 13 Jan '17, 15:17