problem in understanding approach of CHRL2

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

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;
}
1 Like

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

1 Like