atlasworld's blog

Problem 16E codeforces
By atlasworld, history, 6 years ago, In English

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 ?

Tags #dp
  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

This might help you :)

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

    i got this

    trying to understand it..

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can you explain how the conditional probability formula is derived ?

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

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

→ Reply