PALIN3 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Konstantin Sokol
Tester: Gerald Agapov
Editorialist: Tasnim Imran Sunny

DIFFICULTY:

Medium

PREREQUISITES:

Manacher’s Algorithm

PROBLEM:

Given a string S which is consisted of only digits, find the number of palindromic substrings of S without leading zeros and is divisible by 3.

EXPLANATION:

Consider counting all odd length palindromes.

Let D[i] = the length of longest palindromic substring centering at index i.
So if S=”ababac” D would be {1,3,5,3,1,1}. This table D[] can be computed in linear time using Manacher’s algorithm. You can read how to implement Manacher’s algorithm here or here.

Remember that if a number is divisible by 3, the total sum of all of it’s digits is divisible by 3.

Let C(i,j) = The sum of digits between i and j (inclusive) = Si + Si+1 + … + Sj

For each index i compute the number of odd length palindromic substrings centering i and which are divisible by 3. Let, l = (D[i] – 1)/2. So, Si-k … Si … Si+k would be palindrome centering i where 1 <= k <= l . The sum of digits of left and right of i of the palindrome would be same. Let the sum of digits of one side be x, so to be divisible by 3:

( Si + 2*x) mod 3 = 0

Since everything is considered modulo 3, it’s enough to find the reminder of x modulo 3, instead of the sum. So x could have values 0,1 or 2 and the above equation can be solved easily by trying every value.
So the number of palindromes divisible by 3 centering i would be same as the number of k’s(1 <= k <= l) where C(i+1, i+k) mod 3 = x.
This can be found easily in constant time with linear precomputation.
To find that, for each value of y (0 <= y <= 2) and index i precompute how many indexes between 1 and i have C(1,i) mod 3 = y . Since it’s a palindrome, if a number contains a leading zero then it contains a trailing zero too,so only the indexes i where Si != 0 are considered in the precomputation.

The even length palindromes can be counted similarly.

The complexity of the solution is O(N).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

3 Likes

Too bad my hashing+binsearch algorithm on longest palindrome centered at i didn’t fit in the time limit. It probably would’ve if the time limit was 2 seconds instead of 1.

More precisely, just why did I have to waste an hour optimizing my code? There was better stuff to do. Anything was better stuff to do…

Well, at least I see that Manacher can actually be useful in a contest sometimes. Up till now, I thought my hash+binsearch variation would always work.

3 Likes

It seems that binary search+hashing passed all tests in time limit. It was first attempt now. My solution: CodeChef: Practical coding for everyone

I also implemented hashing+binsearch and got AC. But I had to optimize my initial implementation in order to get AC (which cost me both time + several TLE attempts). In case you’re interested, the last optimization which got me AC was to use a separate unordered_map for each palindrome length (instead of a single unordered_map in which I would store the hashes of all the palindromes, as I did in my initial submissions).

" To find that, for each value of y (0 <= y <= 2) and index i precompute how many indexes between 1 and i have C(1,i) mod 3 = y "

Can anyone tell me why ?

We will apply manacher algo first as usual. Lets consider odd length palindromes.
Let x be the sum of digits to the right of i which forms palindrome centered at i. Total sum of palindrome will be 2x+s[i]. So, (2x+s[i])%3 == 0.
By trial and error you can see if x%3 == s[i]%3, then (2*x+s[i])%3 = 0.

Let the palindrome be s[i-k…i…i+k]. We need to find the ans[i] = no of k such that k<=d[i] and sum[i+1…k]%3 = s[i]%3. To to this we will precompute sum[i] and cnt[i][y] in linear time.
sum[i] is sum of digits till i mod 3.
cnt[i][y] = no of k such that k<=i and sum[k] = y (0<=y<=2).

Now, cnt[i+d[i]][s[i]%3] will give me no of k (k<=i+d[i]) such that sum[1…k]%3 = s[i]%3. Similarly for cnt[i][s[i]%3]. So cnt[i+d[i]][s[i]%3] - cnt[i][s[i]%3] will give me no of k (i<k<=i+d[i]) such that sum[1…j]%3 = s[i]%3. However we want no of k (i<k<=i+d[i]) such that the sum[i+1…j] = s[i]%3.
Since cnt[][] consider sum from 1st digit and not from ith digit, I will add sum[1…j] to the condition sum[i+1…j] = s[i]%3 on both sides. So, (sum[1…i] + sum[i+1…j])%3 = (s[i]%3 + sum[1…i])%3. Therefore, sum[1…j] = (s[i]%3 + sum[1…i])%3.
So, we will take t = (sum[i] + s[i])%3. Now, ans[i] = cnt[i+k][t] - cnt[i][t] and if s[i]%3==0, then ++ans[i].

Note : we will not increment cnt[i][y] if s[i]==‘0’ because we dont want the leftmost digit in palindrome to be 0.

My solution : CodeChef: Practical coding for everyone

2 Likes

What is Manachar’s algorithm ?

What is Google?

You can check out manacher’s algorithm here : Manacher's Algorithm | Longest Palindromic Substring - YouTube

" To find ans[i], ans[i] = cnt[i+k][s[i]%3] - cnt[i][s[i]%3] will not work because sum[i] would have contributed to the sum right of I "

Can u pls explain this line once?

I have updated my explanation.

1 Like

Thanks … finally understood :slight_smile:

1 Like