Note:This is my first editorial and i am still a noob in first year of my college so please forgive me for any mistakes.Also suggestions are welcome.
Contest link
Problem:
PRE-REQUISITES:
Basic Combinatronics, Basic Probability, Inverse Modulo, Fermat’s Little Theorem, Fast exponentiation
PROBLEM:
Bob has a string (S), which is initially empty. In one operation, he can select a lowercase character (a-z) uniformly at random and appends it to S. He then evaluates whether S is a palindrome or not; if it is, he gets 1 point.
Given that Bob performs N operations in total, find the expected no. of points Bob gets. It is guaranteed that the answer can always be represented as a rational number a/b
EXPLANATION:
- WE WILL DISCUSS THE SOLUTION WHICH FETCHES 100 POINTS
What we basically have to do is find number of palindromic strings in a string of size N. What we find is that if N is odd, number of such strings is 26^((N/2)+1) and 26^(N/2) if even.Let this be P.
Also number of all possible strings is 26^N.
Next thing is for a particular N expected value of palindromic string is P/((26)^N).
Next observation is that while constructing a string of size N we also have to take into consideration all string of size K (1<=K<=N).
Thus we get a series of the form
1+ 1/26 +1/26 + 1/(26^2)+ 1/(26^2) + 1/(26^3) + 1/(26^3) + 1/(26^4) + 1/(26^4) .... upto N terms.
The next task is to represent it in the form a/b.
To do this we first take a look at b
After adding the terms we find b is 26^X where X is higest power of 26 in the series.
Similarly we find a is something like
26^x +2.(26^(x-1))+....+(J).1
Where J is 1 if n is even else 2.
This can be represented as a sum of G.P. series with some constraints. Use little fermat’s along with fast exponentiation here in calculating the series sum.
Now we are left with (a/b)% 1000000007.
This can be calculated easily using little fermats theorem.
