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

Problem 16E codeforces
Автор atlasworld, история, 6 лет назад, По-английски

Anyone who solve problem 16E, can please share his ideas.There is no official solution of this round. link

in the announcement thread it is mentioned that it will be solved using state compression dp , but what is state compression dp and what will be the dp state for this question ?

Теги #dp
  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It can be solved with dp + bitmasks I think...

This might help you :)

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    i got this

    trying to understand it..

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      We iterate a variable called mask from 0 to (1 << n)-1 Suppose our current mask is i.

      Suppose it has x bits set.This means that those fishes with the corresponding bit set are already dead. The number of fish left alive would be n-x. Now, we iterate through the bits in the mask and check which bits are not set(which fish are still alive). Now we simulate a fight between two fishes alive,that is,we select two fishes randomly with equal probability. That probability(p) would be 1/(# of ways to select two fishes from n-x fishes).

      Let those selected fishes be x and y.

      If x wins, we update dp[mask|(1 << y)]+=dp[mask]*p*a[x][y].

      Similarly we update dp[mask|(1 << x)]+=dp[mask]*p*a[y][x].

      The required answer would be dp[~(1 << i)] for the ith fish.

      This solution takes O(n^2*2^n) time and I think it might pass under the given constraints.

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        yes , what you said , the same thing is conveyed in the above blog which i mentioned above...

        initially all fish are alive so we set dp[1<<n-1]=1

        now iterating for each state , we will take two loops for i and j such that i_th fish will eat the j_th one and we update the probability as

        dp[state^(1<<j)]+=dp[state]*arr[i][j]/((num)*(num-1)/2);

        actually the question is more about probability rather than dp ...

        it is a question of conditional probability , i think ..

        getting probability equation was tricky ..

        i submitted and it fit in time limit .. of 560ms

        Thanks for the explanation !!

        code

        → Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Here is my editorial. I hope it helps. :)

→ Ответить