Блог пользователя mkagenius

Can it be solved by dp,( topcoder editorial only suggested brute force).
Автор mkagenius, 12 лет назад, По-английски
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.
Теги dp
  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 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)
→ Ответить
  • »
    »
    12 лет назад, # ^ |
    ← 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);

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +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.
      → Ответить
»
12 лет назад, # |
← 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)

→ Ответить
»
12 лет назад, # |
← 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 code

Please try and analyse the time complexity.


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


→ Ответить