Блог пользователя pronoobchamploser

Автор pronoobchamploser, история, 4 года назад, По-английски

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?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Автор pronoobchamploser, история, 4 года назад, По-английски

Can somebody please explain how to solve this problem?

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

Thanks.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится