MANYCHEF - Editorial

PROBLEM LINKS

Practice

Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Greedy

PROBLEM

We are given a string S. Each character of S is either a question mark (’?’) or an uppercase letter (‘A’-‘Z’). Replace each question mark with an uppercase letter in such a way that the resulting string contains as many “CHEF” as possible. If there is more than one possible resulting string, output the lexicographically smallest one.

QUICK EXPLANATION

Iterate the string S from the end of the string to the beginning. Each time we can replace the current positions with the string “CHEF”, we replace with it. Then, change all remaining question marks with character 'A’s.

EXPLANATION

First, let’s introduce some notations.

  • N = the number of characters of S.
  • S[i] = the i-th character of S (1-based).
  • S[i..j] = the substring of S consisting of the i-th character of S through the j-th character of S.

Then, let’s introduce an intuitive yet important lemma.

Lemma 1. All occurrences of "CHEF"s in S must be non-overlapping.

Proof. The string “CHEF” cannot overlap with itself because it consists of 4 distinct characters. This is in contrast to, for example, string “ABAB”, which can overlap with itself. In this case, we can have a string with two overlapping "ABAB"s: “ABABAB”.

Now that Lemma 1 is proved, we can come up with the following theorem.

Theorem 1. Consider any string S. If we can replace S[1…4] with “CHEF”, then it is optimal to replace it.

Proof. The proof is by contradiction. Suppose that S can contain at most X "CHEF"s. Since "CHEF"s cannot overlap each other, the next occurrences of "CHEF"s must be at least from position 5. If we do not replace S[1…4], all occurrences of "CHEF"s must be contained in S[5…N]. Let Y be the maximum number of "CHEF"s that S[5…N] can contain. For Theorem 1 to be not optimal, it must be the case that Y > X. But it is not impossible, because:

X = the maximum number of "CHEF"s in S[1…N]

= the maximum number of "CHEF"s in S[1…4] concatenated with S[5…N]

= 1 + Y.

By Theorem 1, we can derive the following greedy solution.

for i = 1; i ≤ N-3; i++:
    if can_replace(S[i..i+3], "CHEF"):
        replace(S[i..i+3], "CHEF")

Now, let’s move to the next lemma.

Lemma 2. All remaining occurrences of '?'s in S that were not replaced by the previous iteration should be replaced with ‘A’.

Proof. We want to have the lexicographically smallest resulting string. The lexicographically smallest letter is ‘A’, so it is always better to replace the question marks with 'A’s.

It seems that now we have found a working solution. However, consider the case “???”. If we apply the previous solution, the resulting string would be “CHEFAAA”, whereas the correct solution should be “AAACHEF” because it is lexicographically smaller. We can fix this easily by iterating the string S backwards (the previous lemma and theorem would still apply) so that all occurences of "CHEF"s are “as to the right as possible”.

Here is the pseudocode of the final solution.

for i = N-3; i ≥ 1; i--:
    if can_replace(S[i-3.. i], "CHEF"):
        replace(S[i-3..i], "CHEF")
for i = N-3; i ≥ 1; i--:
    if S[i] == '?':
        S[i] = 'A'

The time complexity of this solution is O(N).

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

3 Likes

What about C???F
According to this algorithm it would give CHEFF while lexicographically smaller would be CCHEF

No, according to this algorithm it would get CCHEF because it iterates from the end of the string. See the pseudocode.

1 Like

What is wrong in this code??
it is giving right answers for all the tests cases.

#include
#include

using namespace std;

int main()
{
int t;
cin>>t;

while(t–)
{
int i=0,j=0,c,k,l;
string s="";
char b[4]={‘C’,‘H’,‘E’,‘F’};
cin>>s;
l=s.length();
while(i<l-3)
{ c=0;
for(j=0;j<4;j++)
{
k=3;
char p=s.at(i+j);
if(p==’?’)
s.replace(i+j,1,“A”);
p=s.at(i+j);
if(p==‘A’ || p==b[j] || p==b[k])
c++;
k–;
}
if(c==4)
{
s.replace(i,4,“CHEF”);
i+=4;
}
else i++;
}
cout<<s<<"\n";
}
return 0;
}

Are we iterating from the end of the string so that we can get lexicographically small string ?

  1. If we need to find lexicographically large string then from when should we start to loop ? (from start or from the end)

  2. How would we tackle the problem if we have CAEHEH instead of CHEF ?

WHY we iterating Iit from the end of the string ?

Hi… I would like to know for which testcases my Solution is failing. From my end, I could see that all testcases are passing. Can someone please help on this ?

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

  • ???CIELIS???E? --> CHEFCIELISACHEF
  • ???CIELISOUR???F --> CHEFCIELISOURCHEF
  • T?KEITE?SY --> TAKEITEASY
  • ??? --> CHEFCHEF
  • ??? --> AAACHEF
  • C???F --> CCHEF

Somebody pls tell the flaw test case in my submission
https://www.codechef.com/submit/complete/18634328

@e_6151223

The link which you have provided is showing access denied.

https://www.codechef.com/viewsolution/18634328 use this link…

We should iterate from the end of the string. consider this example:

???

if we iterate from end: output-> ACHEF

if we iterate from beginning: output-> CHEFA

we can see that ACHEF is lexicographical smaller. If we iterate from the end than we can put the unused ques marks in starting to be A, hence making the string lexicographical smallest.