### atlasworld's blog

By atlasworld, history, 2 years ago,

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 ?

• -3

 » 2 years ago, # |   0 It can be solved with dp + bitmasks I think...This might help you :)
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 i got thistrying to understand it..
•  » » » 2 years ago, # ^ |   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.
•  » » » » 2 years ago, # ^ | ← 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<
•  » » » » » 4 weeks ago, # ^ |   0 can you explain how the conditional probability formula is derived ?
 » 2 years ago, # | ← Rev. 2 →   0 Here is my editorial. I hope it helps. :)
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 u r great ... Thanks !
•  » » 4 weeks ago, # ^ |   0 thank you !