CHEFSHIP - Editorial

editorial
, , , , , , ,
119

Thanks @rishup_nitdgp for such a good question and also @akashbhalotia for such a great editorial !!
My unnecessary story for the question :

I finally solved this problem and I believe that I have got a basic understanding of string hashing. I still am having a few doubts regarding this topic - string hashing.

Firstly I was checking for collisions in my code so I got TLE. So my hope for solving this question got smashed :disappointed: :disappointed:. So I started looking for other people’s code and then I realised that they weren’t checking for collisions, so I commented that part in my code and it got accepted :partying_face:.

So basically I want to know whether or not should we check for collision and if yes then when should we and how can one make checking collisions more effective ?

Also can anyone please answer this question also ? It’s regarding the Chef Impress question in this month’s cook off. It will be great help for beginners like me.

2 Likes
120

@rishup_nitdgp @akashbhalotia hello sir after reading your editorial I tried to do this question but it got TLE can you please have a look at my solution and explain me where I do something wrong. Any suggestions are welcome sir.
KIndly reply after seeing the comment. It will help me to improve me.

1 Like
121

Refer to this link for understanding the string hashing and how to decrease the probability of collisions.

1 Like
122

I used hashing creates a hash function and if the value of pairs of the hash function is equal then it is a match.
can someone explain to me why I’m getting TLE?

@rishup_nitdgp @everule1 @akashbhalotia Please have a look sir

dd={}

modulo=10**9+7

for i in range(97,123):
    dd[chr(i)]=i-97+1
    
def search(pattern,text):
    n=len(pattern)
    c=0
    e=0
    for j in range(n):
        a=dd[pattern[j]]
        b=dd[text[j]]
        c+=(a*(10**(n-j-1)))%modulo
        e+=(b*(10**(n-j-1)))%modulo
        
    return c==e


for _ in range(int(input())):
    s=input()
    n=len(s)
    co=0
    if n<4:
        print("0")
    else:
        for i in range(2,n,2):
            a=s[:i//2]
            b=s[i//2:i]
            c=s[i:(i+n)//2]
            d=s[(i+n)//2:]
            
            if search(a,b) and search(c,d):
               co+=1
        print(co)
123

Thanks !!
I got it now :smile:

1 Like
124

Getting TLE for following code, used KMP string matching.
#include<bits/stdc++.h>

using namespace std;

void computeprefix(int pref[], string P)
{
pref[0]=0;
int k=0, m=P.length();
for(int i=1;i<m;i++)
{
    //recursively get longest proper prefix and suffix in the existing longest proper substring
    //which is already a prefix and suffix
    while(k>0 && (P[k]!=P[i]))
        k=pref[k];
    
    if(P[k] == P[i])
        k=k+1;
    
    pref[i]=k;
}

// cout << "prefix function\n";
// for(int i=0;i<m;i++)
//     cout << pref[i] << " ";
// cout << endl;

}

int findoccurence(string T, string P, int pref[], int st)
{
int n, m;   n=T.length();   m=P.length();
int q=0;

for(int i=st;i<n;i++)
{
    while(q>0 && T[i] != P[q])
        q=pref[q];
    
    if(T[i] == P[q])
        q++;
    if(q == m)
    {
        return i-(m-1);
        // cout << "Pattern matches at: " << i-(m-1) << " " << endl;
        // q=pref[q-1];          //for futher remaining text
    }
    // cout << i << endl;  
}
return -1;
}

bool check(string T, string P, int pref[], int st, int n, int m)
{
if(st == n)
    return false;
    
int l=n-st;
if(l%2 == 1)
    return false;

int sz=(n-st)/2;
int ind1=st, ind2=st+sz;

for(int i=0;i<sz;i++)
{
    if(T[ind1] != T[ind2])
        return false;
    ind1++;
    ind2++;
    
}
return true;
}

int main()
{
int t;  cin >> t;

while(t--)
{
    string T, P;       cin >> T;
    int n, m, cnt=0;
    n=T.length();      
    
    P="";
    P=P+T[0];
    
    
    set< pair<int, int> > s;
    for(int i=1;i<=n;)
    {
        m=i;
        int pref[m];        //prefix array for out query
        computeprefix(pref, P);    
        int val=findoccurence(T, P, pref, i); 
        
        // cout << val << " " << i << " " << P << endl; 
        
        if(val == i && check(T, P, pref, val+i, n, m))
            cnt++;
        
        if(i == n)
            break;
            
        P=P+T[i];

            i++;
    }
    cout << cnt << endl;
}
return 0;
}
125

can any one tell what is wrong with my solution please
https://www.codechef.com/viewsolution/33351237

126

@abhishek_iita can you please explain why did we create the lps array of reversed string?

127

because of the T2 (to simplify things)
you can treat T2 as T1 when the string is reversed and apply the same rule as that of T1

128

Why my solution is giving WA? https://www.codechef.com/viewsolution/33366047 (it passes for sample test cases, and for many custom test cases as well, well formatted)

I read about string-hashing on cp-algorithms according to which:
hash(i,j) = (hash(0,j)-hash(0,i-1))*(multiplicative modulo inverse of p^i)
and have used this in my solution.

If my WA solution is difficult to understand, I have commented my code in case here: https://ideone.com/SSDjRD

129

I have debugged it: here.
Check out line 32 of your code and the AC one, and I think you shall find the mistake.

1 Like
130

Oh! This silly mistake slipped real quick from my eyes. Thank you soo much.

1 Like
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;
}