hello codeforces

this problem 917A - The Monster has only a greedy solution which is well explained in the editorial

however i want to introduce a Dynamic programming solution

O(N^4) DP solution : 34679276

Explanation :

`the boolean solve function finds out if a certain substring can be a valid sequence of brackets`

`if it finds a question mark it treats it like an open bracket then a closed bracket`

`complexity O(n^2)`

`the main function calls the solve function for every different substring which is nearly`

`N^2 substring`

`so the overall complexity is O(N^4)`

O(N^3) DP solution : 34680960

Explanation :

`like the previous solution the main function calls solve function n^2 times but this time`

`solve function is O(n^2) n times and the rest of the calls is O(1)`

Nearly O(N^2) Accepted DP solution : 35227974 i know that this solutions seems very weird compared to the previous solutions but actually it's doing the same thing efficiently Explanation:

`now we know that in the previous solutions solve(pos,nopen) goes to`

`states solve(pos+1,nopen+1),solve(pos+1,nopen-1)`

`if string[pos] was a question mark and solve(pos,nopen) goes to solve(pos+1,nopen+1)`

`if it was an open bracket`

`and solve(pos+1,nopen-1) if it was a closed bracket`

`now let's put all these states in an array`

`example :`

`if the input string was "((?)"`

`the array should contain:`

`[0] meaning solve(0,0)`

then

`[1] meaning solve(1,1)`

then

`[2] meaning solve(2,2)`

`[1,3] meaning solve(3,1) and solve(3,3)`

`[0,2] meaning solve(4,0) and solve(4,2)`

**notice that we don't need to save the first parameter in the array as all states has the same level**

`now we observe that if there's an open bracket we have to increase all array elements by 1 and -1`

`in case of closing`

`and in case of question mark all states is increased by 1 and new state is added which is`

`equal to first state -2`

**prove it for yourself on a sheet of paper**

`now after every iteration we only have to increment our answer if there's an element in the array =0`

hope you got it

important notes :

-please feel free to comment if you find any mistake in my blog

-i'm not really good at writing blogs so i'm sorry if you find bad styling or poor english

-i hope that this workaround help anyone optimizing similar DP solutions

-it took me around a month to come up with this solution and i really want to know if i'm doing problem solving efficiently

thanks

Auto comment: topic has been updated by AnasAbbas (previous revision, new revision, compare).