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)$.