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 lenth 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 dp2[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] = dp2[i][j]. Can someone help?
If the above statement was not clear, see the following example:
Consider dp2[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 dp2[4][2]
