pronoobchamploser's blog

By pronoobchamploser, history, 10 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, 11 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