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 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 .
I will be checking your approach in a while, but I can explain you how I solved this one.
You need to calculate the probability of fish surviving. So, we can better calculate the probability of a fish getting eaten.
Let's create a dp state this way, $$$dp[i][mask]$$$ will represent the probability of fish number $$$i$$$ getting eaten by the last day if the starting state of our pond is represented by $$$mask$$$.
Now, we can choose which fish dies on the first day (among the fishes already present in the pond) and get the probability of the fish $$$i$$$ dying for a pond configuration which has one fish less than the previous one.
Let $$$p[i][mask]$$$ denote the probability of fish $$$i$$$ getting eaten on the very first day if the configuration of pond is represented by $$$mask$$$ (you can calculate it separately).
Dp transitions can be written in ..
If the fish number $$$j$$$ is dying on the first day ($$$j$$$ may be equal to $$$i$$$), then the dp transition can be written as $$$dp[i][mask] = dp[i][mask] + dp[i][mask\oplus 2^{j-1}]\cdot p[j][mask]$$$.
Time complexity would be $$$O(n^2\cdot 2^n)$$$.
Solution for reference.
Actually your method is way better and fast. It is compressing all the rows, of my above mentioned method and eventually reducing the time complexity.
Your dp state is accurate but I think your transitions might have some problems. If calculate the probability of a fish $$$i$$$ dying on the very first day in a pond configuration represented by $$$mask$$$ as $$$p[i][mask]$$$ (please reply if stuck at this), then the dp transitions in your approach will be simpler and faster.
The value of $$$dp[2^n-1]$$$ will be 1, since this state is the initial state. For any state $$$mask$$$, you choose the fish that has to die. Let's say fish number $$$j$$$ dies on the first day. Now you have reached a new state $$$mask\oplus 2^{j-1}$$$, so you can add the probability by which you have reached this state to it's dp
$$$dp[mask] = dp[mask] + dp[mask\oplus 2^{j-1}]*p[j][mask]$$$.
Time complexity will be $$$O(n\cdot 2^n)$$$. Cheers!!!
Solution for reference.
Nice problem!