CHEFGP - Editorial




Author: Dmytro Berezin

Tester: Alexey Zayakin

Editorialist: Jakub Safin






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.


An optimal string for less b-s than a-s has the form 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.


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.


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.


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!