## B - RGB Matching Editorial by evima

If `R`

, `G`

, and`B`

all appear even numbers of times, the answer is \(0\). Below, we assume `R`

and `G`

appear odd numbers of times and `B`

appears an even number of times. (We can handle the other cases similarly.)

Positive dissatisfactions only result from making pairs of `RG`

, `GB`

, `BR`

.

We can see that there is an optimal solution with at most one `RG`

pair, at most one `GB`

pair, and at most one `BR`

pair. This is because if a solution has two `RG`

pairs, for example, we can recompose two of them into an `RR`

pair and a `GG`

pair, which will not increase the total dissatisfaction.

We can also see that there is an optimal solution with at most two pairs that are `RG`

, `GB`

, or `BR`

. This is because if a solution has an `RG`

pair, a `GB`

pair, and a `BR`

pair, we can recompose them into an `RR`

pair, a `GG`

pair, and a `BB`

pair, which will not increase the total dissatisfaction.

From these two facts and our assumption, we can see that one of the following is true for the optimal solution:

- It has one
`RG`

pair, and all other pairs are`RR`

,`GG`

, or`BB`

. - It has one
`GB`

pair and one`BR`

pair, and all other pairs are`RR`

,`GG`

, or`BB`

.

To find the smallest dissatisfactions in these cases, we can simply find the smallest difference in cuteness between `R`

and `G`

, between `G`

and `B`

, and between `B`

and `R`

, because if the `GB`

pair and the `BR`

pair shares the same dog, it will not be better than making an `RG`

pair. This solution will run fast enough in \(O(N \log N)\) time, since the bottleneck is sorting.

posted:

last update: