CHEFSHIP - Editorial

editorial
, , , , , , ,
152

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

153

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

155

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

157

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

158

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=powerp;
}
}
long long int findHash(int si,int ei)
{
if(si==0)
return hasharr[ei];
else
{
return (hasharr[ei]-hasharr[si])/pow(p,si);
}
}

159

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

161

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

Why is this approach wrong?

162

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 …

164

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

165

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

166

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 CodeChef: Practical coding for everyone
My code is in cpp

167

Hi
https://www.codechef.com/viewsolution/33330471
^^ here’s my solution for CHEFSHIP
(problem link: CHEFSHIP Problem - CodeChef)
(submit here: CodeChef: Practical coding for everyone)
:+1: :slightly_smiling_face:

1 Like
168

I loved your explanation

169

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:

170

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

171

@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

172

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

173

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

4 Likes
174

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;

175

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;