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

**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:

#### Subtask 1

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

**Time Complexity:**

#### Subtask 2

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

**Time Complexity:**

#### Subtask 3

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

Let's assume there is a mass appearing times. By a basic application of the pigeonhole theorem, we can see that the number of balanced scales must be at least . We can achieve this minimal number of balanced scales by pairing the -th mass with the -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 times. No segment of equal values can have a length of more than , so the -th and -th mass will always be different.

**Time Complexity:**

Note from .

: There is a solution that runs in
## Comments