# CHEFGP - Editorial

Practice

Contest

Author: Dmytro Berezin

Tester: Alexey Zayakin

Editorialist: Jakub Safin

EASY

greedy

### PROBLEM

You’re given two integers x,y and a string s containing only characters a and b. Find one possible way to reorder the characters in s so that the number of characters * we need to add to ensure there’s no substring of x+1 consecutive a-s or y+1 consecutive b-s is the smallest possible.

### QUICK EXPLANATION

An optimal string for less b-s than a-s has the form aa..ba..ba..ba..a where all substrings between b-s except the last one have length \le x and the last one has minimum length. Assign a-s greedily to minimise that length.

### EXPLANATION

The problem statement is complicated, but the number of *-s we’re trying to minimise boils down to this:

• find the first position when x+1 consecutive a-s or y+1 consecutive b-s appear
• insert * before the last (x+1-th or y+1-th) of these characters - this corresponds to giving the dissatisfied person a kiwi first
• repeat as long as possible

If we have a maximal substring of n consecutive a-s (that can’t be extended to n+1), we’ll need to repeat the above process \left\lfloor\frac{n-1}{x}\right\rfloor times, since we’re always cutting off x characters and decreasing n by x as long as n > x; similarly, it’s \left\lfloor\frac{n-1}{y}\right\rfloor for n consecutive b-s. Now we can afford to ignore *-s (we can add them at the end of the algorithm) and focus on finding the string consisting only of ab with min. cost.

Let’s denote the number of characters a by n_a and the number of b-s by n_b. Note that the output only depends on n_a and n_b, not the order of characters in the initial string.

## Lemma: if n_a \ge n_b, then there’s an optimal solution with no two consecutive b-s

Proof: consider an optimal solution with some two consecutive b-s. If it starts or ends with a, we can move one of the b-s to the beginning. Otherwise, let’s look at the places after each a. There are at least as many a-s as b-s and at least one of the b-s (the second of our two consecutive b-s) definitely doesn’t occur right after a, so there must be an a such that after it, there’s the end of the string or an a; we can move one of our b-s after the first such a.

This way, we decrease the length of one maximal substring of consecutive b-s, add a maximal substring with length 1 (and cost 0 since x > 0) and maybe do the same for a-s. The cost can’t increase in such an operation. If we repeat that often enough, we’ll come to a situation where no two consecutive b-s occur. QED.

## Lemma: there’s an optimal solution with at most one maximal substring with non-zero cost

Proof: without loss of generality, let’s assume n_a \ge n_b; as per the previous lemma, let’s take one optimal solution without consecutive b-s. If there are two maximal substrings (of a-s) with lengths l_1,l_2 > x in it, let’s write l_1=1+k_1x+r_1, l_2=1+k_2x+r_2 with k_{12} > 0 and 0 \le r_{12} < x. The total cost of these two substrings is then k_1+k_2. We can move k_1x a-s to the second substring, getting substrings with non-zero lengths 1+r_1,1+(k_1+k_2)x+r_2; their cost is still k_1+k_2.

This way, we can convert any solution with minimum cost into another solution with minimum cost and at most one maximal substring of a-s with length > x and all b-s isolated.

## Constructing the solution

Without loss of generality, we can assume the substring with length > x is the last one. Our solution (before adding *-s) can then be written using maximal substrings of lengths a_1,\dots,a_{n_b},l as: a\times a_1, b, a\times a_2, b, …, a\times a_{n_b}, b, a\times l. Here, a_1+\dots+a_{n_b}+l=n_a, 1 \le a_1,\dots a_{n_b} \le x so these have cost 0 and we want the cost of the last substring to be minimal, so l should be minimised.

That can be done greedily. First, let’s take all a_i=1 and subtract n_b from n_a. Then, we’re going to determine the final values of all a_i one by one. For each a_i, we can add y=\mathrm{min}(n_a,x-1) to it and subtract y from n_a; this way, we’re making a_i as large as possible. If we reach n_a=0 at some point (actually, this happens when xn_b \ge n_a initially), we’ve created a solution with cost 0. Otherwise, all a_i must be equal to x (we’ve added x-1 to each of them) and we can set l equal to the current n_a. Obviously, it’s impossible to make l any smaller in such a case, since all a_i are already maximal.

Then we just need to add the *-s (kiwis) and we’re done. The time and memory complexity of this algorithm is O(n_a+n_b) just due to reading the input and printing the output; it can be improved to O(1) memory if we read the input and print the output by individual characters.

### AUTHOR’S AND TESTER’S SOLUTIONS

Setter’s solution

Tester’s solution

Editorialist’s solution

can we use dynamic programming here like
i) including the a at position i
ii) including the b at position i

then answer is maximum of the two conditions??

Lemma: if n_a≥n_b then there’s an optimal solution with no two consecutive b-s.

In order to prove this Lemma, we need to show that if there are consecutive b-s, either the sentence starts or ends with a or there is at least two consecutive a-s. The proof of this part can also be given by pigeon-hole principle as follows-

Case-1: String starts or ends with a-s. There is nothing to prove then.

Case-2: Consider the case when the string doesn’t start or end with a-s. Suppose two b-s are consecutive. Then there are n_b - 1 places in between and there are n_a a-s to place. By pigeon-hole principle we get that there is at least two consecutive a-s.

Here is a video editorial on the problem.
Cheers!

2 Likes

The problem page says that the author is Dmytro Berezin, but the editorial says the setter is someone else.
Can the concerned authority please look into it?

1 Like

Error in copying, I guess. Fixed.

Thanks for that!