NEO01 - EDITORIAL (Unofficial)

editorial
, , ,
1

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
2

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.

3

Yea almost everyone did, getting AC in one attempt is applaudible, at least for people like me. :slight_smile:

4

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

5

Don’t use quicksort, it has a bad worst case. Try using merge sort or the built in sort function.

6

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

7

use inline sort i.e.:
sort(arr,arr+n)

8

Quick Sort worst case goes to O(n^2) and thus exceeds time

9

Essentially similar kind of approach (y)

10

@godslayer12 i have used randomised quick sort and hence avg. time complexity is O(nlogn)

11

I don’t understand how adding negative numbers will increase the happiness value…

EDIT–
I got it!

12

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
13

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

14

What is your question exactly ?

15

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

16

The time complexity should be O(nlogn) because you have to sort all the values at least.
And the greedy algorithm needs proving (though I don’t know how to prove it).

2 Likes
17

I don’t find anything faulty in your approach, this SHOULD definitely work.
Maybe you’re missing some corner case still testing your code for counter cases. :smiley:

18

What you are saying is true, don’t know the exact reason. Still it won’t hurt to try other sorting methods once. :slight_smile:

19

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
20

Right, in case of randomised pivot probability of running into worst case is less but not nill