Partially correct in "Chef And String" ||please help||

please help :pray:

sol link:-https://www.codechef.com/viewsolution/37290772

Problem link :- https://www.codechef.com/problems/CHRL2

My approach in short:

I took the string now i have to find no.of. “CHEF” in that, so i check for C, now whenever i get ‘H’ i check if i had a previous C or not, if yes decrement the C ( because that C with the help of current H will form CH) again for E if yes (decrement H to form CHE) and now F to form ( CHEF ). This work in O(N).

My Code:

#include<bits/stdc++.h>
using namespace std;

#define FASTIO1 ios_base::sync_with_stdio(false)
#define FASTIO2 cin.tie(NULL),cout.tie(NULL)
#define all(x) (x).begin(),(x).end()
#define ll long long

int main() 
{
    FASTIO1;
    FASTIO2;
    string s;
    cin>>s;
    ll c=0,h=0,e=0,f=0,n=s.length();
    for(ll i=0;i<n;i++)
    {
    	if(s[i]=='C') c++;
    	else if(s[i]=='H' && c>0) c--,h++;
    	else if(s[i]=='E' && h>0) h--,e++;
    	else if(s[i]=='F' && e>0) e--,f++; 
	}
	cout<<f;
    return 0;
}

Your approach: It is a simple brute force i guess, so the efficiency boil downs to O(N^2) which will give you a TLE because string length can be 10^5.

I hope this would help.

2 Likes

Thanks a lot for teaching me such a great method !!! :smiley: :heart:

1 Like

It is very less time consuming solution, thanks ! :blush:

1 Like

Sir please help I am not able to solve this problem https://www.codechef.com/problems/TRAINSET . I have been solving this for a month now.
I am getting correct answers for testcases but facing TLE issue…
I will not ask you any further questions personally but please help for this one .

Ahh !! don’t call me sir i am just like you, a college student.

Moreover i’ve replied to your original thread of that question.

1 Like