[Unofficial Editorial] PALLIND from LOCAPR18

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

LOCAPR18

Problem:

PALLIND

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.

Solution:

Github link

Codechef

3 Likes

For various values of n the series for a is:
n=1
(1)
n=2
(26+1)
n=3
(26+1+1)
n=4
(26x26 + 26 + 26 + 1)
n=5
(26x26 + 26 + 26 + 1 +1)

Nice Editorial mate!

Thanks @devarshi09 :slight_smile: