Bekh's blog

By Bekh, history, 5 weeks 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?

Read more »

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

By Bekh, history, 7 months ago, In English,

Here's the problem : 227C - Flying Saucer Segments

In the editorial here: http://codeforces.com/blog/entry/5378?locale=en We ended up having F(n) = 3*(F(n-1) + 1) — 1 Could somebody please elaborate on how to get we got ((3^n) — 1) from the recurrence? Sorry if this is a newbie question I'm trying to learn more on the topic.

Read more »

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

By Bekh, history, 7 months ago, In English,

http://codeforces.com/blog/entry/14256 in D2-C.

I understood that for each x there is exactly 1 k. But how can I prove that for each K in [1, a] there always exists nice numbers for all remainders [1, b-1]? For instance if a = 3, b = 5. How to be so sure that for Each k {1, 2, 3} there will always be nice numbers with remainder values [1, b-1]

Read more »

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