quid_ditch's blog

Linearity of Expectation!
By quid_ditch, history, 6 years ago, In English

Hello Everyone, I was solving this problem: 722E][PROBLEM: - Research Rover. 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!

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

What the hell do you mean "using linearity of expectation"? Linearity of expectation is not some specific algorithm, but just a generic lemma about probability distributions. In fact most solutions for an expected value problem probably use it, explicitly or implicitly.

You can't say "can I solve this problem with linearity of expectation" and expect people to understand what you mean. What's next, "can I solve this problem with for-loops"?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes this is what i am trying to ask for the problem. Sorry for my bad english.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by quid_ditch (previous revision, new revision, compare).

→ Reply