I have read the editorial but didn't understand the proof. Can someone please explain the proof! asked 01 Feb '18, 21:42

http://codeforces.com/blog/entry/57420?#comment410676 Go through this comment. His approach is the best. answered 01 Feb '18, 22:17

I dont know if it helps,but u could try it with dp. dp[i][j] denotes whether it is possible to have a valid substring ending at i of length j. dp[i][0]=true for all i Lets talk about recurrence: if(s[i]==')' or s[i]=='?'): then u can end with this i,now s[i1] may be '(' or ')'. case 1: '(' so we have a string like this validStringEndAti2 ( ) So in this case dp[i][j]=dp[i2][j2] case 2: ')' So we have string like this validString ( ValidStringEndingWith) ) eg ()(()),()()(()) So in this case we see all possible lengths of i1,and go to those position lets say x and see if s[x1]=='(',if it is then dp[i][j]=dp[i][j] or dp[x2][j(x2)] (as now we can concatenate the strings ending at x2) (This would probably time out so u could try using some data structures or bit manipulation) answered 01 Feb '18, 23:27
