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.
Yes it is the same 
Nice solution mate
Been testing code since 4h , no bugs ;-;
Some observation that ! ^^
Haha, i mis-read too 
Though I think they did use the word “SUBSET” there.
1 Like
You are only considering positive numbers in your starting subset but as I mentioned in the editorial we need to take NON-NEGATIVE numbers as our starting happiness that means you need to take 0 into consideration while building the starting subset.
Yeah… It was subset mentioned in the question
We store absolute values of negative numbers in an array and sort them, then check from lowest to highest absolute negative values whether the number can be added to out subset
https://www.codechef.com/viewsolution/14248782
here i added non-negetive number to the positive set then too WA
Subarray instead of subset amde the Q hell for me.Found out on 2nd day that i misread…wanted to bang my head on wall…and also the setters for using that type of sample I/O…
Good Going
Yeah, was thinking that.
Do you have a code for this using ternary search ?
Nice explanation! It is true that adding a larger number to a nonnegative partition is better than adding a smaller number, but the numbers outside the partition P should not be ignored since they contribute to the answer. Let the sum of numbers outside P be Q, then
h(P\cup\{a\})+(Q-a)=(P_{cnt}+1)(P_{sum}+a)+(Q-a)=P_{cnt}P_{sum}+P_{sum}+aP_{cnt}+Q
h(P\cup\{b\})+(Q-b)=(P_{cnt}+1)(P_{sum}+b)+(Q-b)=P_{cnt}P_{sum}+P_{sum}+bP_{cnt}+Q
If $a < b \implies h(P \cup {a}) + (Q-a) < h(P \cup {b}) + (Q-b) \implies$adding b is preferable to a. So it leads to the same conclusion
1 Like
@meooow, you’re very correct with that. I did claim 2 first to make sure negatives are in single-element partitions before doing claim 3, but your one-step explanation is great since it’s shorter proof for all three claims! 