CHEFROUT - Editorial

editorial
, ,
1

Problem Link

Practice

Contest

Author: Praveen Dhinwa

Tester: Pawel Kacprzak and Misha Chorniy

Editorialist: Bhuvnesh Jain

Difficulty

CAKEWALK

Prerequisites

Looping techniques

Problem

You are given an array consisting of ‘C’, ‘E’ and ‘S’ denoting cooking, eating and sleeping respectively. You need to tell whether the array is correct i.e. has ‘C’, ‘E’ and ‘S’ in correct order or not.

Explanation

Solution 1

The problem can be solved as stated in the question itself. All we need to find is whether is the activities recorded by Chef’s dog are in the order Cooking, Eating and Sleeping or not. So, we can group the equal elements together. This can be done easily using a “for” loop as follows:


vector<char> u;
for i in 0 to s.length()-1:
	j = i
	while(j < s.length() && s[i]==s[j]):
		j += 1
	u.push_back(s[i]);
	i = j-1

Now, if size(u) > 3, then answer is definitely “no”. Otherwise, check if it follows the sequence. i.e.


if size(u) == 3, u[0] = 'C', u[1] = 'E', u[2] = 'S'
if size(u) == 2, u[0] = 'C', u[1] = 'S' or u[0] = 'C', u[1] = 'E' or u[0] = 'E', u[1] = 'S'
if size(u) == 1, trivally true

The above will suffice for 100 points as the complexity of the above code is O(n). It may initially seem that the complexity of the above code is O(n^2). To see why the above doesn’t hold, let us analyze the complexity in a different manner. We see how many time each position will be visited. Each position will be visited once, either by the variable i or j. Since there are n locations in total, the complexity becomes O(n).

Solution 2

The question can be solved using information about the state only. Let us denote the states ‘C’, ‘E’, ‘S’ by 0, 1, 2 respectively. Then the solution is “yes” if and only if, state[i] <= state[i+1] for 0 <= i < s.length()-1. The editorialist has used this idea and the implementation can be seen in his solution.

Solution 3

This solution is similar to the second one except that instead of maintaining the state, we just check if the given string corresponding to the required regular expression or not. This is also a builtin function in most languages as well.

For example, the C++ code would be

cout << (regex_match(s, regex("^C*E*S*$")) ? "yes" : "no") << endl;

The java code code be found in the answer below.

Time Complexity

O(n) per test case

Solution Links

Setter’s solution

Tester’s solution

Editorialist solution

2

Even easier with Java regex, here is my [solution][1].
[1]: https://www.codechef.com/viewsolution/13457196

2 Likes
3

#include

using namespace std;

int main()
{
int t;
cin>>t;
string s;
getline(cin,s);
while(t–)
{
getline(cin,s);
int flag=1;
for(int i=0;s[i+1]!=’\0’;i++)
{
if(s[i]==‘C’)
{
if(s[i+1]==‘C’)
i++;
else if(s[i+1]==‘E’)
i++;
else if(s[i+1]==‘S’)
i++;
else {//cout<<“no”<<endl;
flag =0;
break;
}
}
if(s[i]==‘E’)
{
if(s[i+1]==‘E’)
i++;
else if(s[i+1]==‘S’)
i++;
else {//cout<<“no”<<endl;
flag=0;
break;}
}
if(s[i]==‘S’)
{
if(s[i+1]==‘S’ || s[i+1]==’\0’)
i++;
else {//cout<<“no”<<endl;
flag=0;
break;}
}
}
if(flag==1)
cout<<“yes”<<endl;
else cout<<“no”<<endl;
}

return 0;

}

4

It can also be solved through checking their ASCII values … coincidently their order of ASCII values is same as order of priority.
ASCII of ‘C’ < ‘E’ < ‘S’ i.e same as 0 < 1 < 2 {as told in editorial}

/*
Program CHEFROUT
Written by "Vaibhav" aka 'ZodiacBestro'
In 2017
*/

#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define eps 1e-9
#define fast_cin ios_base::sync_with_stdio(false)

const int MOD = 1e9+7;

typedef long long ll;
typedef pair<int,int> pii;

int main()
{
	//freopen("Task.in","r",stdin);freopen("Task.out","w",stdout);
	//fast_cin;
	int t; cin >> t;
	while(t--){
		string s;
		cin >> s;
		char curr,last;
		int i;
		for (i = 1; i < s.size(); ++i)
		{
			curr = s[i];
			last = s[i-1];
			if (int(curr) < int(last) )
			{
				break;
			}
		}
		if (i == s.size())
		{
			cout << "yes\n";
		}
		else{
			cout << "no\n";
		}
		
	}

	return 0;
}