You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

This question is marked "community wiki".

asked 21 Jan '13, 00:25

fushar's gravatar image

3★fushar ♦♦
16345853
accept rate: 0%

edited 21 Jan '13, 01:10

admin's gravatar image

0★admin ♦♦
15.9k347484508


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

link

answered 21 Jan '13, 09:49

supan51191's gravatar image

1★supan51191
1
accept rate: 0%

1

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

(21 Jan '13, 10:07) fushar ♦♦3★

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

link

answered 22 Mar '13, 18:15

shubham26's gravatar image

2★shubham26
6115
accept rate: 0%

edited 22 Mar '13, 21:55

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 ?

link

answered 17 Jun '13, 17:19

geekguy's gravatar image

3★geekguy
122
accept rate: 0%

WHY we iterating Iit from the end of the string ?

link

answered 11 Apr '15, 20:03

gether's gravatar image

3★gether
1
accept rate: 0%

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
link

answered 31 Dec '15, 14:19

sarath127's gravatar image

2★sarath127
1
accept rate: 0%

edited 31 Dec '15, 14:56

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,590
×780
×716
×7
×7

question asked: 21 Jan '13, 00:25

question was seen: 17,031 times

last updated: 31 Dec '15, 14:56