×

# SFXPAL - EDITORIAL

Setter: Bogdan Ciobanu
Tester: Misha Chorniy
Editorialist: Taranpreet Singh

Easy-Medium

# PREREQUISITES:

Combinatorics, Modular Arithmetic.

# PROBLEM:

Given three integers $N$, $S$ and $M$, print the number of valid strings of length $N$ using an alphabet set of size $S$. A valid string is a string whose suffices of size greater than 1 are not a palindrome. Print this answer modulo $M$.

# QUICK EXPLANATION

• Build the number of non-palindrome strings of length $N$ from small to large.
• If the number of non-palindrome strings of length $i$ is given by $cnt[i]$, then $cnt[i] = cnt[i-1]*S-cnt[\lceil i/2 \rceil]$. Just calculate this for all $1 \leq x \leq N$ modulo $M$.

# EXPLANATION

Let us reverse the strings. It is easy to see that answer remains the same. Now, we have to compute the number of strings for which none of the prefixes of length greater than 1 is a palindrome.

Considering strings of length $1$, we have a total of $S$ different strings.

Considering strings of length $2$, we can have $S*S$ different strings, out of which there are $S$ strings having a prefix of length 2, which is a palindrome. So, we have $S*S-S$ valid strings.

Things become interesting now. See, For all these strings, suppose we append one more character, we get $S*(S*S-S)$ different strings of length $3$. Let us try to find out how many from these are valid.

See, all these string of length $3$ have a non-palindrome prefix up to length $2$. So, the only way any string from these shall be non-valid is when the string is a palindrome of length $3$. The number of palindrome strings of length $x$ we can have in the set is same as the number of non-palindrome strings of length $\lceil x/2 \rceil$ which is $S*S-S$ for $x = 3$ So, Number of valid strings of length $3$ is $S*(S*S-S) - (S*S-S)$.

Assuming we know the number of valid strings of length $x-1$ and length $\lceil x/2 \rceil$ we can find the number of valid strings of length $x$. This gives us a linear time solution, to sequentially compute valid strings of length $x$ denoted by $cnt[x]$ using recurrence $cnt[x] = cnt[x-1]*S-cnt[\lceil x/2 \rceil]$. All computations to be done modulo $M$.

A common mistake is to subtract $S^{\lceil x/2 \rceil}$ when asked to count the number of palindrome strings of length $x$. But here, the strings in the set have the property that none of the string is having any prefix being a palindrome. So, It makes sense to count only those strings whose any other prefix is not a palindrome, which is the same as $cnt[\lceil x/2 \rceil]$.

For the people on lookout of a different solution, there also exist another solution using some inclusion-exculsion with backtracking which works for $N \leq 50$ only. You may find it for practice if you wish to. :P

# Time Complexity

Time complexity is $O(N)$ per test case.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

3.9k2791
accept rate: 22%

19.8k350498541

 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:

×1,668
×877
×649
×124
×24
×4

question asked: 13 Dec '18, 15:05

question was seen: 226 times

last updated: 20 Dec '18, 12:50