B - RGB Matching Editorial by evima
If R
, G
, andB
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 areRR
,GG
, orBB
. - It has one
GB
pair and oneBR
pair, and all other pairs areRR
,GG
, orBB
.
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: