×

PALLIND - Editorial

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

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)$.

Tester's solution can be found here.

Editorialist's solution can be found here.

This question is marked "community wiki".

3★bipin2
3.1k254671
accept rate: 8%

14.9k11856

 0 Hey @bipin2, I would like to know why is expected value summation of f(i) ? Should not it be summation of i*f(i)? answered 31 May, 22:30 2★milanj1 21●3 accept rate: 0% 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? (01 Jun, 01:02) milanj12★ @vijju123 any suggestions? (10 Jul, 22:17) milanj12★ 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. (11 Jul, 00:57) 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 (11 Jul, 15:28) milanj12★ 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. (11 Jul, 18:37) he is right I guess.. let me find a passed solution to confirm... (11 Jul, 19:29) 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)}$ (11 Jul, 19:30) he subtracted last term when n is even... https://www.codechef.com/viewsolution/19170881 (11 Jul, 19:35) 1 @l_returns Thanks for the help :D , @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 (15 Jul, 13:50) milanj12★ 1 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. (15 Jul, 21:30) 1 welcome @milanj1 :D (15 Jul, 21:58) 1 done @vijju123 (15 Jul, 21:58) 1 Thanks @l_returns (16 Jul, 02:23) np :) @vijju123 (16 Jul, 11:33) showing 5 of 14 show all
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,130
×112
×97
×36
×16