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

×

[Unofficial Editorial] PALIND from LoC April 2018

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

codeup_nil123's gravatar image

3★codeup_nil123
514
accept rate: 0%

edited 03 May '18, 20:37

vijju123's gravatar image

4★vijju123 ♦♦
15.2k11860

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:

×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