CHRL2 - Editorial

general
, , ,
1

PROBLEM LINKS

Contest

Practice

Author: Roman Furko

Tester: Sergey Kulik

Editorialist: Vinod Reddy

DIFFICULTY:

simple

PREREQUISITES:

basic dp

EXPLANATION

Subtask 1:

We will implement an O(N^2) algorithm for this subtask as N < 2000 this will pass. So the main observation of this algorithm is that consider the ‘F’ with smallest index such that there exists a subsequence ending at this ‘F’ with characters ‘C’,’H’,’E’,’F’.Now consider such a subsequence T {‘C’,’H’,’E’,’F’}. Now this ‘F’ should be removed from the string in one of the moves in the optimal solution or else if this ‘F’ is not removed and the ‘E’ is removed then we can exchange the ‘F’ removed with the ‘E’ with our ‘F’. if ‘E’ is also not removed then we can extend our logic to ‘H’. if ‘H’ is not removed then we extend the same logic to ‘C’. It cannot be that all of the four characters are not removed.

Now when we remove this ‘F’ in a move it can always be removed along with the nearest ‘E’ to the left of it because if it’s not the case either ‘E’ is not removed at all in which case the presently used ‘E’ can be replaced with the nearest ‘E’ or this ‘E’ is used with another ‘F’ in which case the ‘CHE’ of second ‘F’ can be exchanged with ‘CHE’ of the first. Similarly we ‘H’ be the nearest one to the left of chosen ‘E’ and similar case for ‘C’. So we find such subsequence and remove those four characters and repeat the same procedure for remaining string
So for example lets take the string CHECHFECF.

1  2  3 4  5 6  7 8  9
C H E C H F E C F

The first ‘F’ with a sequence possible will be the one at position 6. And the corresponding ‘E’ will be the one at position 3 and ‘H’ at 2 and C at 1. When we remove the characters we will be left with CHECF and again we follow same logic and remove one more ‘CHEF’.

Implementation :
It can be implemented in O(N^2). You can use a boolean array to track whether a symbol is removed or not and for each ’F’ from left to right try to find the first ‘E’ to the left of it which is not removed and then first ‘H’ which not removed to the left of ‘E’ and then ‘C’. Then remove these characters by making their tracking variables to true. It’s easy to implement. For the code please check editorials solution.

Subtask 2 :
This is almost same as above algorithm but just a good implementation.

Since at every time in the above algorithm we check for the nearest next character to left which is not used (for ‘F’ we check for nearest left ‘E’,for ‘E’ we check for ‘H’,for ‘H’ we check for ‘C’) we will precompute the information. We will maintain four vectors one each for positions of each of characters ‘C’,’H’,’E’,’F’. so the arrays will be P[char][int[]].

We loop from left to right. Whenever ‘C’ comes we insert it’s position into P[‘C’] . Whenever we encounter ‘H’ we check if P[‘C’] is empty. If it’s empty then this ‘H’ is not useful as we cannot use it to form a subsequence so we throw it away. If P[‘C’] is not empty then we can map ‘H’ to the last position in P[‘C’] and so whenever ‘H’ is used we use it with ‘C’. Since the ‘C’ is mapped to ‘H’ we just remove the last element of P[‘C’]. So the array P[‘H’] are positions of ‘H’ for which there is a ‘C’ mapping and not mapped to any ‘E’. whenever ‘E,’F’’ comes we do the same thing as ‘H’. So finally the elements of C[‘F’] contains positions of ‘F’ for which there is a mapping to ‘E’ and this ‘E’ has a mapping to ‘H’ and this ‘H’ has a mapping to ‘C’.So finally no of elements in C[‘F’] will be our answer.

Here a simple observation will help. We really need not maintain the positions in P[char][int[]]. We just need to know the size of P[‘C’],P[‘H’],P[‘E’],P[‘F’].So now new array will be NP[char][int] .When removing element originally in P[‘C’],P[‘E’],P[‘H’] we just decrease the value in NP[‘C’],NP[‘H’],NP[‘E’]. When we were inserting before we just increase the value against character. See the setter’s code for exact implementation.

SOLUTIONS

Setter’s Solution: CHRL2.cpp

Tester’s Solution: CHRL2.cpp

Editorialist’s Solution: CHRL2.cpp

4 Likes
2

#include< iostream>

 #include< cstdio>

 #include< cstring>

 char a[100005];

 int main(){

    scanf("%s",a);

    int i,c,ch,che,chef;
    c=ch=che=chef=0;

    for(i=0;i<strlen(a);i++){
        if(a[i]=='C'){
            c++;
        }
        else if(a[i]=='H'){
            if(c>0){c--; ch++;}
        }
        else if(a[i]=='E'){
            if(ch>0){ch--; che++;}
        }
        else if(a[i]=='F'){
            if(che>0){che--; chef++;}
        }
    }
    printf("%d\n",chef);
    return 0;
}
10 Likes
3

