Hello,↵
↵
Here's the problem link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1159↵
↵
I know and already got AC with other neater solutions, but I was trying various dp states/approaches for practice. I wanted to know what I am missing in this dp approach since I'm getting a bit lower value than the sample output (0.5012511 instead of 0.5002286)↵
↵
Solution link: https://ideone.com/AjdoVF↵
↵
approach: ↵
↵
* i is zero based↵
↵
Dp definition:↵
↵
* dp[i][rem] is probability to get a final even 'usedCandy' count in range [i, m) using 'rem' candies such that usedCandy = totalCandies — rem↵
↵
base case:↵
↵
* at i == m, return isEven(usedCandy)↵
↵
transition:↵
↵
* at each [i][rem], if 'tk' is amount given to man 'i'. 'tk' is in [0, rem]↵
↵
* answer = Summation for all 'tk' in [0, rem] -> P(man 'i' getting exactly tk candies) * dp[i + 1][rem — tk]↵
↵
* P(a man getting exactly 'tk' candies) having 'rem' candies in total can be found through binomial theorom C[rem][tk] * p^tk↵
q^(rem — tk) such that p is probability for↵
↵
* a person to get a single candy = 1/(m+w) and q = 1 — p↵
↵
If something is not clear with my solution, please ask.↵
Where am I going wrong with this dp?
↵
Here's the problem link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1159↵
↵
I know and already got AC with other neater solutions, but I was trying various dp states/approaches for practice. I wanted to know what I am missing in this dp approach since I'm getting a bit lower value than the sample output (0.5012511 instead of 0.5002286)↵
↵
Solution link: https://ideone.com/AjdoVF↵
↵
approach: ↵
↵
* i is zero based↵
↵
Dp definition:↵
↵
* dp[i][rem] is probability to get a final even 'usedCandy' count in range [i, m) using 'rem' candies such that usedCandy = totalCandies — rem↵
↵
base case:↵
↵
* at i == m, return isEven(usedCandy)↵
↵
transition:↵
↵
* at each [i][rem], if 'tk' is amount given to man 'i'. 'tk' is in [0, rem]↵
↵
* answer = Summation for all 'tk' in [0, rem] -> P(man 'i' getting exactly tk candies) * dp[i + 1][rem — tk]↵
↵
* P(a man getting exactly 'tk' candies) having 'rem' candies in total can be found through binomial theorom C[rem][tk] * p^tk↵
q^(rem — tk) such that p is probability for↵
↵
* a person to get a single candy = 1/(m+w) and q = 1 — p↵
↵
If something is not clear with my solution, please ask.↵
Where am I going wrong with this dp?
