CHEFSHIP - Editorial

PROBLEM LINK:

Practice
Contest

Author: Ritesh Gupta
Tester: Raja Vardhan Reddy
Editorialist: Akash Bhalotia

DIFFICULTY:

Easy

PREREQUISITES:

String-Matching, Hashing, Prefix Function.

PROBLEM:

Given a string S, find the number of ways to retrieve some strings T_1 and T_2 from it, such that S=T_1+T_1+T_2+T_2, where + denotes string concatenation.

HINTS:

Not the full solution. Just some hints to help you if you are stuck at some point. As soon as you encounter a hint that you had not thought of, try solving the problem on your own.

Hint 1:

Try learning a string-matching algorithm, which can compare strings fast, such as hashing or kmp.

Now that you can compare parts of a string fast, can you solve the problem?


Hint 2:

We need to find all T_1 and T_2 such that S=T_1+T_1+T_2+T_2.
T_1+T_1=2*T_1, and T_2+T_2=2*T_2.
Both 2T_1 and 2T_2 are of even lengths.

Iterate over all the even indices, and partition the array as follows:

P_1: [0,\frac{i}{2}-1]
P_2: [\frac{i}{2},i-1]
P_3: [i,\frac{i+N}{2}-1], and
P_4: [\frac{i+N}{2},N-1]

and check if P_1=P_2 and P_3=P_4, using any efficient string matching algorithm.


QUICK EXPLANATION:

show

Iterate over all the even indices and divide the string into two parts. The first part will be further divided into parts P_1 and P_2 of equal length, while the second part into P_3 and P_4, again, of equal length. If P_1=P_2 and P_3=P_4, increment the count. Checking for equality can be done using any popular string-matching algorithm like kmp or hashing.

EXPLANATION

show

We need to find the number of ways in which S can be represented as a combination of some T_1 and T_2 such that S=T_1+T_1+T_2+T_2.

To do this, we can divide S into four parts P_1, P_2, P_3 and P_4 such that S=P_1+P_2+P_3+P_4 and check whether P_1 equals P_2 and P_3 equals P_4 (equal means same in length and in characters).

As an example, consider the string: aaaabaaaabaa (0 -indexed ).
There are two ways to partition it into P_1,P_2,P_3,P_4 such that P_1=P_2 and P_3=P_4.
We can choose P_1 to be [0,0], P_2 to be [1,1], P_3 to be [2,6] and then P_4 will be [7,11].
The second way is to choose P_1 to be [0,4] P_2 to be [5,9], P_3 to be [10,10] and then P_4 will be [11,11].

Since P_1 and P_2 need to be checked for equality, P_1 and P_2 should be of the same length, thus, P_1+P_2 will have an even length. As |S| is divisible by 2 (see problem constraints), the remaining part P_3+P_4 will also have an even length.

Thus, we can iterate over all even positions in the string and check if they partition the string into four parts, such that the first and the seconds parts are equal, and the third and the fourth parts are equal. Keep in mind that all parts must be of positive length ( i.e. \gt 0).

To check for equality fast, we can use any popular string matching technique, like hashing, prefix-function, z-function, etc.

I have used hashing in my implementation, as it makes solving this problem pretty straightforward.

When we receive the string, we create its rolling-hash array, which enables us to get the hash value of any substring in constant time. We iterate over all the even positions such that the resulting partitions are of positive length. If the string is 0 -indexed, the parts will be as follows:

P_1: [0,\frac{i}{2}-1]
P_2: [\frac{i}{2},i-1]
P_3: [i,\frac{i+N}{2}-1], and
P_4: [\frac{i+N}{2},N-1]

Note that division here implies integer division, or taking the floor value of the division result.

When we know the end-points of the parts, we can get their hashes from the hash-array in constant time, and check P_1 and P_2, P_3 and P_4, respectively, for equality.

If P_1=P_2 and P_3=P_4, we increment the count. Then we go on to check the next even index for the next probable partition of the string, into T_1+T_1+T_2+T_2.

Thus, to solve the problem:

  1. Create the rolling-hash array of the string.
  2. Iterate over all the even indices in range [2,N-2] and check if the resulting partition P_1=P_2 and P_3=P_4, using the hash-array.
  3. For every successful partition that satisfies the condition, increment the count.

