### mkagenius's blog

By mkagenius, 9 years ago,
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.

• +16

 » 9 years ago, # |   0 I have the following idea: d[n][m1][m2][k] is answer for the problem "what is probability, if n numbers remained, we need to select m1 of them, lotteryholder should select m2 of them and we win if at least k numbers 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(nm2k)
•  » » 9 years ago, # ^ | ← Rev. 2 →   0 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);
•  » » » 9 years ago, # ^ |   +8 You have incorrect formula for probability of element's selection.Correct one is , if we select m elements of n, because each element can be selected equiprobably.
 » 9 years ago, # | ← Rev. 2 →   0 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)
 » 9 years ago, # | ← Rev. 2 →   0 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 codePlease try and analyse the time complexity.P.S. : Found the mistake, I used if(dp[][][][] > 0) return dp[][][][]. but it sud be ">=" .