problem in understanding approach of CHRL2

general
, ,
1

Hi, im having problem in understanding the approach mentioned in the editorial of this problem - https://www.codechef.com/LTIME08/problems/CHRL2 . Please can someone share a better/easy approach ??

Thanks :slight_smile:

1 Like
2

Lets Understand this question from bottom up manner. Here we need the word CHEF as sub-sequence. Since we maintain the count of every consecutive word to 0 i.e., C=CH=CHE=CHEF=0. Now to count of word CHEF we need to check whether ‘CHE’ word occur before the letter ‘F’ in sub-sequence or not. And for sub-sequence ‘CHE’ we need to check whether ‘CH’ occur prior to the letter ‘E’ or not. And for ‘CH’ we need to check only the letter ‘C’ occur prior to the letter ‘H’ or nor.

So According to this, whenever we encounter the letter ‘C’ just increment the Count of ‘C’ and move on. Now whenever we encounter the letter ‘H’, we first check whether ‘C’ has been visited or counted or not. If It has been counted then we will increment the counter of ‘CH’ and decrements the count of ‘C’ because we have counted this letter in ‘CH’. Same process repeats for rest of the word.

I hope you will get this simple explanation rather than scary DP which is mentioned in editorial. Here is the same code mentioned in First comment of editorial.

#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;
}
3

Thanks a lot!! It helped!! :slight_smile:

1 Like