pronoobchamploser's blog

By pronoobchamploser, history, 7 months ago, In English

I recently started studying expected value and linearity of expectations. After studying some material I came across this problem: https://atcoder.jp/contests/dp/tasks/dp_j

Now, thinking in terms of linearity of expectation, my thought:

E(number of operations to eat N dishes) = E(number of operation to eat a1 dish) + E(number of operation to eat a2 dish) + ...

Then, E(number of operation to eat a1 dish) = a1 * E(number of operation to eat 1 dish)

Then, E(number of operation to eat 1 dish) = 1/n * 1 + (1 — 1/n)*(1/n) * 2 + ... = n

What's wrong with this interpretation? At what step am I misusing the linearity of expectation?

Read more »

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

By pronoobchamploser, history, 7 months ago, In English

Can somebody please explain how to solve this problem?

Editorial is horrible and it's impossible to understand how it's solved.

Thanks.

Read more »

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