PROBLEM LINK
Author: Dmytro Berezin
Tester: Alexey Zayakin
Editorialist: Jakub Safin
DIFFICULTY
EASY
PREREQUISITIES
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 consecutiveb-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.