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

×

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

svineet's gravatar image

3★svineet
362410
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★

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.

link

answered 25 Oct '16, 02:24

vivek1_007's gravatar image

5★vivek1_007
7025
accept rate: 0%

edited 25 Oct '16, 02:45

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) pankajkhan5★
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,212
×427

question asked: 25 Oct '16, 00:01

question was seen: 1,068 times

last updated: 04 May '18, 00:54