PROBLEM LINK:Setter: Bogdan Ciobanu DIFFICULTY:EasyMedium 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
EXPLANATIONLet 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*SS$ valid strings. Things become interesting now. See, For all these strings, suppose we append one more character, we get $S*(S*SS)$ 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 nonpalindrome prefix up to length $2$. So, the only way any string from these shall be nonvalid 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 nonpalindrome strings of length $\lceil x/2 \rceil$ which is $S*SS$ for $x = 3$ So, Number of valid strings of length $3$ is $S*(S*SS)  (S*SS)$. Assuming we know the number of valid strings of length $x1$ 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[x1]*Scnt[\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 inclusionexculsion with backtracking which works for $N \leq 50$ only. You may find it for practice if you wish to. :P Time ComplexityTime complexity is $O(N)$ per test case. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 13 Dec '18, 15:05
