You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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

asked 01 Feb '18, 21:42

pk301's gravatar image

2★pk301
62710
accept rate: 16%


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

Go through this comment. His approach is the best.

link

answered 01 Feb '18, 22:17

rohitthapliyal's gravatar image

3★rohitthapliyal
319110
accept rate: 5%

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)

link

answered 01 Feb '18, 23:27

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
accept rate: 23%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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