NEO01 - EDITORIAL (Unofficial)

PROBLEM LINK

Practice
Contest

CONTEST PANEL

Author: neo1tech9_7

PREREQUISITES

Basic Math

DIFFICULTY

EASY

PROBLEM

An array with N elements (both positive and negative) is given, a term happiness is defined as the sum of all elements of a selected subset from given array multiplied by the number of elements in it. A element from the array can be taken in a subset only once and all elements must appear in some subset, find the maximum value of happiness possible.

EXPLANATION

Complexity: O(nlogn)

Subtask 1:

This subtask consists of all negative array elements, so to maximise the happiness we select a subset of 1 element for all array elements i.e simply the summation of all array elements.

Subtask 2:

As anyone would guess, to maximise happiness we need to select a subset whose sum(number of terms)* is the greatest.

To start off with my solution what I do is pre-calculate the sum of subset of all positive numbers and subset of all negative numbers and take note of count of positive numbers and zeroes and store absolute values of negative numbers in an array or vector and sort it in ascending fashion.

So for our initially selected subset (set of all non-negative values) we are at happiness=(positive sum)*(count of positive numbers and zeroes).

for example:
A = {10,5,-1,-2,-3}
starting subset = {10,5}
starting happiness = (10+5)*(2) = 30
negative vector = {1,2,3} (Recall that we took absolute values)

Note: We are adding absolute values of all negative numbers and will be testing whether the number will be appearing in the subset from smallest absolute value to greatest.

Find the proof for this greedy algorithm in the answer by @hikarico.

Note that this selected initial subset is dynamic and we will check whether the addition of negative numbers (from smallest absolute value to the greatest) will result in happiness greater than what we have at present and if addition of negative numbers in the selected subset results in a greater happiness we insert that negative value in the subset, refer the pseudocode below for clarification.

accumulator = subset length
sum = subset sum
ans = accumulator*sum
for(i from 0 to length of negative array){
   if((sum-negative[i])*(accumulator+1) greater than ans){
       ans = (sum-negative[i])*(accumulator+1);
       sum-=negative[i];
       accumulator++;
   }
}

After you’ve done this you are at a situation where no addition of negative numbers in the subset will result in greater happiness so what we do is make subsets of one element for all the remaining negative elements not in any subset and thus subtract all the remaining negative numbers from happiness.

Thus this is how we arrive at max happiness possible.

Do feel free to share your approach and feel free to comment if you have any doubt :smiley:

SOLUTION

My AC
Execution Time: 0.1 s
Memory: 3.3M

6 Likes

The difficult part in this question was to realize that

sum (negative numbers) + sum(positive numbers)*(number of positive numbers)

will not work. The test cases we’re quite deceiving and I’m quite sure I’m not the only one that fell for it.

https://www.codechef.com/viewsolution/14238057link text

i have used same logic still im getting TLE error for subtask 2 plz help me why im getting such error

try reading dis code https://www.codechef.com/viewsolution/14095249 @code_man

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 to code

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

I did it in a similar way…here is my AC code: https://www.codechef.com/viewsolution/14214892

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.

Link to solution

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 https://www.codechef.com/viewsolution/14097565 .
Can you tell me is it the same approach you are suggesting or different?

@shubham_827

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.

Can anyone have a look and explain me why my solution gave WA
MY Solution

python3.4:

https://www.codechef.com/viewsolution/14123773

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:

link text