Bekh's blog

By Bekh, history, 5 years ago, In English

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?

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Bekh (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Bekh (previous revision, new revision, compare).

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

Here's the error in your code: Consider that we are at the i-th man with rem candies left. Since the first i men have already been distributed the candies and we will not give them any more candies so, the probability of the first i men getting a candy now is 0. So, we are effectively left now with (m - i) men and w women and the next candies can be distributed to them with equal probability. So, in the state dp[i][rem], the probability of success becomes p = 1.0 / ((m - i) + w). Make this change and you'll get AC.

BTW, I still don't get why are you doing if(ret == ret) return ret;. So, I used a visited array instead. Please explain that line.

Here's the updated code.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Oh, thank you. I've completely missed that!

    for the (ret == ret) part. I initially memset the dp array with (-1) this fills that memory chunk with all 1's (because the 2's complement representation of (-1) is all 1's). In double values, all 1's is defined as NaN (Not a Number). NaN's has some unusual properties, one of them is that NaN is not equal to any other value including itself. Checking (ret == ret) should return false for the initial state of the dp, otherwise for any other value it should return true.

    for more about NaN's: http://www.cs.technion.ac.il/users/yechiel/c++-faq/nan.html

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Well that's something interesting. Thanks :)

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        No, problem. Good luck!