S03E02 - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Kanhaiya Mohan
Tester: Nishant Shah, Divyansh Tyagi, Syed Ali Aatif
Editorialist: Akshit Dhoundiyal

DIFFICULTY

Easy

PREREQUISITES

Basic observation, Substring Manipulation

PROBLEM

Given a string S consisting of N upper-case letters. You need to determine the maximum length of the string that can be obtained in at most K operations such that the number of distinct letters in it is 1. In one operation you can select a prefix, of any size, from the string and remove a suffix of that prefix, of any size, from the string.

EXPLANATION

To understand how a given string is finally converted to a string with all the letters the same (or to an empty string) by performing at most K moves, we first need to figure out how a move changes the current string.

Exploring “a move”

A single valid move consists of:

  1. Taking out a substring of any size from the left side of the string.
  2. Removing a part of any size from the right of that removed substring.
  3. Adding back the remaining substring to the front of the initial remaining string.

In other words, each move is equivalent to removing any subarray from the string.

Example:

Consider the string ABCDEFG, before and after a valid move.

By observation, we can see that at the end of a valid move, a substring of the given string is removed.

***Note: ***We find the maximum length of string that can be obtained for each letter of the English alphabet one by one. The maximum out of those values will be our answer for the test case.

Procedure to find the maximum length of string for a letter under consideration:

Considering the sample test case 1 with the letter A:

We start with the division of the complete string into 3 parts - prefix, middle and suffix.

Prefix and suffix are groups of maximum contiguous occurrences of the letter from the beginning and the end of the string respectively. The remaining part of the string is the middle part.

We then traverse through the middle part to find similar groups of contiguous occurrences of the letter. The sizes of all such groups encountered is pushed into an array, which is reverse-sorted afterwards.

With maximum K moves (K>0), we can select K-1 groups in the order of decreasing size from the middle part. In other words, we take out the first K-1 elements exhaustively from the array.

The sum of the sizes of such groups is the maximum length that can be obtained for that letter.

For letter A, in this case, the max length will be 1+(1)+1 = 3

Finally, the maximum value of all the max lengths for each letter is our answer

Check out these additional examples for a clearer understanding of internal cases with letters.

Alternate example 1:

For N = 13, K = 4 moves

Maximum length for letter A = 2 + (3+2+1) + 0 = 8

The substrings hypothetically deleted in the 4 moves are {B, C, BD, E} in no particular order.

Alternate example 2:

For N = 13, K = 3 moves

Maximum length for letter A = 2 + (3+2) + 0 = 7

The substrings hypothetically deleted in the 3 moves are {B, CABD, E} in no particular order.

Alternate example 3:

For N = 13, K = 3 moves

Maximum length for letter B = 0 + (1+1) + 0 = 2

The substrings hypothetically deleted in the 3 moves are {AA, AACA, DAAAE} in no particular order.

Special Case 1: If K = 0,

In this case, our initial string and the final string will be the same for all the letters, as we cannot make any changes to the string. If the string contains any letter other than the letter under consideration, then the max length for that string will be 0. On the other hand, if the string only consists of that letter, then the max length will be the length of the string itself.

Special Case 2: If K != 0 and the string just contains 1 unique letter,

Using the approach discussed above will lead to an error in this case. Here’s why:

The prefix and suffix parts will cover the entire string when the letter under consideration and the unique letter in the string are the same, so the final answer produced will be twice the length of the string.

But the answer for this case should be N, where N is the length of the string. So, if we return min(N, prefix+middle+suffix), then this condition will be automatically taken care of.

SOLUTIONS

Setter's Solution
3 Likes

Can someone please provide a test case where my code will give WA output.
link:- https://pastebin.com/R3zNFnFD

Try this testcase:

1
10 1
DCADBBBADD

The correct answer is 3 (“DDD”)

Can you also provide a test case which my solution is missing Solution: 54539990 | CodeChef?

1 Like

I understood the miskate.
Thank you for your time.

Can someone please provide a test case where my code will give WA output.
link:- solution

Try to use stress testing, your code is difficult to read :sweat_smile:

u can also do in linux (google it)

1 Like

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

Can anybody please tell me where is my code failing, I have applied the same concept but with a little complex implementation.

My code goes wrong only for the 1st test case.
Could you please help me figure it out?
@notsoloud @nishant403 @mr_mastermind @mafailure @ssvb

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

Can anyone please help me figure out why I’m getting WA. I tried stress-testing against AC solutions but couldn’t find any test-cases with mismatching answers.
https://www.codechef.com/viewsolution/54786325

how much would you rate this problem in terms of codeforces rating ?

Maybe around Codeforces Div.2 C? But it’s very subjective and different people will have different opinions.

somewhat around 1400-1600 range ?

Codeforces problem difficulty X means that a person with rating X had a roughly 50% chance to solve it during the contest. While being distracted by the other problems too, so it isn’t like people have the whole 2 hours available to spend on that problem alone. See more explanations here. Accurate problem difficulty estimation needs to account for the actual contest performance of many people (preferably hundreds or more).

My current rating on Codeforces is around 1500. I spent 1.5 hours to successfully solve this S03E02 problem during its CodeChef contest. What does this tell us about its difficulty? Maybe the difficulty range 1400-1600 is approximately correct? But more likely we just don’t have enough data at hand.

For a more accurate estimate, somebody could dig up the CodeChef’s contest results data and find everyone, who solved this problem. Then guess their Codeforces ratings (or do some kind of approximate CodeChef->Codeforces rating conversion). Filter out cheaters. And finally do calculations as described in the Codeforces blog.

BTW, why are you interested in the Codeforces difficulty rating of this problem?

nothing serious at all, just felt it to be a little tough, so got curious bout it’s rating