sober_phoenix's blog

By sober_phoenix, history, 3 years ago, In English

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 .

  • Vote: I like it
  • -3
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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 ..

this way

Solution for reference.

»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

Check here.

Solution for reference.
Nice problem!