Help in dp with bitmask .

Правка en5, от sober_phoenix, 2021-05-05 10:06:58

So I was trying to solve the problem 16E - Рыбы 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 probability of having the fishes represented by mask i.
initially all fishes are alive hence dp((1<<n)-1) = 1 i.e dp(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 .

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский sober_phoenix 2021-05-05 10:06:58 18
en4 Английский sober_phoenix 2021-05-05 10:03:53 2 Tiny change: 'e probabiltiy of havin' -> 'e probability of havin'
en3 Английский sober_phoenix 2021-05-05 10:02:25 29
en2 Английский sober_phoenix 2021-05-05 10:00:04 6 Tiny change: 'trying to the probl' -> 'trying to solve the probl'
en1 Английский sober_phoenix 2021-05-05 09:58:52 991 Initial revision (published)