mkagenius's blog

Can it be solved by dp,( topcoder editorial only suggested brute force).
By mkagenius, 13 years ago, In English
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.
Tags dp
  • Vote: I like it
  • +16
  • Vote: I do not like it

»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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)
→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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);

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      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.
      → Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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)

→ Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ">=" .


→ Reply