IPL(ZCO 2014)

general
1

Someone please suggest a way to precede these kind of problems! I am a lot interested but a beginner programmer! (knows only basics)

http://www.iarcs.org.in/inoi/2014/zco2014/zco2014-2b.php

2

If you are new to these types of problems, refer this link.
http://www.iarcs.org.in/inoi/online-study-material/topics/dp.php

3

See the question is simple dp

Given
n matches you a(1),a(2),a(3)…a(n)

So now what will be the total number of selection of matches a player can play 2^n.

However we have one more constraint that is a player can’t play 3 matches in a row thus it is clear that brute force won’t be suffice and would definitely time out… Hence what we can do is analyze the problem on smaller values of n (actually this is the first step one should follow when dealing with such problems)

So lets for n=4
5 6 3 10

So now what can we do
We can pick first match that is 5
Then second that is 6 and then 4rth that is 10 getting total of 21. Getting any hints want am I doing!

Lets observe the solution
Given a(1),a(2)…a(n)
So there will be two types of solution one having a(1) and other not having a(1)

So if write a function
F(a,b) where a is the match under our observation (we would be iterating the matches one by one) and b the left matches we can continuously play.

So if we take a(1) we can play only one match more in continuity (no 3 matches in a row)

Hence after taking a(1) we can either take a(2) or again start the problem starting from a(3)

So the function
f(a,b)=max( f(a+1,b-1)+matchfeesof(a),f(a+2,b))

Now here maximum value of b=2 hence time complexity would be 2a ie suffice. We are taking b=2 because we can play at most 2 matches in a row

Let’s take example
F(1,2) for matches 5,4,10,7
F(1,2)=max(f(2,1)+5,f(3,2))

So now keep on doing like this for all f(a,b) needed and obtain the answer… Note f(a,0)=0 because if we can play 0 matches in continuity then value if also 0

Hope it clears your problem
Well that was hell lot but I experienced problems with dp too hence I am helping you with such a large explanation.

Phew

Hope it help.

Happy coding

4

thanks a lot man! got the logic…
But could you please send me the complete code for the solution of this problem. @japoorv

5

Buddy add me on Google plus and I would help you to write the code

japoorv0@gmail.com

6

Okay here’s the solution:
http://discuss.codechef.com/questions/57151/zco-dynamic-programming-problems

Regarding implementation:
Keep Fees[0]=0 and store the numbers from 1 to N
The final solution would be stored at

      Best[0][0]