CHEFSHIP - Editorial

editorial
, , , , , , ,
71

can anyone tell me why my code is wrong…
https://www.codechef.com/viewsolution/33329978

72

@admin But some of us didn’t wrote brute force as even there was no partial marking and ended up the contest while thinking for an optimized solution.
A very heavy loss in my rating(-108).That’s not fair to be honest

73

@ akashbhalotia

can you please explain setter’s approach?
i know KMP algorithm is used here but didn’t able to get how?

2 Likes
74

thanks for reply, i get it now

1 Like
75

Syntax is substr( starting index , length );

76

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 length recorded in lps1 for len-1.

3 Likes
77

why my solution gave TLE CodeChef: Practical coding for everyone ??

78

You can also find the video Editorials for the 3rd problem of the Cook Off which is Impressing Chefina.
Impressing Chefina
The Video editorial for the second problem is also uploaded soon.

79

@akashbhalotia Can you explain the implementation of getHash(int l, int r) function in your code. I am not able to follow it. What the function is doing. I understood the precomputation of hash value for the whole string but just not getting the getHash function.

1 Like
80

are the test cases strong for the practice section ?

81

I have explained it here.

1 Like
82

you all are using a lot of algorithms for string matching and everything But, can u all please check out this 9 line code solution. This is submitted after some hours of contest when the problems are shifted to practice section.

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

83

Thank You for such an explanation. I didn’t see it earlier. Can we implement the hash for prefix sums and then change getHash accordingly ? Will it work.

84

Yes, it will work.

1 Like
86

Ok boomer.

88

@akashbhalotia pleaseeeeee explain these two lines

hashs[i]=(1LL * hashs[i+1] * P + s[i] - ‘a’ + 1) % MOD;
pows[n-i]=(1LL * pows[n-i-1] * P) % MOD;

and this line too

int ans=hashs[l] + MOD - (1LL*hashs[r+1]*pows[r-l+1])%MOD;

???

89

Thank you so much. I still don’t fully understand because I am not very familiar with the topic, but I really appreciate the time that you took to write out the response. Thank you so much.

90

Please refer to this.

91

Time complexity is O(n).
Approach:

  • I used hash prefix sums one from the left and another one from the right.
  • First Iterate from L to R, then R to L.
  • while iterating from left to right; check if the other half of current substring has the same hash, If yes, check if they are equal using substring matching, Increment left Array on that position and similarly, for right Array while iterating from right to left.
  • To get Substring in O(1), I used string_view, it’s a new feature in C++17. (WTF! right ?, I know, It’s crazy).
  • Finally, Iterate through indices and Compute answer from the left and right arrays which denotes if the ith position can result in solution from left and from right respectively.

Checkout the solution:

#include <bits/stdc++.h>
#define pi pair<int,int>
#define EPS 1e-9
#define ll long long int
#define pii pair<long long,long long>
#define f(i,a,b) for(ll i = (ll)(a); i <= (ll)(b); i++)
#define rf(i,a,b) for(ll i = (ll)(a); i >= (ll)(b); i--)
#define PI 3.14159265
#define ff first
#define ss second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define debug(x) cout << #x << " = " << x << endl
#define INF 1000000009
#define mod 1000000007

using namespace std;

int t,n;

string s;

int main() 
{
cin>>t;
while(t--)
{   
	cin>>s;
	n = s.size();
	string_view sv(s.c_str(), n);

	vector<int> hash1(n+1, 0), left(n+1, 0), right(n+1, 0), hash2(n+1, 0);
	unordered_map<int,int> m;
	hash1[0] = s[0]-'a'+1;
	m[hash1[0]] = 1;
	left[0] = 0;
	for (int i=1;i<n-2;i++) {
		hash1[i] = hash1[i-1] + s[i]-'a'+1;
		if (m.count(hash1[i]>>1) && sv.substr(0, i/2+i%2) == sv.substr(i/2+i%2, i/2+1))  left[i]++;
		m[hash1[i]] = 1;
	}
	
	m.clear();
	
	hash2[n-1] = s[n-1]-'a'+1;
	m[hash2[n-1]] = 1;
	right[n-1] = 0;
	
	for (int i=n-2, j=1;i>=2;i--, j++) {
		hash2[i] = hash2[i+1] + s[i]-'a'+1;
		if (m.count(hash2[i]>>1) && sv.substr(i, j/2+1) == sv.substr(i+j/2+1))  right[i]++;
		m[hash2[i]] = 1;
	}
	
	int ans = 0, l,r;
	
	for (int i=0;i<n;i++) {
		ans += left[i]*right[i+1];
	}
	
	cout<<ans<<"\n";
}
return 0;
}

Happy Coding!

2 Likes
92

more specifically if i==n-1 then hash[i+1],i.e hash[n], then what will be the value of hash[n]?