×

# [Unofficial Editorial] PALIND from LoC April 2018

 2 Mathematical explanation The points (or gain) for each win is $X_l=1$ where $l$ is the length of the String. (Points for loss is $0$). Expectation is the weighted sum of the points, the weights being the probability of each event. Precisely, the expected number of points for $N$-length palindrome is $E_N=\sum_{i=1}^{N} P_iX_i=\sum_{i=1}^NP_i$ , where $P_i$ is the probability to get the string with length=$i$ as a palindrome. So we have to calculate $P_l$. Consider a string of length $l$. The sample space is of size $26^l$ as we have 26 character choices for every position. If $l$ is odd, then number of palindromes of length $l$ is $26^{l+1\over 2}$ [Just decide the characters of the positions $1,2,\dots, {l+1\over 2}$ and the remainder spaces are filled symmetrically]. If $l$ is even, then it is enought to fill the positions $1,2,\dots,l/2$ and fill the remainder symmetrically to get palindrome. So we have $P_k= \left\{{26^{1-k\over 2}, 2\not|k \\ 26^{-{k\over 2}},2|k} \right.$ So, we observe that $P_k=26^{-\left\lfloor {k\over 2} \right\rfloor }$ $\mathbb{1:}\\E_N=P_1+P_2+\dots +P_N=\left\{ {1+2\left(26^{-1}+26^{-2}+\dots+26^{-\left\lfloor {k\over 2} \right\rfloor }\right), \textrm{ if }2\not|N \\ 1+2\left(26^{-1}+26^{-2}+\dots+26^{-\left\lfloor {k\over 2} \right\rfloor+1}\right)+26^{-\left\lfloor {k\over 2} \right\rfloor }, \textrm{ if } 2|N}\right.$ Let $x=\lfloor k/2 \rfloor$. After simplyfying we will have, $\mathbb{2:}\\E_N=\left\{ {1+2\cdot\frac{26^x-1}{26^x\cdot 25}, \textrm{ if }2\not|N \\ 1+2\cdot\frac{26^x-1}{26^x\cdot 25}-\frac{1}{26^x}, \textrm{ if }2|N} \right.$ To compute the inverses, we have to use Fermat's little theorem: $a^{p-1}\equiv 1\pmod p\forall a\in \mathbb{N}, (a,p)=1$ So we will have the two parts of expression $(2)$ as congruent to $\left(1+2\cdot(26^x-1)\cdot25^{p-2}\cdot26^{p-1-x}\right)\pmod p$ and $\left(1+2\cdot(26^x-1)\cdot25^{m-2}\cdot26^{m-1-x}-26^{p-1-x}\right)\pmod p$ Coding To use make the above computation faster, use the modular exponentiation. This is suitable as $10^9+7$ is prime. Here goes the code for 50 points wherein the computation has been done with the expression labelled as $1$: Partial Here goes the code for 100 points using simplified expression labelled as $2$: Full asked 02 May '18, 21:35 51●4 accept rate: 0% 15.2k●1●18●60
 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,498
×868
×626
×240
×153
×105
×55
×36

question asked: 02 May '18, 21:35

question was seen: 224 times

last updated: 03 May '18, 21:48