CHEFPCHF - Editorial

editorial
, , , , , ,
1

PROBLEM LINK

Practice

Contest

Author: Hanlin Ren

Tester: Jakub Safin

Editorialist: Jakub Safin

DIFFICULTY

MEDIUM

PREREQUISITIES

counting palindromes using hashing

PROBLEM

Count the number of odd-length palindromes in a sequence of numbers. The sequence has length N and contains K non-zero numbers, where K \ll N.

QUICK EXPLANATION

Using direct+reverse hashes and binary search, find the largest palindrome centered at each non-zero number and between each pair of adjacent non-zero numbers. Add palindromes containing only zeroes.

EXPLANATION

We’ve got here a variation on the classic problem of counting (or finding the longest) odd-length palindromes, which is solved by finding prefix hashes of the original sequence, reversed sequence, and binary-searching the longest palindrome centered at each index. Subtask 2 is basically this. There’s the usual caveat of choosing the right hashing method - the tests were made to fail hashing mod 2^{64} :smiley:

The main complication is that the sequence is too long to even keep in memory. Fortunately, non-trivial palindromes can only be centered at very few indices. Let’s handle the following cases:

  1. palindromes containing only zeroes
  2. palidromes centered at a non-zero number
  3. palindromes centered at a zero, but containing a non-zero

Case 1

We can find all K+1 sequences (possibly empty) of consecutive zeroes. In a sequence of length L, we can find (L/2)(L/2+1) odd-length palindromes if L is even and (L+1)^2/4 if L is odd.

Case 2

It’s clear that if a palindrome is centered at p_c, then all non-zero numbers appearing in it form a odd-length palindromic subsequence of q centered at c. Also, p_{c+x}-p_c = p_c-p_{c-x} for all indices p_{c-x},p_{c+x} in this palindrome - therefore, we can compute a new sequence d_{1..K-1} of consecutive differences d_i=p_{i+1}-p_i, and then we need an even-length (possibly empty) palindrome in this array centered between d_{c-1} and d_c.

These two conditions are sufficient - if a substring centered at p_c contains non-zero numbers in the range [c-x,c+x] such that subsequences q_{c-x..c+x} and d_{c-x..c+x-1} are palindromic, then it is a palindrome.

We can use a modification of the usual algorithm: compute normal and reverse prefix hashes of q and d, try all c, binsearch for the largest x which gives these two palindromes, find the maximum length 2l+1 of a palindrome which doesn’t contain indices p_{c-x-1} or p_{c+x+1}, and add l+1 to the answer.

Case 3

Let’s consider the pair of non-zero numbers closest to the center. They need to be equal and at equal distances from the center, so they must be adjacent in seq. p - if they are p_c and p_{c+1}, then p_c+p_{c+1} must be even and the palindrome is centered at \frac{p_c+p_{c+1}}{2}.

Now we can proceed in a similar way to case 2. Palindromes in s containing [c-x,c+1+x] correspond to palindromes q_{c-x..c+1+x} and d_{c-x..c+x}.

Note that palindromes in this case are automatically distinct from all palindromes in case 2, but not in case 1. We need to subtract \frac{p_{c+1}-p_c}{2} to exclude palindromes containing only zeroes.

Case 1 takes O(K) time; in cases 2 and 3, we need to check O(K) centers and do an O(\log{K}) binary search; mrecomputing hashes takes O(K) time as well, so the total time complexity is O(K\log{K}). Memory complexity: O(K).

AUTHOR’S AND TESTER’S SOLUTIONS

Setter’s solution

Tester’s solution

1 Like
2

Actually my solution uses manacher and is O(K) :slight_smile:

We can construct a new string str whose alphabet is [-10^9,10^9]. Negative char -a means a block of zeros of length a, and 0 means one zero. We don’t use -1.

For a maximal consecutive block of 0 s of length a, we split it into several blocks:

  • if a=1, we replace it by a 0;
  • if a is odd, we replace it by -\frac{a-1}{2},0,-\frac{a-1}{2};
  • if a is even, we replace it by -\frac{a}{2},-\frac{a}{2}.

Then we can do manacher on the new string. We get the palindrome radius of all positions and compute the answer. The palindrome radius is defined as the max R[i] such that for any r<R[i], str[i-r]=str[i+r].

How to compute the answer? We need to sum up all radius in the original string. If str[i] is negative, then it’s a block of a 0's and the i-th(0-indexed) char has radius i, so the total radius is \frac{a(a+1)}{2}. Otherwise it’s positive or 0, and we can find its radius R' in the compressed string. We need to extend R' a bit so we consider zeros, e.g. consider string -2,1,-3, for the middle 1 its R' is 1, but its actual R is 3, since on the left and right of (i-R,i+R) there are zeros.

The total computation can be done in O(K), which is faster than O(K\log K).(Actually not that faster.)

Also I hope admin to do something to manage privileges better. I can’t see my and tester’s solution even 9 hours after the contest :frowning: If you can see my code, you probably can understand my solution better.

5 Likes
3

In all my years of competitive programming, I never got to learning Manacher and only needed it instead of hashing once (in an old Codechef contest :D).

These two methods seem to be interchangeable most of the time.

1 Like
4

I made the code for this prob in Clion and got the correct output for all test cases but when I submit my soln I get an SIGSEGV and I cant figure out the error is

my code is

>     #include <stdio.h>
>     #include <string.h>
>     
>     int main() {
>         int t,x;
>         scanf("%d ",&t);
>         for(x=0;x<t;x++)
>         {
>             int n,k,i,j,m,l,r,out;
>             scanf("%d %d", &n, &k);
>             char q[k],string[n];
>             int p[k];
>             for (i=0;i<k;i++)
>                 scanf("%d %c",&p[i],&q[i]);
>             for (i=0;i<n;i++)
>                 string[i]='0';
>             for (i=0;i<k;i++)
>                 string[p[i]-1]=q[i];
>             out=n;
>             if(k==0)
>                 out+=n;
>             for(i=0;i<n-2;i++)
>             {
>                 int flag;
>                 for(j=i+2;j<n;j+=2)
>                 {
>                     char str[(j+1)-i],rev[(j+1)-i];
>                     for(m=i;m<=j;m++)
>                     {
>                         str[m-i]=string[m];
>                     }
>                     for(l=j-i,r=0;l>=0;l--,r++)
>                         rev[r]=str[l];
>                     flag = strcmp(str,rev);
>                     if(flag==0)
>                         out++;
>                 }
>             }
>             printf("%d \n",out);
>         }
>         return 0; }
5

If you read the editorial, you would know. Hint: good luck allocating 1 GB of memory.

3 Likes
6

The links to the tester and setter solutions don’t appear to work.

2 Likes
7

I was wondering that. Because I messed up this problem and when after contest when I was discussing with my friends, some solved the 1st and 2nd subtask using manachers while some solved 1st and 3rd using logic. So, their was a solution using manacher’s. But I thought there must be another solution because ‘officially’ ltime is ioi based and ioi doesn’t has manachers

1 Like
8

Can links to solutions be made accessible?

9

@r_64 what have you done for the case when str[i]>0
how you computed R’
@mathecodician