hello codeforces↵
↵
this problem [problem:917A] 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 : [submission: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 : [submission: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 : [submission: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↵
↵
↵
this problem [problem:917A] 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 : [submission: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 : [submission: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 : [submission: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↵
↵