COOK53 Expectation problem [RRPLAYER]

Revision en1, by match, 2015-07-02 10:23:59

http://www.codechef.com/COOK53/problems/RRPLAYER

This is the problem link. I have one doubt here.

Although I agree with the states mentioned in the editorial. But, when I was trying to solve it on my own. I create the states as F(i,j) meaning i songs have not been played even once and j songs have been played atleast once. With this, I can have the following recurrence relations

These are some base cases.

f(0,i) = 0.0 //all songs have been played once. f(i,0) = [1 + f(n-1,1)]/i

Now, lets derive for other (i,j)

f(i,j) = [1 + f(i,j)]/j + [1 + f(i-1,j)]/i

f(i,j) = 1/i + 1/j + f(i,j)/j + f(i-1,j)/i

f(i,j)[1-1/j] = [i + j + j*f(i-1,j)]/(i*j)

f(i,j)*(j-1)/j = [i + j + j*f(i-1,j)]/(i*j)

Cancelling j from both sides on denominator

f(i,j) = [i + j + j*f(i-1,j)]/(i*(j-1)) //final recurrence relation

But if you see, this becomes undefined for f(i,1) because in denominator there is a term for (j-1). What am I missing here?

Tags codechef, cookoff

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English match 2015-07-02 10:23:59 1018 Initial revision (published)