NEO01 - EDITORIAL (Unofficial)

editorial
, ,
21

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

22

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

23

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

24

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

25

Essentially similar kind of approach (y)

26

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

27

What is your question exactly ?

28

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
29

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:

30

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:

31

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

32

I have tested it on many cases, spent hours, don’t know why it is failing. Please do inform if you find any.

33

Sorting will make it quite convenient to solve. Just one loop from end of array upto the -ive numbers which increases the happiness.

34

The real thing, in my opinion, was that to realize Q mentioned “subset” instead of “subarrays”. I just looked at sample I/O, confused subset with subarrays and banged my head on how to solve it. Lol.

3 Likes
35

We dont have to do much with average time. You need to make sure your WORST time complexity is meeting requirement.

36

Looking to improve the editorial with a demonstration of the greedy approach of adding negative elements to the initial non-negative-elements-subset … right now it just like “use it, it works”…

37

Okay, I appreciate the suggestion :slight_smile:
So tell me the statements you want me to add to the explanation.

38

This is what i was talking about :slight_smile: … very good…

2 Likes
39

Already done by @hikarico …

40

Probably you want me to explain the logic of adding negative elements ? We can add that something like “Lesser negative elements should be added first to the selected subset only then is the possibility to increase happiness”, satisfactory ?