IPL: ZCO 2014 Dynamic Programming question

dynamic-programming
zco

#1

PROBLEM

So I framed a DP described by the following code: Link

The subproblem I framed was that dp* 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?


#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* + max( dp(i+1,0), dp(i+2,1), dp(i+3,1) ) // if j is 1.

= a* + 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.


#3

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.


#4

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?


#5

10

3 2 1 1 2 3 1 3 2 1