Help in dp with bitmask .

Revision en3, by sober_phoenix, 2021-05-05 10:02:25

So I was trying to solve the problem 16E - Fish with push dp. However it's failing locally. Can you please help me figure out where is this going wrong ? Submission : 115175573

main idea

dp(i) — denotes the probabiltiy of having the fishes represented by mask i.
initially all fishes are alive hence dp((1<<n)-1{111...(n times)}) = 1 , now from each state i, next day, it can go to a state i^(1<<j) , for such a j for which j-th bit is turned on . i.e j-th fish is alive on the current day in the pond. probability of going to such a state will be given by —

let , cnt be the count of fish alive in that pond on the current day then probability to go mentioned state will be,
prob_sum = a(k1 , j)/C(cnt,2) + a(k2,j)/C(cnt,2) + ..... such that all k are the set bits of mask i and k!=j (i.e all alive fishes in the pond on current day except the j-th fish).

Can anyone help me find the wrong in my approach or code .

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English sober_phoenix 2021-05-05 10:06:58 18
en4 English sober_phoenix 2021-05-05 10:03:53 2 Tiny change: 'e probabiltiy of havin' -> 'e probability of havin'
en3 English sober_phoenix 2021-05-05 10:02:25 29
en2 English sober_phoenix 2021-05-05 10:00:04 6 Tiny change: 'trying to the probl' -> 'trying to solve the probl'
en1 English sober_phoenix 2021-05-05 09:58:52 991 Initial revision (published)