PROBLEM LINK:
Author: Vaibhav Tulsyan
Tester: Aditya Paliwal
Editorialist: Aswin Ashok
DIFFICULTY:
EASY
PREREQUISITES:
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.
, 