Need help with UVA — 10218 — Let's Dance

Revision en4, by Bekh, 2019-02-12 20:48:25

Hello,

I know and already got AC with other, 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)

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?

#### History

Revisions

Rev. Lang. By When Δ Comment
en5 Bekh 2019-02-12 20:54:52 17 Tiny change: 'with other, but I wa' -> 'with other neater solutions, but I wa'
en4 Bekh 2019-02-12 20:48:25 9
en3 Bekh 2019-02-12 20:47:36 2 Tiny change: 'proach: \n * i is ' -> 'proach: \n\n * i is '
en2 Bekh 2019-02-12 20:47:19 26
en1 Bekh 2019-02-12 20:46:16 1279 Initial revision (published)