Yes it is the same 
Nice solution mate
Been testing code since 4h , no bugs ;-;
Your approachā¦kind of has a fault.
Whether a negative number has to be included or not, is determined by the CURRENT sum. Whether (k+1)th negative number is to be added will depend on the sum after adding kth negative number. Make your approach a bit more dynamic/spontaneous. Instead of calculating sum etc. , just keep a simple check on if (sum+arr[i])x(m+1)>sum x m
Go on adding negative numbers (from less negative [eg -1,-2] to more negative [eg- -1000], obviously). When the condition becomes false, (i.e. on adding the negative number, our score reduces), then thats the limit. After that subtract the negative numbers individually.
1 Like
Some observation that ! ^^
Wondering over the whole contest how this problem get too much submissions. Now came to know question was asking subset for maximum happiness instead of subarray as mentioned in the question. Problem setter should state it clear that it was subset or atleast given have some sample input for that case. It is not solverās part to decide whether it is subset or subarray.
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
By the way, this question can also be solved using ternary search.
1 Like
Yeah, was thinking that.
Do you have a code for this using ternary search ?
I am using the inbuilt sort function to sort the array and then traversing the array from right to left until I hit a negative number. Now I am taking one number(-ve number) at a time and checking if there is an increase in the happiness count. Wherever I get a decrease in count I break the loop and sum the remaining negative numbers.
Following is my AC code: