Editorial for DMOPC '20 Contest 7 P1 - Bob and Balance

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 4fecta

Subtask 1

We can simply greedily pair 1s with 2s until we run out of either number, after which we pair the remaining masses arbitrarily.

Time Complexity: \mathcal{O}(N)

Subtask 2

This subtask was intended to reward slower solutions with the correct idea.

Time Complexity: \mathcal{O}(N^2)

Subtask 3

To make things convenient, let's sort the masses in non-decreasing order.

Let's assume there is a mass appearing x > N times. By a basic application of the pigeonhole theorem, we can see that the number of balanced scales must be at least x - N. We can achieve this minimal number of balanced scales by pairing the i-th mass with the (i+N)-th mass in the sorted array. As it turns out, this construction also extends to the case where there is no mass appearing more than N times. No segment of equal values can have a length of more than N, so the i-th and (i+N)-th mass will always be different.

Time Complexity: \mathcal{O}(N \log N)

Note from d: There is a solution that runs in \mathcal{O}(N).


There are no comments at the moment.