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?
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,bbcontains three palindromic substrings instead of one. The two remaining substrings are accounted for, too, but separately, considering the events??=?band?? = b?.