×

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

 0 I have read the editorial but didn't understand the proof. Can someone please explain the proof! asked 01 Feb '18, 21:42 2★pk301 627●10 accept rate: 16%

 0 http://codeforces.com/blog/entry/57420?#comment-410676 Go through this comment. His approach is the best. answered 01 Feb '18, 22:17 319●1●10 accept rate: 5%
 0 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) answered 01 Feb '18, 23:27 1.6k●2●9 accept rate: 23%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,738
×688

question asked: 01 Feb '18, 21:42

question was seen: 385 times

last updated: 01 Feb '18, 23:27