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 ?

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

This might help you :)

i got this

trying to understand 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.

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

can you explain how the conditional probability formula is derived ?

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

u r great ... Thanks !

thank you !