Editorial Link

Problem C. Family Door and Brackets**Short Intro of Problem:** We are given a string *B* consisting of ( and ). We need to find pairs of strings (*A*, *C*) such that *A* + *B* + *C* becomes valid string. A valid string is one which is balanced i.e no of opening and closing brackets is same and also for no position, the prefix sum of number of '(' > ')'.

Let *dp*[*len*][*extra*] be the ways of arranging brackets such that the resultant length is *len* and no of '(' is greater than no of ')' .

Clearly *dp*[*len*][*extra*] = *dp*[*len* - 1][*extra* + 1] + *dp*[*len* - 1][*extra* - 1] as we can either place ')' or '(' at *len*^{th} position.

If *extra* = 0, then we can't place '(' at end so thats the edge case that we handle.

In the solution, as we select *c* length of prefix with *d* balance, we now need to add suffix of length (*m* - *n* - *c*) with balance (*d* + *b*), where *b* is balance of main input string.

But as we add suffix, this balance is opposite in nature. Earlier *dp*[*i*][*j*] meant length *i* and *j* **extra** opening brackets. Now while adding suffix, we need *dp*2[*i*][*j*] which represents length *i*, and *j* **less** opening brackets. Moreover, we have to consider only those ways where the number of closing brackets must never exceed *j* midway otherwise that would make the overall prefix balance negative and thus we will miscount.

The editorial doesn't proves how *dp*[*i*][*j*] = *dp*2[*i*][*j*]. Can someone help?

If the above statement was not clear, see the following example:

Consider *dp*2[4][2]. This should **not** contain the follwing sequence:

- )))(, Reason -> Though overall balance is 2, there exists a balance of 3( > 2)

So if we have added 2 extra opening brackets and plan to use the above sequence as a suffix thinking it gives a balance of 2 for nullification, it will make the prefix balance < 0 at some position and thus it should not be counted in*dp*2[4][2]