PALLIND - Editorial

editorial
expected-value
locapr18
modular-arith
pallind

#1

PROBLEM LINK:

Practice
Contest

Author: Vaibhav Tulsyan
Tester: Aditya Paliwal
Editorialist: Aswin Ashok

DIFFICULTY:

EASY

PREREQUISITES:

Expected Value

Modular Arithmetic

MMI

PROBLEM:

A short and concise description of the problem statement.
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.

EXPLANATION:

Given an empty string, Bob randomly picks a character from ‘a’ to ‘z’
and appends to the string and every time he appends he checks if the resultant
string is a palindrome, if yes he get one point for that append operation. Bob does
n such append operations and we are asked to find the expected value of the total
number of points he gets. We have to find the answer modulo 10^9 + 7.

SOLUTION:

It is the sum of expected number of palindromes of length i, for i=1 to n.
We can get the probability of getting a palindrome of length i by fixing the first i/2
characters and let the second i/2 characters be the mirror image of the first. For
example: A string of length 4 will be palindromic if we fix its first two characters
and let the next two be the mirror of the first two and for a String of length 5 we
can fix the first three characters and let the last two characters be the mirror of
first two. This works out to be 26^{ceil (i/2)}/26^i which is f(i)= 1/26^{floor(i/2)}.
This is because ceil(i/2) + floor(i/2) = i (for all integers)

The final answer is \sum_{i=1}^{i=n} f(i)

This becomes:
1 + 1/26 + 1/26 + 1/26^2 + 1/26^2 + …..+1/26^{floor(n/2}

We can notice same terms repeating so we can re write the series

1 + 2(1/26 + 1/26^2 + 1/26^3 + . . . + 1/26^{floor(n/2)}) if n is odd

1 + 2(1/26 + 1/26^2 + 1/26^3 + . . . + 1/26^{floor(n/2)}) - 1/26^{(n/2)} if n is even

Since n is very large we cannot evaluate every term. We can notice that (1/26 + 1/26^2 + .. ) is in GP so we can use sum of GP formula and Modular Multiplicative
inverse to get the final answer.

TIME COMPLEXITY

To find sum of GP we have to find Modular Multiplicative inverse of the
denominator in the sum of GP formula, which can be found out using Modular
Exponentiation and the time taken for it is O(logn) and last term if n is even can
also be found out it O(logn), Multiplication and addition can be performed in O(1)
so it can be done in O(logn). Since there are t cases per file the overall complexity
is O(tlogn).

SOLUTIONS LINK:

Tester’s solution can be found here.

Editorialist’s solution can be found here.


#2

Hey @bipin2, I would like to know why is expected value summation of f(i) ?
Should not it be summation of i*f(i)?


#3

1+2(1/26+1/262+1/263+…+1/26floor(n/2))+1/26(n/2) if n is even

And in this there should not there be a minus sign with the last term?


#4

@vijju123 any suggestions?


#5

He gains only 1 point, hence its summation of f(i). E(x) = Summation of (x* p(x)). Since he gains only 1 point, x=1.


#6

Thanks a lot @vijju123

please also make correction in the editorial replace this

1+2(1/26+1/262+1/263+…+1/26floor(n/2))+1/26(n/2) if n is even

with

1+2(1/26+1/262+1/263+…+1/26floor(n/2)) - 1/26(n/2) if n is even


#7

Can you give me a solution using your formula to prove it passes? I cannot just edit the editorial’s formula, esp if it can be wrong. @taran_1407 @aryanc403 @l_returns , please help here.


#8

he is right I guess… let me find a passed solution to confirm…


#9

which can also be seen as if n is even ,
floor(n/2)=n/2
so as per editorial a term can come for twice at max… not thrice…
also for n=4
= 1 + 1/26 + 1/26 + 1/26^2
= 1 + 2(1/26 + 1/26^2) - 1/26^2
= 1 + 2(1/26 + 1/26^{floor(4/2)} ) - 1/26^{4/2}
=1 + 2(1/26 + 1/26^{floor(n/2)}) - 1/26^{(n/2)}


#10

he subtracted last term when n is even… https://www.codechef.com/viewsolution/19170881


#11

@l_returns Thanks for the help :smiley: , @vijju123 We can say the solution is not correct because it is a summation from 1 to n, so total n terms,

in the given expression for n=even there are n+2 terms


#12

I am so sorry, I edited it out earlier a few days earlier but it seems it didnt got registered due to my unstable net. i have edited it out now. Please confirm.


#13

welcome @milanj1 :smiley:


#14

done @vijju123


#15

Thanks @l_returns


#16

np :slight_smile: @vijju123