PROBLEM LINK:
Author: Kanstantsin Sokal
Tester: Pavel Sheftelevich
Editorialist: Pawel Kacprzak
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Palindromes
PROBLEM:
In this problem, for a given binary string S of length N, your task is to find the number of palindromic subsequences of S, which are exponential. A subsequence S_{i_1}, S_{i_2}, \ldots, S_{i_k} is exponential if and only if k \geq 1 and for all 1 \leq j < k we have i_j+1 = p \cdot i_j. Moreover, we say that p is the order of such a subsequence.
QUICK EXPLANATION:
For each 1 \leq i \leq N and 2 \leq p \leq N, generate all exponential subsequences of order p with at least 2 elements starting at index i. For each such subsequence, iterate over all its prefixes and for each one, check if it is a palindrome using a linear scan over its elements. Finally, add N to the result, because each subsequence of length 1, by the definition, forms an exponential palindrome and we have N such subsequences.
EXPLANATION:
SUBTASK 1
In the first subtask N is at most 20, so in order to solve the problem, we can simply generate all possible non-empty subsequences of S, and for each one, first check if it’s exponential and if it is, check if the string corresponding to this subsequence forms a palindrom. Notice that there are 2^N - 1 non-empty subsequences of S, and checking if a given subsequence is exponential and palindromic can be done in linear time by iterating over its elements. This approach leads to O(2^N \cdot N) time solution for a single test case, which is enough to pass the first subtask if only it’s implemented efficiently.
SUBTASK 2
In the second subtask N ca be as large as 1000, so the method we used to solve the first subtask is definitely too slow. We need completely different approach here. There are a lot of possible approaches here and we will describe one of them.
One idea is to use dynamic programming approach. We are going to iterate over all possible values of p from 2 to N, and for each one, we will independently count the number of palindromic sequence of order p. Finally, we will add N to the result in order to count all subsequences of length 1.
Let dp[i][p] be the set of all possible indices j such that a subsequence S_i, S_{i \cdot p}, S_{i \cdot p^2}, \ldots, S_j is a palindromic subsequence of order p. Notice that subsequence S_i, S_{i \cdot p}, S_{i \cdot p^2}, \ldots, S_j is palindromic if and only if S_i = S_j and the subsequence S_{i \cdot p}, S_{i \cdot p^2}, \ldots, S_{j/p} is palindromic. We will used this fact in order to update the dp table. It easy to see that we can do this in ascending order of the distance between the first and the last element of a subsequence. For each such distance, we will iterate over all possible starts of a subsequence from 1 to N. In more details, the pseudocode for updating the table may look like this:
answer = 0
for p = 2 to N:
exp = p
while exp <= N:
for i = 1 to N:
j = i * exp
if j > N:
break
if palindrome(i, j, p):
dp[i][p].insert(j)
answer += 1
exp *= p
Where palindrome(i, j, p) is defined as follows:
ispalindrome(i, j, p):
if i * p == j or i * p * p == j:
return S[i] == S[j]
return S[i] == S[j] and j is in dp[i * p][p]
More efficient implementation of this approach may lead to a solution which will pass also the last subtask.
The other possible solutions here are for example any non-efficient implementation of the method given as a solution to the last subtask. Please refer to the section below for more details.
SUBTASK 3
In the last subtask, N can be as large as 5 \cdot 10^5, so we need asymptotically fast solution. Notice that time limit for this subtask in not very strict, so we don’t have to worry about any extreme optimizations here.
The first observation we can make is that there are N palindromic subsequences of length 1, so we reduced the problem to counting the number of palindromic subsequences of length at least 2.
One possible approach to solve this problem is to iterate over all possible starts of a subsequence, and for each such start, iterate over all possible orders p from 2 to N. For each such start i and order p, we are going to generate the string T corresponding to a subsequence of S starting at index i and ending at the index maximum j \leq N such that j = i \cdot p^e. Then, the set of all prefixes of T is equal to the set of all valid subsequences of S of order p starting at index i.
What we are going to do is to iterate over all prefixes of T and check if such a prefix is a palindrome by scanning all its elements. Notice that for a fixed i and p, string T has length O(\log_p \frac{N}{i}), so the total length of all prefixes of T is O((\log_p \frac{N}{i})^2). This value is quite small even for i = 1 and p = 2, but more importantly, it decreases extremely fast when i and p grows. This is a crucial fact why this approach is so fast here, and let us to check if a single prefix of T is a palindrome using a linear scan.
We can optimise the palindrome checking procedure. To do this, we can use the following trick:
function check_palindrome(string s)
{
int num = 0;
int reverse_num = 0;
for(i = 0 to s.size())
{
int bit = 1 if s[i] == '1' else 0;
num = num*2 + bit;
reverse_num = reverse_num + bit*(2^i);
if(num == reverse_num)
then the prefix of string s from 0 to i is a palindrome;
}
}
Therefore, we don’t need to check every prefix separately for palindrome. We can do this on the fly.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Last but not least, during the implementation, remember to count subsequences of length 1 independently in order to avoid O(N^2) solution. Also pay attention to overflow errors while computing powers of p.