Brackets all over

#1

I am not getting how to use dp. This is same question
“Famil Door and Brackets” of Codeforces ,I saw editorial but didn’t get the intitution behind it. plz help me

#2

Hi @Bhawna

You can think of it as if you are given a sequence of brackets, first you should check the validity of these brackets eg: ())) - This is an incomplete sequence as number of opening and closing brackets are not same. And eg: ()() - This is a complete sequence. So now you have to make two different sequences which should balance the overall string a+s+b. So a can be independent or dependent on s or b and same applies to b. So you can make a dp to store the number by which the number of opening brackets are greater than the number of closing brackets till that index i. And then as stated in editorial you can add product of minimum balance dp and remaining balance dp to the answer.

Hope it Helps.

#3

  1. Calculate dpi, j : How many sequences of brackets of length i has balance j and intermediate balance never goes below zero (They form a prefix of a valid sequence of brackets).

  2. For the given sequence of length n calculate the resulting balance a and the minimum balance b.

  3. Try the length of the sequence added at the beginning c and its balance d. If - b ≤ d then add dpc, d × dpm - n - c, d + a to the answer.

Can u plz elaborate each point using example?

#4

Hi @Bhawna

Let dp[i][j] = number of bracket sequences of length i and balance j.
Let’s formulate a recurrence for dp[i][j]. To do that, consider a bracket sequence of length i and balance j.
There are two cases: It’s either the sequence ends with a ‘)’ or it ends with a ‘(’. Let’s consider these cases.

Case 1: Ends with ‘)’
Then if we remove that last bracket, the remaining sequence must have a balance of j + 1, because that last ‘)’ must have matched a ‘(’ and thus reduced the number of unmatched left brackets to j.
So we have dp[i][j] = dp[i — 1][j + 1] in this case.

Case 2: Ends with ‘(’
Then if we remove that last bracket, the remaining sequence must have a balance of j — 1, because that last ‘(’ matches nothing and only adds to the number of unmatched left brackets.
In this case, we have dp[i][j] = dp[i — 1][j — 1]

Since case 1 and case 2 are just partitions of dp[i][j], we combine them to get the total possibilities for dp[i][j]:
dp[i][j] = dp[i — 1][j + 1] + dp[i — 1][j — 1]

Hope it Helps.

#5

@Bhawna
Please mark your doubt as solved.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.