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?