The setter has used the prefix-function technique, while the tester has used the z-function to solve this problem.

The logic for both of these is same: compute the function for the string as well as its reverse, divide it into parts as described above, and use the two functions to check for equality of the parts. The function from the original string is used to check if P_1=P_2, while the function from the reverse string is used to check if P_3=P_4.

TIME COMPLEXITY:

show

The time complexity is: O(N) per test case,
where N is the length of the string.

Why?

Computing the rolling hash array of a string takes O(N) time. Then we iterate over all the even indices in O(N) time, while checking the parts for equality in constant time.


SOLUTIONS:

Setter
#include <bits/stdc++.h>
 
using namespace std;
 
// char input[] = "input/input00.txt";
// char output[] = "output.txt";
 
const int N = 200010;
 
int a[N],lps1[2][N],lps2[2][N];
string s;
 
void computeLPSArray1(int key) 
{
	int len = 0;
	lps1[key][0] = 0;
	int i = 1; 
 
	while(i < s.size()) 
	{ 
	    if(s[i] == s[len])
	    {
	        len++;
			lps1[key][i] = len;
	        i++;
	    }
	    else
	    {
	        if(len != 0)
	            len = lps1[key][len - 1];
	        else
	        { 
	            lps1[key][i] = 0;
	            i++; 
	        } 
	    } 
	} 
} 
 
void computeLPSArray2(int key) 
{
	int len = 0;
	lps2[key][0] = 0;
	int i = 1; 
 
	while(i < s.size()) 
	{
	    if(s[i] == s[len])
	    {
	        len++;
 
	        if(2*len > i+1)
	        	len = lps1[key][len - 1];
	        
			lps2[key][i] = len;
	        i++;
	    }
	    else
	    {
	        if(len != 0)
	            len = lps1[key][len - 1];
	        else
	        { 
	            lps2[key][i] = 0; 
	            i++; 
	        } 
	    } 
	} 
} 
 
int main()
{
	// freopen(input, "r", stdin);
	// freopen(output, "w", stdout);
 
	int t;
	cin >> t;
 
	while(t--)
	{
		cin >> s;
 
		int n = s.size();
 
		for(int i=0;i<n;i++)
			lps1[0][i] = lps1[1][i] = lps2[0][i] = lps2[1][i] = 0;
 
		computeLPSArray1(0);
		computeLPSArray2(0);
		reverse(s.begin(),s.end());
		computeLPSArray1(1);
		computeLPSArray2(1);
 
		int ans = 0;
 
		for(int i=1;i<n-2;i+=2)
		{
			if((2*lps2[0][i] == (i+1)) && (2*lps2[1][n-i-2] == (n-i-1)))
				ans++;
		}
 
		cout << ans << endl;
	}
 
	return 0;
} 
Tester
//raja1999
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
 
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
 
