Missing Proof for why greedy works
Editorial was good at discussing solution, but I think needs proof why the greedy works. First, assume we start with full partition (everything not yet merged).
Define happiness as h(P)=P_{cnt}P_{sum}.
Claim 1: It is better to merge two partitions with nonnegative sum.
\because This is easy to show. Suppose we have two partitions A and B, with A_{sum},B_{sum}\geq 0. Then:
h(A)+h(B)=A_{cnt}A_{sum}+B_{cnt}B_{sum}\leq(A_{cnt}+B_{cnt})(A_{sum}+B_{sum})=h(A\cup B)
The right side expands to the left side plus some nonnegative value, so the inequality is correct.
Claim 2: It doesn’t make sense to merge two negative partitions.
\because Same reasoning from claim 1, but now the right side will have an extra negative value.
Claim 3: Adding a larger number to a nonnegative partition is better than adding a smaller number.
\because Let a < b. We show that adding b to partition P (P_{sum}\geq 0) is more beneficial.
h(P \cup \{a\}) = (P_{cnt}+1)(P_{sum}+a) = P_{cnt}P_{sum} + P_{sum} + a(P_{cnt}+1)
h(P \cup \{b\}) = (P_{cnt}+1)(P_{sum}+b) = P_{cnt}P_{sum} + P_{sum} + b(P_{cnt}+1)
But a < b \implies a(P_{cnt}+1) < b(P_{cnt}+1) \implies h(P \cup \{a\}) < h(P \cup \{b\}), so indeed we prefer b.
Greedy Strategy:
From claim 1 and 2, we can put all nonnegatives into one partition in one move. After that, we can expose claim 3 by adding negative numbers closer to 0 while we maintain nonnegative-ness of the partition. The claims above show why the greedy strategy works, I hope that was helpful to all of you.
Link to solution