CodeChef: Practical coding for everyonelink text
i have used same logic still im getting TLE error for subtask 2 plz help me why im getting such error
I don’t understand how adding negative numbers will increase the happiness value…
EDIT–
I got it!
Hi, i´m concerned/interested on demonstration of why this greedy approach (“store absolute values of negative numbers in an array or vector and sort it in ascending…”) actually work… until now i could not find any counter-example that make it fail, or even to make fail a solution ordering that vector descending instead of ascending.
So, why trying to add negative values from lesser to greater values don´t work? And, could not occurs something similar like in previous approach, when ordering negative values ascending by their absolute values making fail also this approach used in competition?
2 Likes
After sorting the array I am calculating the suffix sum of negative numbers, and checking from right to left (of negative numbers) each time taking an interval of numbers and subtracting from subset containing +ve numbers.
It is failing at subtask2. Can anyone provide some counter case where it is not working?
I have tested it on many examples with AC solutions but it gives correct answer each time.
link text
https://www.codechef.com/viewsolution/14238057
why i got TLE even after using randomized quicksort, ihave read randomized quicksort always follows average time complexity which is O(nlogn) also in my algorithm there is no fix pivot still i got TLE
Even Randomized Quicksort has a worst case complexity O(n^2). It doesn’t happen as often as it does in Quicksort, but it’s still possible.
1 Like
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?
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 CodeChef: Practical coding for everyone .
Can you tell me is it the same approach you are suggesting or different?
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
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.
By the way, this question can also be solved using ternary search.
1 Like
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:
Yea almost everyone did, getting AC in one attempt is applaudible, at least for people like me. 
Don’t use quicksort, it has a bad worst case. Try using merge sort or the built in sort function.