Editorial - EXPALIN

editorial
ltime32
palindrome
string

#1

PROBLEM LINK:

Practice
Contest

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*[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*[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* == S[j]
    return S* == 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* == '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.


#2

Awesome Explanation !


#3

https://www.codechef.com/viewsolution/9266509

why did it tle?


#4

@anupam_datta Instead of re-declaring or clearing the vector try to overwrite it.
Re-declaring or clearing a vector has time complexity of O(n) where n is the size of vector.


#5

Why does this get runtime error ?


#6

Why am i getting NZEC ???
https://www.codechef.com/viewsolution/9267941


#7

I have passed string as reference in my palindrome function so it should not copy the whole string.
https://www.codechef.com/viewsolution/9269046
Why still getting TLE in subtask 3?


#8

Can anybody tell me why i got a TLE on 3rd Subtask ??
https://www.codechef.com/viewsolution/9268942


#9

My (simplified) understanding of the solution:

Iterate over all possible values of the Order p (starting from 2) and treat every index i as centre of the palindromic subsequence. Treating i as the centre allows us to check if the subsequence is a palindrome on the fly, because we only have to check the newly added peripheral characters on the left and the right. We are assured that the subsequence we have till now is a palindrome already, so we only have to check if the newly added characters on the left and right of the subsequence match each other or not. Be careful to consider 2 cases here:

First Case (Your palindrome is an odd length palindrome):
The character at index i can be the centre of a palindrome so in this case you have to check the characters to the left and right(not immediate left and right) of i. Call them start and finish. Initially, start will be equal to i/p and finish will be equal to i X p… if start and finish are equal, then great, increment your answer by 1 and set start = start/p and finish = finish X p. Obviously if start and finish violate any boundary conditions like start%p !=0 OR finish > length of string OR obviously if character at start != character at finish, then you should break from this inner loop and start considering the next index i+1 as the centre of your palindromic subsequence.

Second Case (Palindrome is of even length:) Treat the index i as one of the 2 characters which form the centre of your even length palindrome. In this case the start will be equal to i (instead of i/p) and finish will be the same as previous case: i*p. Perform the same checks as before, checking everytime if start==finish and if yes, set start = start/p and finish = finish/p. Break if start%p != 0 OR if finish is greater than the length of the string OR if start != finish.

Caveat: As mentioned in the editorial, you will have to add the length of the string to your answer because every subsequence of length is a valid answer. This hack allows us to start considering subsequences whose length is at least 2, otherwise, as mentioned, we will end up with an O(n^2) algorithm, which will fail horribly.

Please see the linked tester’s excellent solution for the implementation details.


#10

I am not sure but I think your code’s complexity is somewhat O(N2log(N)) which isn’t enough for subtask 3.


#11

It’s an idea for speeding it up, but won’t solve his TLE.


#12

You almost manage to solve it, but you did one very inefficient thing. Notice that you are passing a string by a value to your palindrome checking function. This causes copying the whole string during each call to this function. I change the function to operate on a global variable and the solution passed: https://www.codechef.com/viewsolution/9268292


#13

This is my solution which got tle https://www.codechef.com/viewsolution/9265512

This is which get accepted
https://www.codechef.com/viewsolution/9268112


#14

I get your point, but look at my comment to his question. His main issue is passing the string by a value to the palindrome checking function.


#15

oh! sorry, I misunderstood that.you are right.


#16

Double check for possible overflows.


#17

@pkacprzak Can’t access author’s solution! Could you please fix the link ?


#18

Wouldn’t overflow produce a WA rather than a runtime error ?


#19

It depends on the execution. For example, you may try to access some unbounded entries of an array etc. I submitted your solution using long long type where appropriate and it passed: https://www.codechef.com/viewsolution/9268632


#20

My bad, I might have been accessing negative index entries in the array due to overflow.