So I was trying to 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 that 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 that that 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 .