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