CHEFSHIP - Editorial

[yogesh2000]

setter and tester sir can explain there solutions. Please sir.

[qwerty87]

i have also used LPS(Prefix sum technique) as setter solution but i did not get it! why @rishup_nitdgp used the (len*2>(i+1)). could you please explain me the little bit!

[rishup_nitdgp]

It is for avoid overlapping. I explained it here:

CHEFSHIP - Editorial

I’m basically using two lps, lps1 is with overlapping and lps2 is without overlapping. Ips1 is the same as used in KMP. Now, see how can we construct lps2 with the help of lps1. We know that we are moving both the i and len with 1 increment. When we first encountor the overlapping then is should involve only one charactor overlap i.e. for any position i, if there is overlap then it should be such that substring 1 to k is equal to substring k to i. We can replace the len in this case with the len…

[abhi_dtu2014]

@pastor Read about gcc compilers and try to find which gcc is your vs code running on. I mostly use ideone but seems like it still doesn’t support c++17. I used code and compile from codechef only.

[anshuman126]

can you please provide the cpp code by using hashing

[aayush_84719]

For each iteration you are calculating the hashValue in O(n), thus making your overall complexity O(n*n) which will surely timeout. You need to do some preCalculation as you are calculating the same stuff again and again.
Have a look : CodeChef: Practical coding for everyone

[ajaygupta007]

in kmp solution of setter why use 2 keys(0,1).is it can using only two 1d-array?
my question is why prefix function is calculated for reverse of array

[pastor]

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

[harsh_joeyit]

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

[iit_yt_28]

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

[i_gupta0903]

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

[anon53216933]

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);
}
}

[ssjgz]

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

[anon53216933]

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

Why is this approach wrong?

[i_gupta0903]

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 …

[anon53216933]

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

[pksingh290]

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

[souravunni27]

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

[wickedknight]

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)

[varunv153]

I loved your explanation