IPL: ZCO 2014 Dynamic Programming question


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?

1 Like

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.

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.

1 Like

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?

1 Like


3 2 1 1 2 3 1 3 2 1