royappa's blog

By royappa, history, 3 months ago, In English,

I solved Topcoder SRM 607 Div. 1 250 using Linearity of Expectation in the practice room.
https://community.topcoder.com/stat?c=problem_statement&pm=12964&rd=15840

I brushed up the rules about Linearity of Expectation (LoE). The proof is easy algebra and using it is also easy.

But I still don't understand WHY it works here.

In this problem, suppose the concatenated input is "??". It has 3 substrings: the first "?", second "?" and the whole string "??".

The solution just separately generates every substring, finds the probability that it is a palindrome, and adds it all up, so we get 1+1+(1/26) = 2.038. Fine.

But for "??" to be a palindrome requires the first and second substring "?" to be the same letter chosen for the "??". I mean, if "??" = "bb" then the first substring also has to be "b" and the last substring also has to be "b".

So why can we just add up the palindrome probability of each substring independently without considering its matching with the other substrings?

 
 
 
 

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

We may use the following intuition. When we consider the event ?? = bb, we add 1 (multiplied by its probability) to the answer. While in reality, bb contains three palindromic substrings instead of one. The two remaining substrings are accounted for, too, but separately, considering the events ?? = ?b and ?? = b?.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks!! That helps even though I still don't see fully, yet. What it's getting me to do is understand the event space generated by my code (?? generates 26*26 events on its own, and each ? generates 26 on its own) so I think I can work it out from there.