You are not logged in. Please login at www.codechef.com to post your questions!

×

MCO16106 - Editorial

PROBLEM LINK:

Practice Contest

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.

RELATED PROBLEMS:

asked 13 Nov '16, 21:38

zscoder's gravatar image

6★zscoder
62813
accept rate: 6%

edited 13 Jan '17, 15:17

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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