SHIFTPAL- Editorial

general
, , , , ,
5

This view content is excellent :smiley:

6

If the characters are same, then the answer is equal to the length of string (e.g if s = “aaaa”, answer is 4)

However, can the answer ever be greater than 2 if all characters aren’t same?

If yes, can someone please provide an example. Thanks in advance.

1 Like
7
Click to view

#include
#include<bits/stdc++.h>
typedef long long int lli;
using namespace std;
lli pow2(lli p){
return 1 << p;
}
int main()
{
lli t,n;string s;
cin>>t;lli count=0;
for(lli tt=0;tt<t;tt++)
{
cin>>s;
n=s.length();
s=s+s;
count=0;
lli sum1=0,sum2=0;int k=2;
for(lli i=0;i<n;i++)
{
sum1+=(s[i]-‘a’+1)*(lli)(pow2(i));

        sum2+=(s[i]-'a'+1)*(lli)(pow2(n-1-i));
    }
 
    if(sum1==sum2)count++;
    for(lli i=1;i<n;i++)
    {
        lli j=i+n-1;
        sum1-=(s[i-1]-'a'+1);
        sum1/=k;
        sum1+=(s[j]-'a'+1)*(lli)(pow2(n-1));
        sum2-=(s[i-1]-'a'+1)*(lli)(pow2(n-1));
        sum2*=k;
        sum2+=(s[j]-'a'+1);
        if(sum1==sum2)count++;
    }
    cout<<count<<"\n";
}
return 0;

}

can some one help me…thx in advance!!

8

why you are writing so many #define in code?
what is logic behind this?

Tester’s solution

9

@vijju123

How to deal with the problem of rounding of powers of ‘p’ when the power value crosses mod value?

As in, when we are comparing hash and reverse hash, one hash is multiple of other hash(as given in prerequisite). But that holds true only if the power values round up at the same point for given string.

e.g consider string s=abbbbbba.
ns = s+s = abbbbbbaabbbbbba

now if string under consideration is [2 7].
Suppose that while computing prefix array, power value rounds off at index 5.
And suppose that while computing suffix array, power value rounds off at index 7.

So, the hash[2 7] using prefix array CANT BE EQUAL to hash[2 7] using suffix array.

How to deal with this problem?

10

Here is my clean hash solution : CodeChef: Practical coding for everyone
Manacher’s Algorithm Solution : CodeChef: Practical coding for everyone

1 Like
11

I didn’t read through your code very carefully, but it seems that you haven’t accounted for the case when subtracting the two prefix sums, or two suffix sums makes it negative. You should add MOD to it in that case.

12

You can check out my code here BTW I think I have written it quite clearly http://ix.io/1bvW

13

My method of subtraction.

y=(a[1][k][2*l-i]-a[1][k][l-i]);
y%=mod[k];
y=(y+mod[k])%mod[k];

14

A nice alternative approach :slight_smile:

15

Your code failed on sample case itself. What is the logic behind your hash function?

16

Unable to format my comment.

This question was my first attempt with Hash. Yes, it also fails on sample test case.

m = some base. I took 26,101,1001 etc. But failed on all.
There 3 for mod.
All stored in modular airthmetic
Hash for prefix
s[0]
s[0]*m+s[1]
s[0]*m2+s[1]*m+s[2]
s[0]*m3+s[1]*m2+s[2]*m+s[3]+....

similarly for
s[2*l]
s[2*l]*m+s[2*l-1]
s[2*l]*m2+s[2*l-1]*m+s[2*l-2]
s[2*l]*m3+s[2*l-1]*m2+s[2*l-2]*m+s[2*l-3]+....

for substring [i,j]

hash value (prefix[j]-prefix[i])*(modInv(m))^i //here i found error while writing this. Will try again and get back.
17

cool, that’s really thinking out of the box :slight_smile:

18

I formatted it for you. Time for a comfortable reading now :smiley:

1 Like
19

I have a doubt.
If the function STRREV would have been available will this much of headache coding still be required?

20

Nice editorials @vijju123. I wish you could be editorialist for all rated contests :slight_smile:

21

OMG THAT WAS SO CUTEE!!

Its motivations like these that keep me going despite a few things <3

2 Likes
22

I think the problem is that you forgot to add new lines. If there are multiple test cases, all of the results are printed one after another on the same line.

23

yeah it is… :slight_smile:
thanks to vijju…

24

I am glad you liked it :slight_smile: . It was written in a rush though XD