Hi,

I thought may be a dp solution is possible.

I have a solution but it does not work, any hint on how to apply dp.

Two lottery game. (div2 500pt) srm 418.

Thanks.

P.S : I can share my code, if needed, i used a dp[33][33][33][33] array.

I thought may be a dp solution is possible.

I have a solution but it does not work, any hint on how to apply dp.

Two lottery game. (div2 500pt) srm 418.

Thanks.

P.S : I can share my code, if needed, i used a dp[33][33][33][33] array.

n][m_{1}][m_{2}][k] is answer for the problem "what is probability, ifnnumbers remained, we need to selectm_{1}of them, lotteryholder should selectm_{2}of them and we win if at leastknumbers will be selected".For the first number we have four states, and each of them have fixed probability. So, we have four transitions to different states and solution in

O(nm^{2}k)Same as what I thought, can you give the exact recurrence relation please (mine is definitely faulty).

========here it is======================

int ii = i;

solve(ii,a,b,q) = (1.0/(n-ii))*(1.0/(n-ii))*solve(i+1, a-1, b-1, q-1) +

(1.0/(n - ii))*(1.0 - 1.0/(n-ii))*solve(i+1,a-1, b, q) +

(1.0/(n - ii))*(1.0 - 1.0/(n-ii))*solve(i+1,a, b-1, q) +

(1.0 - 1.0/(n-ii))*(1.0 - 1.0/(n-ii))*solve(i+1,a,b,q);

Correct one is , if we select

melements ofn, because each element can be selected equiprobably.Can anyone provide the exact recurrence, I am still not able to guess it.

P.S : got the relation, as yeputons said, it will be:

int ii = i;

double ret = ((double)a/(n-ii))*((double)b/(n-ii))*solve(i+1, a-1, b-1, q-1) +

((double)a/(n - ii))*(1.0 - (double)b/(n-ii))*solve(i+1,a-1, b, q) +

((double)b/(n - ii))*(1.0 - (double)a/(n-ii))*solve(i+1,a, b-1, q) +

(1.0 - (double)a/(n-ii))*(1.0 - (double)b/(n-ii))*solve(i+1,a,b,q);

(Accepted at topcoder)

I thought the complexity would be n*m*m*k .

But I can't understand why my code is taking 10^8 iterations for n=15, m=7, k= 7.

Here is the code

Please try and analyse the time complexity.

P.S.: Found the mistake, I used if(dp[][][][]>0) return dp[][][][]. but it sud be">=".