### 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 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.