CHEFSHIP - Editorial

editorial
, , , , , , ,
131

@abhishek_iiita I also tried to implement the solution using kmp algorithm, but without any extra lps array and period. Can you explain why the period is calculated for the substring?

I used the similar approach as yours for calculating the 2 lps arrays. While iterating over the original string I just checked the length of lps for two halves and if the they exceed the half lengths then I increment the count. Still getting a WA.

Here is the link to my solution - CodeChef: Practical coding for everyone

Thanks for any help :slight_smile:

132

This post was flagged by the community and is temporarily hidden.

133

Here is a case for which your code is failing.

1
abababaa

P.S. Your code is not covering the overlapping cases.

1 Like
134

Your code is not optimized that’s why you are getting TLE. It is still O(n^2). Refer this for a better understanding of the hashing in strings.

135

Can you explain me a little more like in which portion I have to change so my code can optimize. Any suggestion are pleased .Thanks

136

@rishup_nitdgp Got it! Thanks :+1:

137

is there some similar question in leetcode or some other place where test cases are available. I really need to verify and improve my approach.

138

Below is my code. Please someone tell me what I am doing wrong in this. It is passing example set.

#include
#include <stdlib.h>
#include
#include
#include
#include <stdio.h>
using namespace std;

int main()
{
int t;
cin>>t;
while(t–){
string s;
cin>>s;
int len;
int x=0;
len=s.length();
for(int i=1;i<len;i++)
{
if(s[0]==s[i])
{
string s1,s2;
s1=s.substr(0,i-1);
s2=s.substr(i,i-1);
if(s1.compare(s2)!=0)
{
continue;
}
else{
string s3,s4;
s3=s.substr(2i,((len-2i)/2)-1 );
s4=s.substr(len-(2i)+1,((len-2i)/2)-1);
if(s3.compare(s4)!=0)
{
break;
}
else{
x=x+1;
}
break;
}
}
}
if(x==1)
{
cout<<“1”<<endl;
}
else{
cout<<“0”<<endl;
}

}

return 0;
}

139

That modification of KMP algorithm to find non-overlapping longest prefix which is also a suffix is cool. Thanks for including that solution.

140

It was a good question and the story and all were interesting sir. It was my first time to get two acs in a cook-off . I felt bad in the morning when many said that my brute-force solution was not supposed to work :sweat_smile: ! The feeling that I didn’t deserve the increase in my rating made me feel bad . So I learnt hashing as suggested in tutorial and got ac for the question in practice. I don’t think that I would have learnt hashing if my brute-force failed. Something good did come out of this sir .
Thank you.

2 Likes
141

Just learned String hashing. So might be a weird question. In editorialist solution :
long getHash(int l, int r){return (MOD-(hash[r+1]*pow[r-l+1])%MOD+hash[l])%MOD;}
}
why we are taking range of substring(r+1,l) rather than (r,l-1) ? Please explain.

142

Its a backward hashing that’s why loop starts from n-1 to 0 hence you find hash of getHash(l,r) = hash[l] - hash[r+1]*pow[r-l+1])%MOD this way.

For forward hashing we could have used getHash(l,r) = hash[r] - (hash[l-1]*power[r-l+1]%MOD) this way.

143

I have tried using forward hashing still I have to use the range(l,r+1) otherwise wrong answer. Here:- CodeChef: Practical coding for everyone

144

why am i getting TLE in my code :
MY CODE
any help and insight would be helpful.
Thank you.

145

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

146

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!

1 Like
147

It is for avoid overlapping. I explained it here:

148

@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.

149

can you please provide the cpp code by using hashing

150

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

1 Like