CHEFSHIP - Editorial

i found a blog and now on i have c++17 running fine on codeblocks with the same mingw compiler but still no help in vs code i don’t know how to manipulate json in vscode and i guess thats why it is working

I have used the KMP approach. It is getting a WA
Can anybody find mistake in my CODE

Sir can you explain what do you mean by overlapping length ? PLz

@akashbhalotia isnt it also required to check the substrings when their hash values are same?

Why is this approach of find hash values wrong?

void computehashvalues(string s)
{
int l=s.length(),power=31;
hasharr[0]=(s.at(0)-‘a’+1);
for(int i=1;i<=l-1;i++)
{
hasharr[i]=hasharr[i-1]+((s.at(i)-‘a’+1)power);
power=power
p;
}
}
long long int findHash(int si,int ei)
{
if(si==0)
return hasharr[ei];
else
{
return (hasharr[ei]-hasharr[si])/pow(p,si);
}
}

Please either format your code or (better!) link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

https://www.codechef.com/viewsolution/33436196

Why is this approach wrong?

Since u ll be using some value as for modulus so it is quite possible hasharr[ei] < hasharr[si] (after modulus) so in the the findhash function u need to consider mod number as well …

Can plz correct it i am not able to uderstand what corrections do i have to make??

@akashbhalotia for what this if(2*len > i+1)
len = lps1[key][len - 1]; is for??

can anyone please tell why time limit is exceeded in my submission.i used the rolling hashing array
and time complexity according to me is O(n) for each test case.codechef.com/viewsolution/33548226
My code is in cpp

Hi
https://www.codechef.com/viewsolution/33330471
^^ here’s my solution for CHEFSHIP
(problem link: https://www.codechef.com/problems/CHEFSHIP)
(submit here: https://www.codechef.com/submit/CHEFSHIP)
:+1: :slightly_smiling_face:

1 Like

I loved your explanation

Time for finding inverse modulo is also considered. Since the competition, the test cases have been improved to pass only O(n) cases.

In line 49 instead of

    pref[i]==((MOD+pref[2*i+1]-pref[i])%MOD)*modInverse(p[i+1])%MOD

make it

    (pref[i] * p[i+1])%MOD==((MOD+pref[2*i+1]-pref[i])%MOD)%MOD

I think this should work.

Basically instead of dividing the RHS (which takes log time to find inverse), multiply the LHS (which takes constant time). I hope this helped​:v::v::v:

For some reason I think the hashes you are comparing are wrong.

int k=i+(s.size()-1-i)/2;
    int j=(i+1)/2;
    int h1,h2,h3,h4;
    h1=(h[0]-((h[j]*power[j])%m)+m)%m;
    h2=(h[j]-((h[i+1]*power[i-j+1])%m)+m)%m;
    h3=(h[i+1]-((h[k+1]*power[k-i])%m)+m)%m;
    h4=h[k+1];

This seems fishy.

l1 = i + 1;
        l2 = N - 2 * l1;
        l2 /= 2;
        if (l1 <= 0 || l2 <= 0)
            break;
        h1 = (pre[l1 - 1LL]);
        h1 = (h1 * powre(l1)) % p2;
        h2 = (pre[2LL * l1 - 1LL] - pre[l1 - 1LL] + p2) % p2;
        h3 = (pre[2LL * l1 + l2 - 1LL] - pre[2LL * l1 - 1LL] + p2) % p2;
        h3 = (h3 * powre(l2)) % p2;
        h4 = (pre[N - 1] - pre[2LL * l1 + l2 - 1LL] + p2) % p2;

This seems good.

Here have a look at my code.
https://www.codechef.com/viewsolution/33373856

@abhaypatil2000
I guess i took the right hashes.But the problem is TLE which is shown even after me trying to optimize the code.Kindly look into it and suggest how can i optimize it further.
https://www.codechef.com/viewsolution/33581063
My code works fine for the sample test cases and i am using a suffix hash array instead of a prefix hash array which u used

PLEASE, let’s get over this editorial now
nicely done, chef

There is no need for any passive aggression. Be respectful towards the panelists who are taking the time to help the community.

4 Likes

Thanks for the explanation but can you explain Why we are subtracting from MOD?
MOD-(hash[r+1]*pow[r-l+1])%MOD+hash[l])%MOD;

We need hash[l]-(hash[r+1]*pow[r-l+1]) under a modulo. However, subtraction under a modulo can lead to a negative result. But modulo only allows answers from 0 to (MOD-1). Thus, when we perform subtraction under a modulo, we add MOD to the result if it’s negative. Instead of checking whether or not the result is negative, I’ve simply added MOD to it, and then performed MOD again. This will guarantee that the result is between 0 and (MOD-1).

Thus, I wrote:

(MOD-(hash[r+1]*pow[r-l+1])%MOD+hash[l])%MOD;

This can also be written as:

long left=hash[l];
long right=(hash[r+1]*pow[r-l+1])%MOD;

long res=(left-right)%MOD;
if(res<0) return res+MOD;
else return res;