royappa's blog

By royappa, history, 7 years 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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
7 years 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?.