PALIN3 - Editorial

editorial
, , , ,
1

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.

2 Likes
2

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
3

It seems that binary search+hashing passed all tests in time limit. It was first attempt now. My solution: http://www.codechef.com/viewsolution/3642587

4

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