PROBLEM LINKSDIFFICULTYSIMPLE PREREQUISITESGreedy PROBLEMWe 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 EXPLANATIONIterate 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. EXPLANATIONFirst, let's introduce some notations.
Then, let's introduce an intuitive yet important lemma. Lemma 1. All occurrences of "CHEF"s in S must be nonoverlapping. 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: By Theorem 1, we can derive the following greedy solution. for i = 1; i ≤ N3; 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 = N3; i ≥ 1; i: if can_replace(S[i3.. i], "CHEF"): replace(S[i3..i], "CHEF") for i = N3; i ≥ 1; i: if S[i] == '?': S[i] = 'A' The time complexity of this solution is O(N). SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 21 Jan '13, 00:25

What is wrong in this code?? it is giving right answers for all the tests cases. include <string>include<iostream>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<l3) { 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; } answered 22 Mar '13, 18:15

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 ? answered 17 Jun '13, 17:19

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
answered 31 Dec '15, 14:19
