Editorial - EXPALIN

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[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.

1 Like

Awesome Explanation !

2 Likes

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

why did it tle?

1 Like

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

1 Like

@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.

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

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

2 Likes

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

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

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.

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

Why does this get runtime error ?

1 Like

Double check for possible overflows.

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

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

1 Like

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

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

1 Like

thanks!!!

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

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?

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

//