//std::ios::sync_with_stdio(false);
int z[200005][2];
int solve(string s,int fl){
	int n=s.length();
	int l,r,k,i;
	l=0;
	r=0;
	f(i,1,n){
		if(i>r){
			l=i;
			r=i;
			while(r<n && s[r-l]==s[r]){
				r++;
			}
			z[i][fl]=r-l;
			r--;
		}
		else{
			k=i-l;
			if(z[k][fl]<r-i+1){
				z[i][fl]=z[k][fl];
			}
			else{
				l=i;
				while(r<n && s[r-l]==s[r]){
					r++;
				}
				z[i][fl]=r-l;
				r--;
			}
		}
	}
}
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		string s;
		int ans=0,i,j;
		cin>>s;
		int n=s.length();
		string rev_s="";
		fd(i,s.length()-1,0){
			rev_s+=s[i];
		}
		solve(s,0);
		solve(rev_s,1);
		for(i=1;i<s.length();i+=2){
			j = n-i-2;
			if(j<0){
				break;
			}
			//cout<<
			if(z[i/2+1][0]>=(i+1)/2 && z[j/2+1][1]>=(j+1)/2){
				ans++;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
} 
Editorialist
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
	static class Hashing
	{
	    long[] hash,pow;
	    long P, MOD;
	    int N;

	    Hashing(char str[], long P, long MOD)
	    {
	        this.N=str.length;this.P=P;this.MOD=MOD;
	        hash=new long[N+1];pow=new long[N+1];
	        init(str);
	    }
	    void init(char str[])
	    {
	        pow[0]=1;
	        for(int i=N-1;i>=0;i--)
	        {
	            hash[i]=((hash[i+1]*P)%MOD+(str[i]-'a'+1))%MOD;
	            pow[N-i]=(pow[N-i-1]*P)%MOD;
	        }
	        pow[N]=(pow[N-1]*P)%MOD;
	    }
	    long getHash(){return getHash(0,N-1);}
	    long getHash(int l, int r){return (MOD-(hash[r+1]*pow[r-l+1])%MOD+hash[l])%MOD;}
	}
	public static void main(String[] args) throws IOException
	{
	    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

	    int i,N;

	    int T=Integer.parseInt(br.readLine().trim());
	    StringBuilder sb=new StringBuilder();

	    while(T-->0)
	    {
	        char str[]=br.readLine().trim().toCharArray();
	        Hashing hash=new Hashing(str,31,(int)(1e9+7)); //compute rolling-hash

	        int count=0; N=str.length;
	        for(i=2;i<=N-2;i+=2)
	        {
	            int l1=0,r1=i/2-1; //Part-1
	            int l2=r1+1,r2=i-1; //Part-2
	            int l3=i,r3=(i+N)/2-1; //Part-3
	            int l4=r3+1,r4=N-1; //Part-4

	            //Check if Part-1=Part2 and if Part-3=Part-4
	            boolean C1=hash.getHash(l1,r1)==hash.getHash(l2,r2);
	            boolean C2=hash.getHash(l3,r3)==hash.getHash(l4,r4);

	            if(C1&&C2) count++;
	        }
	        sb.append(count).append("\n");
	    }
	    System.out.println(sb);
	}
}

Feel free to share your approach if it differs. You can ask your doubts below. Please let me know if something’s unclear. I would LOVE to hear suggestions :slight_smile:

27 Likes

Test Cases were weak problem was easy and implementation was heavy(if done “yourself”)

10 Likes

Very Poorly designed Test case :-1:

39 Likes

why some O(n*n) sulution also got accepted???

35 Likes

I didn’t submit it because tym complexity for brute force solution was O(n^2) and it would have exceeded the limit. But after contest I saw even brute force solution were accepted. Setter should keep this in mind and do not set weak test cases .

34 Likes

same thing happen to me aslo bro

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

4 Likes

@admin @akashbhalotia if possible please judge it with better testcases brutforce passed for some cases
see here

4 Likes

it must be get hacked if this were submitted on CODEFORCES

13 Likes

Hi all,

Apologies for the weak test cases in the problem CHEFSHIP. Here’s what actually happened. After preparing and testing the problem, we observed that there’s a need to reduce the load on the servers. So, while making modifications for that, we missed out on including sufficient testcases to break the brute solution. Sorry for the inconvenience caused.

25 Likes

I like your problems. Please make sure it doesn’t happen again.

Its okay, shit happens.
But question was good.

Atleast I am not aware with hashing approach, so would learn something new.
Thank you :slight_smile:

10 Likes

I don’t know why i am getting TLE in CHEFSHIP.
Problem Link- https://www.codechef.com/COOK118B/problems/CHEFSHIP
My Submission - https://www.codechef.com/viewsolution/33308621

i know that complexity of substr is O(n)

Can anybody tell any alternative way to extract substring from a string in an efficient way except substr
or
Can anybody point out a mistake so that i can change something in my code and get AC?

Thanks in Advance!

Pls rejudge the submissions as it can hamper ratings of individuals

15 Likes

This mistake also teach everyone something new.

Can you please include the KMP solution? I am not getting it.

8 Likes

If we reduce the time limit for python, usko nani yaad ayegi :laughing:

2 Likes

I am just a noob so please don’t take it seriously…:slightly_smiling_face:

I tried with kmp just like setter’s solution .Not getting how to remove overlapping length of lps .can you please elaborate a liitle about if(2*len > i+1) @rishup_nitdgp please.
{len = lps1[key][len - 1];}

Chill dude. The only problem is that bruteforce works in python (which shouldn’t happen).

2 Likes