×

# IPL: ZCO 2014 Dynamic Programming question

 1 1 PROBLEM So I framed a DP described by the following code: Link The subproblem I framed was that dp[i] is the most profit that one can get if he plays i-th match. If we play i-th match, then we can either Play (i-1)th match and not play the one before that, then use the best answer we have for dp[i-3] OR Don't play (i-1)th match and instead choose whatever was best (i-2) matches i.e dp[i-2] When we have filled the whole dp array we select the maximum element in the array. Three subtasks give AC for this but the rest 7 fail. What is wrong with the logic? Also on an unrelated note, what is the cutoff for ZCO usually? Whole 2 problems? How hard is it to get into IOITC? asked 25 Oct '16, 00:01 3★svineet 36●2●4●10 accept rate: 0% I looked up agnishom's answer and saw the solution, but I'm still not sure what is wrong with my solution that his solution covers. (25 Oct '16, 00:26) svineet3★

 2 Your program doesn't check all the cases. Your logic is partially correct.There exists a better,simpler and easily implemented DP solution for this. Here is the logic: dp(i,j) denotes the best optimal answer to the problem if we select the i th match with j more matches which can be selected consecutively. We will call max(dp(0,1),dp(1,1)) for the required optimal answer. dp(i,j) = a[i] + max( dp(i+1,0), dp(i+2,1), dp(i+3,1) ) // if j is 1. = a[i] + max( dp(i+2,1), dp(i+3,1) ) // if j is 0. Hope this helps you. Sorry, but i can't post the exact code. You have to do this by yourself. answered 25 Oct '16, 02:24 70●2●5 accept rate: 0% 1 Thanks for the answer, but I want the flaw in my code, not the correct answer. Could you please give me a test case where my code does not give the optimal answer? (25 Oct '16, 19:29) svineet3★ 10 3 2 1 1 2 3 1 3 2 1 (04 May '18, 00:54)
 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,212
×427

question asked: 25 Oct '16, 00:01

question was seen: 1,068 times

last updated: 04 May '18, 00:54