CHEFFAV - Editorial

editorial
,
1

Favourite String of Chef:

PROBLEM LINK:

Practice

Code Drive Contest Division 1

Code Drive Contest Division 2

Code Drive Contest Division 3

Author: Sobhagya Singh Dewal

Tester: Lavish Gupta , Takuki Kurokawa

DIFFICULTY:

SIMPLE

PREREQUISITES:

Implementation

PROBLEM:

A string is called Chef’s favourite if:
Every substring “chef” must have a substring “code” before it.

You are given a string S of size N, print “AC” if it is Chef’s favourite otherwise print “WA”.
Note that it’s guaranteed that S will contain only lowercase English alphabets and S will always contain “code” and “chef” as a substring.

QUICK EXPLANATION:

If the first occurrence of “code” is before first occurance of “chef” then answer is AC else WA.

EXPLANATION:

Let’s consider 2 cases where in the first case the first occurrence of “chef” is before “code” and in the second case the first occurrence of “code” is before “chef”.
In the first case we can clearly say that there will be no “code” before the 1st “chef” hence the answer is WA.
In the second if the first “code” occurs before first “chef” then it will occur before all “chef” hence the answer will be AC.
Time Complexity: O(4*N) == O(N) for each testcase.

SOLUTIONS:

Setter’s Solution 

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

int f(string s,string a,int n)
{
   for(int i=0;i<(n-3);i++)
   {
      if(s[i]==a[0] && s[i+1]==a[1] && s[i+2]==a[2] && s[i+3]==a[3])
        return i;
   }
   return -1;
}

void myfun()
{ 
   string s;
   cin>>s;
   int n=s.size();
   
   int code=f(s,"code",n);
   int chef=f(s,"chef",n);

   if(code<chef)
   {
      cout<<"AC\n";
   }
   else
   {
     cout<<"WA\n";
   }

}

signed main()
{
  int t = 1;
  cin >> t;
  for (int tt = 1; tt <= t; tt++)
  {
    myfun();
  }
  return 0;
}
Tester's (Lavish Gupta) Solution 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 10;
const int MAX_N = 10000;
const int MAX_SUM_N = 100000;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
int sum_n = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll z = 1000000007;
ll sum_nk = 0 ;

int first_pos(string str , string p)
{
    int ind = -1 ;
    int n = str.size() , m = p.size() ;

    for(int i = 0 ; i + m <= n ; i++)
    {
        int flag = 1 ;
        for(int j = i , k = 0 ; k < m ; k++ , j++)
            if(str[j] != p[k])
                flag = 0 ;
        if(flag && ind == -1)
            ind = i ;
    }
    return ind ;
}
 
void solve()
{   
    int n = readIntLn(1 , MAX_N) ;
    string str = readStringLn(n , n) ;

    for(int i = 0 ; i < n ; i++)
        assert(((str[i] - 'a') >= 0) && ((str[i] - 'a') < 26)) ;

    int flag = 0 ;

    int ind = first_pos(str , "code") ;
    if(ind != -1)
        flag ^= 1 ;

    int ind2 = first_pos(str , "chef") ;
    if(ind2 != -1)
        flag ^= 2 ;

    assert(ind != -1 && ind2 != -1) ;
    // cout << "ind1 = " << ind << " ind2 = " << ind2 << endl ; 

    if(flag != 3)
    {
        cout << "WA" << '\n' ;
        cerr << "flag = " << flag << endl ;
        return ;
    }

    int flag2 = 0 ;

    if(ind < ind2)
    {
        flag2 = 1 ;
        cout << "AC" << '\n' ;
    }
    else
        cout << "WA" << '\n' ;
    cerr << "flag = " << flag << " flag2 = " << flag2 << endl ;
    return ;

}
 
signed main()
{
    //fast;
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif
    
    int t = 1;
    
    t = readIntLn(1,MAX_T);

    for(int i=1;i<=t;i++)
    {    
        solve() ;
    }
    
    assert(getchar() == -1);
    // assert(sum_n <= MAX_SUM_N);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    // cerr<<"Sum of lengths : " << sum_n << '\n';
    // cerr<<"Maximum length : " << max_n << '\n';
    // cerr << "Sum of product : " << sum_nk << '\n' ;
    // cerr<<"Total operations : " << total_ops << '\n';
    // cerr<<"Answered yes : " << yess << '\n';
    // cerr<<"Answered no : " << nos << '\n';
}
Tester's (Takuki Kurokawa) Solution 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        string s;
        cin >> n >> s;
        string ans = "AC";
        for (int i = 0; i < n - 3; i++) {
            if (s.substr(i, 4) == "code") {
                break;
            }
            if (s.substr(i, 4) == "chef") {
                ans = "WA";
            }
        }
        cout << ans << '\n';
    }
    return 0;
}
2 Likes
2

Hi, can someone please let me know what is wrong with my code? It fails one of the tests but I have no idea why- I have looked at other accepted solutions and they appear very similar almost exactly the same as mine!

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

Thank you!

3

For a case “codechefchef”, your code will print WA, but it should be AC. Because their is one “code” before both “chef”.
Like solution was just to check first occurrence of “code” before first occurrence of “chef”.

1 Like
4

Ohh I see- isn’t the question a bit unclear in this sense? But thanks for confirming this makes sense in this case!

5

could have used library function find for getting index
int i, j, n, m;
cin>>n;
string str;
cin>>str;
int a= str.find(“code”);
int b= str.find(“chef”);
if(a<b)
{
cout<<“AC”<<endl;
}
else
{
cout<<“WA”<<endl;
}

1 Like
6

I also solved like this.

7

can someone tell me what is wrong here:
/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int i = 0; i < T; i++) {
int N = sc.nextInt();
String S = sc.nextLine();
int a = S.indexOf(“code”);
int b = S.indexOf(“chef”);
if(a < b) {
System.out.println(“AC”);
}
else {
System.out.println(“WA”);
}
}
}
}