Linearity of Expectation!

Правка en2, от quid_ditch, 2018-10-10 15:33:47

Hello Everyone, I was solving this problem: 722E][PROBLEM: - Исследовательский зонд. I was able to solve this by counting the number of paths that pass through the 0, 1, 2 and so on anomalies along with the sum of anomalies of each path. But I am wondering whether this problem can be solved using the lemma of linearity of expectation (LOE). LOE is quite trivial on 3000 * 3000 grid. But how to do LOE when size of grid is 1<=n,m<=1e5.

Thanks in advance!

Теги probabililty, linearity of expectation, #combinatorics

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский quid_ditch 2018-10-10 15:33:47 13 Tiny change: 'ved using linearity' -> 'ved using the lemma of linearity'
en1 Английский quid_ditch 2018-10-10 14:57:46 463 Initial revision (published)