PALIN3 - Editorial



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




Manacher’s Algorithm


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.


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 solution can be found here.
Tester’s solution can be found here.


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.


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

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