SPOJ problem SQRBR

I’m trying to solve SQRBR using DP but I couldn’t find a recurrence relation any help is highly appreciated.

Nice problem. I initially solved it with an \mathcal{O}(n^3) approach, but then I Googled it to find this Quora answer by Raziman T.V., which has a better \mathcal{O}(n^2) solution. I’ll describe this approach below (with a few minor tweaks).

The recurrence used is f(i, j) which returns the number of valid bracket sequences from position 1 to i with j more opening brackets than closing brackets. For convenience let’s call the difference between opening and closing brackets simply the difference. If we are at position i and we need j more “[” than “]”, then we can obtain that by two ways.

  1. We put a “[” at position i to get a difference j. This means that there must have been a difference of j-1 upto position i-1.
  2. We put a “]” at position i to get a difference j. This implies that there must have been a difference of j+1 upto position i-1.

We are also given a set of positions s which must contain “[”. For such positions, option 2 is unavailable. For j<0 naturally f(i, j)=0 because we are proceeding from left to right and if we have more “]” than “[” we can never end up with a valid sequence. Again f(0,0)=1 as the empty sequence with difference 0 is valid. Also f(0,j) for j>0 is 0.

Putting all of this together,

f(i,j) = \begin{cases} 0 & \text{if } j<0 \;\;\text{or}\;\; i=0, j>0\\ 1 & \text{if } i=0, j=0 \\ f(i-1,j-1) & \text{if } i \text{ is in } s \\ f(i-1,j-1) + f(i-1,j+1) & \text{otherwise} \\ \end{cases}

The final answer will be f(2n,0) as 2n is the last position in our sequence and we want the sequence to be valid, so we need difference 0.
That’s the \mathcal{O}(n^2) solution, which is pretty smart actually.
And if you need some code for reference let me know :slight_smile:

4 Likes

Very well explained, I went through RAZIMAN TV post but it was difficult to interpret. Thank You!

Oops forgot to add that, fixed now!

1 Like

I coded it up and f(2n-1,0) wasn’t working then used f(2*n,0) and it works. Thank You!

1 Like

Nice work :smiley:

1 Like