oh I had it like you but without c-- in the if str[i] == 'H', I had instead if str[i] == 'F' { c--; h--; e--; f++} which was wrong :stuck_out_tongue:

4

very neat code :wink:

5

glad u liked it… :smiley:

6

had exactly the same code (though the name of variables are different ) :slight_smile:
very good writing style … easy to understand…

7

Tell me if my approach is wrong.Aren’t we just calculating the number of time the word CHEF can be formed using those characters only once?..if yes then my logic is to just count the number of c’s ,f’s,e’s and h’s and the minimum of them is the count we require.
THANK YOU

c,h,e,f=0,0,0,0
A=raw_input()
for i in range(0,len(A)):
	if A[i]=="C":
		c+=1
	elif A[i]=="E":
		e+=1
	elif A[i]=="F":
		f+=1
	elif A[i]=="H":
		h+=1
x=min(c,e,f,h)
print(x)

edit:
Do we require the CHEF to be in the same order in the given string?...
8

@broadword: did u get the answer to your query…I am also having the same query. i also used the same algo.

9

consider , FEHCCHEF , ANS=1 but ur ANS=2

10

#include
#include<string.h>
using namespace std;
int main()
{ char a[100000]; char b[20]=“CHEF”;
char *p=b; int c=0,i; int d[100000];
cin>>a;
for(i=0;i<100000;i++)
d[i]=0;
for(i=0;i<strlen(a);i++)

if(d[i]==0)
if(a[i]==*p)
if(*p==‘F’)
{p=b;
c++; i=0; d[i]=1;
}
else {
p++; d[i]=1;}

cout<<c;

return 0;
}

11

@admin
Below is the solution is of a problem of codechef[1].
I have applied the right algorithm I guess and it should pass all the test cases but I am facing a problem. For every test case where the string size is more than 32 the result seems to be gibberish and garbage and for string size less than 32 the answer comes out to be right and seems to pass every test case as well.

    using namespace std;
    int main(int argc, char const *argv[])
    {
        string str;
        cin>>str;
        int i=0;
        vector<pair<char,int>> v;
        v.push_back(make_pair('C',0));
        v.push_back(make_pair('H',0));
        v.push_back(make_pair('E',0));
        v.push_back(make_pair('F',0));
        int length = str.size();
        std::cout<<length<<std::endl;
        str.resize(length);
        while(length--)
        {
           
            if(str[i]=='C')
                v['C'].second++;
            else if (str[i]=='H'&& v['C'].second)
            {
                v['H'].second++;
                v['C'].second--;
            }
            else if (str[i]=='E'&& v['H'].second)
            {
                v['E'].second++;
                v['H'].second--;
            }
            else if (str[i]=='F'&& v['E'].second)
            {
                v['F'].second++;
                v['E'].second--;
            }
            else if(str[i]=='\0')
                break;
            i++;
        }
        cout<<v['F'].second<<endl;
        v['F'].second=0;
        return 0;
    }

//Problem Link [1]::https://www.codechef.com/problems/CHRL2
//submission link[2] :: https://www.codechef.com/submit/complete/8823298

I finally asked this question at Stackoverflow here. Please refer to the link if anyone has a similar problem. :slight_smile:

12

Hmm i am using a ruby code for this…not sure why its breaking through

 #!/usr/bin/env ruby
    
    get_string=gets
    array_comp = ""
    chef_count = 0
    
    get_string.split('').each do |character|
      if character == "C" && array_comp == ""
        array_comp.concat("C")
      end
      if character == "H" && array_comp.length == 1
        array_comp.concat("H")
      end
      if character == "E" && array_comp.length == 2
        array_comp.concat("E")
      end
      if character == "F" && array_comp.length == 3
        array_comp.concat("F")
        chef_count += 1
        array_comp = ""
      end
    end
puts chef_count.to_i

Is there something I am missing here? https://www.codechef.com/submit/complete/8954982

13

hi

14

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sc(a) scanf("%d",&a)
#define gc getchar_unlocked
#define scl(a) scanf("%lld",&a)
#define ll long long
#define all© c.begin(),c.end()
#define N 10010
#define mod 1000000007

int dp[26];

int main()
{
string s;
cin>>s;
int i;
memset(dp,0,sizeof(dp));

int ans=0,x=1000100;

for(i=0;i<s.length();i++)
{
	dp[s[i]-'A']++;
	if(s[i]=='F')
	{
		if(dp[2]!=0 && dp[4]!=0 && dp[5]!=0 && dp[7]!=0)
		{
			ans++;
			dp[2]--;
			dp[4]--;
			dp[5]--;
			dp[7]--;
		}
	}
	if(dp[2]==0)
		dp[4]=dp[5]=dp[7]=0;
	if(dp[7]==0)
		dp[4]=dp[5]=0;
	if(dp[4]==0)
		dp[5]=0;
}

cout<<ans<<endl;

return 0;

}

