help in http://codeforces.com/contest/918/problem/C

help
,
1

I have read the editorial but didn’t understand the proof. Can someone please explain the proof!

2

http://codeforces.com/blog/entry/57420?#comment-410676

Go through this comment. His approach is the best.

3

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[i-1] may be ‘(’ or ‘)’.

case 1: ‘(’

so we have a string like this validStringEndAti-2 ( )

So in this case dp[i][j]=dp[i-2][j-2]

case 2: ‘)’

So we have string like this validString ( ValidStringEndingWith) )

eg ()(()),()()(())

So in this case we see all possible lengths of i-1,and go to those position lets say x and see if s[x-1]==’(’,if it is then dp[i][j]=dp[i][j] or dp[x-2][j-(x-2)] (as now we can concatenate the strings ending at x-2)

(This would probably time out so u could try using some data structures or bit manipulation)