I have tested it on many cases, spent hours, don’t know why it is failing. Please do inform if you find any.
Sorting will make it quite convenient to solve. Just one loop from end of array upto the -ive numbers which increases the happiness.
The real thing, in my opinion, was that to realize Q mentioned “subset” instead of “subarrays”. I just looked at sample I/O, confused subset with subarrays and banged my head on how to solve it. Lol.
3 Likes
We dont have to do much with average time. You need to make sure your WORST time complexity is meeting requirement.
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.
9 Likes
Don’t understand what to do with negative no.s?
https://www.codechef.com/viewsolution/14212667
Pls check someone why my code gives wrong answer on submit while while gives right answer on custom input… Why?
Looking to improve the editorial with a demonstration of the greedy approach of adding negative elements to the initial non-negative-elements-subset … right now it just like “use it, it works”…
Okay, I appreciate the suggestion 
So tell me the statements you want me to add to the explanation.
This is what i was talking about … very good…
2 Likes
Probably you want me to explain the logic of adding negative elements ? We can add that something like “Lesser negative elements should be added first to the selected subset only then is the possibility to increase happiness”, satisfactory ?
At this point, something like that will be enough… note that should be “greater negative elements should be tested first” otherwise make clear you are talking about absolute values of negative elements. Another improve, complexity is not O(n) because sorting is at least n*logn in this case. Greetings and thanks in advance…
Thanks I’ll incorporate this in the editorial, Appreciate the help !
sum (negative numbers) + sum(positive numbers)*(number of positive numbers)
why this thing will not work?Please give one counter example of this.
Being a school student, most of that went over my head.I solved the problem using this solution https://www.codechef.com/viewsolution/14097565 .
Can you tell me is it the same approach you are suggesting or different?
Done the changes, thanks !
Zeros must be included into positive set… also you must check if adding some negative value to it can improve solution. For example, the case with numbers 9 and -8 has result 2 instead of 1.
Yes you need to include zeroes into positive set to maximise happiness.