Please tell why I am getting WA in one of the test cases .
Which Test case is missing in my solution .

1 Like
15

#include<stdio.h>
#include<string.h>
void main()
{
char s[100000];
int i;
int c=0,h=0,e=0,f=0,l;
scanf("%s",s);
l=strlen(s);

for(i=0; i<l; i++)
{
    if(s[i]=='C')
    {
        c++;

    }
    else if(s[i]=='H')
    {
        if(c>h)
            h++;

    }
    else if(s[i]=='E')
    {
        if(h>e)
        {
            e++;
        }

    }
    else if(s[i]=='F')
    {
    if(e>f)

f++;
}

}

printf("%d",f);
}

is anything wrong with my code ?
it is giving run time error

16

#include
#include<string.h>
using namespace std;
int main()
{
long int counte,counth,countc,countf,ans;
char ch[100001];
cin>>ch;
long int n=strlen(ch);
countc=counth=counte=countf=ans=0;
for(int i=0;i<n;i++)
{
if(ch[i]==‘C’)
{
//cout<<“STARTED FOUNDING CHEF . C LETTER FOUNDED\n”;
countc++;
}
else
if(ch[i]==‘H’&&countc>0)
{
//cout<<“H LETTER FOUND.\n”;
counth++;
}
else
if(ch[i]==‘E’&&counth>0&&countc>0)
{
//cout<<“E LETTER FOUND.\n”;
counte++;
}
else
if(ch[i]==‘F’&&counte>0&&counth>0&&countc>0)
{
//cout<<“F LAST LETTER FOUND.RESETTING ALL.\n”;
counte=counth=countc=0;
//cout<<“ANSWER NOW INCREMENTED.\n”;
ans++;
//cout<<“ANSWER NOW “<<ans<<” \n”;
}
}
cout<<ans<<"\n";
}
Please tell whats wrong in my code??

17

#include
#include<string.h>
using namespace std;
int main()
{

long int counte,counth,countc,countf,ans;

char ch[100001];
cin>>ch;
long int n=strlen(ch);
countc=counth=counte=countf=ans=0;
for(int i=0;i<n;i++)
{
	if(ch[i]=='C')
	{
		//cout<<"STARTED FOUNDING CHEF . C LETTER FOUNDED\n";
		countc++;
	}
	else
	if(ch[i]=='H'&&countc>0)
	{
		//cout<<"H LETTER FOUND.\n";
		counth++;
	}
	else
	if(ch[i]=='E'&&counth>0&&countc>0)
	{
		//cout<<"E LETTER FOUND.\n";
		counte++;
	}
	else
	if(ch[i]=='F'&&counte>0&&counth>0&&countc>0)
	{
		//cout<<"F LAST LETTER FOUND.RESETTING ALL.\n";
		counte=counth=countc=0;
		//cout<<"ANSWER NOW INCREMENTED.\n";
		ans++;
		//cout<<"ANSWER NOW  "<<ans<<" \n";
	}
}
cout<<ans<<"\n";

}
Please tell whats wrong in my code??

18

I don’t know whats wrong in my below code. Kindly help me to find out the error in that.

def string_manipulation(ipstring):
cond = ‘CHEF’
result = 0
alist = list(map(lambda x: x,ipstring))
if (len(ipstring) >= 1 and len(ipstring) <= 100000) and ipstring.isupper() == True:
ipstring_indexes = [x for x in range(len(alist)) if alist[x]==list(map(lambda x: x,cond))[0]]
for loop in range(0,len(ipstring_indexes)):
if len(ipstring_indexes)-1 != loop:
num = alist[ipstring_indexes[loop]:ipstring_indexes[loop+1]]
else:
num = alist[ipstring_indexes[loop]:len(alist)-1]
if “”.join([n for i, n in enumerate(num) if i==0 or n != num[i-1]]) == cond:
result = result+1
else:
result = 0
return result
print string_manipulation(raw_input(‘Enter String’))

19

The above code written in Python

20

I have the following solution. Can someone tell me what’s wrong with the logic?

<?php

$str = fgets(STDIN);

$chef = 'CHEF';
$pointer = 0;
$count = 0;

for ($i=0; $i<strlen($str); $i++)
{
	if ($str[$i] === $chef[$pointer])
	{
		if ($pointer === 3)
		{
			$pointer = 0;
			$count++;
		}
		else
		{
			$pointer++;
		}
	}
}

echo $count;