Subtask 1

We can simply greedily pair ~1~s with ~2~s 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)~.