You are not logged in. Please login at www.codechef.com to post your questions!

×

PALLIND - Editorial

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.

This question is marked "community wiki".

asked 04 May, 12:18

bipin2's gravatar image

3★bipin2
3.1k254671
accept rate: 8%

edited 18 hours ago

vijju123's gravatar image

4★vijju123 ♦
13.8k11138


Should not the expected value be \sum_{i=1}^{i=n} f(i)

link

answered 31 May, 18:59

milanj1's gravatar image

3★milanj1
02
accept rate: 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)?

link

answered 31 May, 22:30

milanj1's gravatar image

3★milanj1
02
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) milanj13★

@vijju123 any suggestions?

(10 Jul, 22:17) milanj13★

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) vijju123 ♦4★

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) milanj13★

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) vijju123 ♦4★

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

(11 Jul, 19:29) l_returns4★

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) l_returns4★

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

(11 Jul, 19:35) l_returns4★
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

(yesterday) milanj13★
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.

(18 hours ago) vijju123 ♦4★
1

welcome @milanj1 :D

(18 hours ago) l_returns4★
1
(18 hours ago) l_returns4★
1

Thanks @l_returns

(14 hours ago) vijju123 ♦4★

np :) @vijju123

(4 hours ago) l_returns4★
showing 5 of 14 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×14,435
×102
×82
×36
×16

question asked: 04 May, 12:18

question was seen: 465 times

last updated: 4 hours ago