DP Workaround 
Difference between en11 and en12, changed 4 character(s)
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↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en12 English AnasAbbas 2018-02-14 23:25:24 4 (published)
en11 English AnasAbbas 2018-02-14 23:23:03 6
en10 English AnasAbbas 2018-02-14 23:20:24 20
en9 English AnasAbbas 2018-02-14 23:17:47 32
en8 English AnasAbbas 2018-02-14 23:14:46 6 Tiny change: 'd bracket complexity' -> 'd bracket `\n\n`complexity'
en7 English AnasAbbas 2018-02-14 23:13:49 3 Tiny change: 'd bracket ---complexity' -> 'd bracket complexity'
en6 English AnasAbbas 2018-02-14 23:12:51 90
en5 English AnasAbbas 2018-02-14 23:07:57 2276
en4 English AnasAbbas 2018-02-14 21:50:47 22 Tiny change: '79276]\n\n\n\n' -> '79276]\n\n~~~~~\nint x,y\n~~~~~\n\n\n\n\n\n'
en3 English AnasAbbas 2018-02-14 21:50:17 29 Tiny change: '79276]\n\n\n\n' -> '79276]\n\n~~~~~\nint x,y\n~~~~~\n\n\n\n\n\n'
en2 English AnasAbbas 2018-02-14 21:49:40 21
en1 English AnasAbbas 2018-02-14 21:46:53 265 Initial revision (saved to drafts)