You are not logged in. Please login at www.codechef.com to post your questions!

×

Faster alternative of this

for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { rev=rev+abs(s[i]-s[j]); } }

asked 27 Sep '17, 23:02

rishabh_2708's gravatar image

1★rishabh_2708
1
accept rate: 0%


you can proceed as follows :
( considering number of elements = n and array indexes starting at 0)
1. sort the array in descending order , so that abs(s[i] - s[j]) = (s[i] - s[j]) for j > i ( This takes O(nlogn) time )
2. find the sum of following series :
$(n-1)*(s[0]-s[n-1]) + (n-3)*(s[1] - s[n-2]) + (n-5)*(s[2] - s[n-3]) + ...$

This will get you to O(nlogn) from O(n^2)

Note that the last term will become zero if the number of items is odd , this is not a problem

Explanation :
If you sort the array and write down the sum terms and get rid of the brackets , you will see that :
1. largest number occurs (n-1) times as positive and 0 times as negative. smallest number occurs (n-1) times as negative and never as positive
2. second largest number occurs (n-2) times as positive and 1 time as negative , and so on and so forth.
Adding it all up , it forms the series I wrote above.
I hope I was of help :)

link

answered 29 Sep '17, 02:00

my_name_is_nrg's gravatar image

4★my_name_is_nrg
826
accept rate: 0%

edited 30 Sep '17, 00:07

I don't think it requires $s[i] \ge 0$.
Same for @we7d also.

(29 Sep '17, 02:07) meooow ♦6★

I agree with @meooow because we are using abs

(29 Sep '17, 02:09) swetankmodi ♦♦6★

now that I think about it , yeah it does not require s[i] >=0 .. I guess I was just being too cautious :p

(30 Sep '17, 00:06) my_name_is_nrg4★

if s[i]>=0, you can sort then use prefix sum for(int i=n-1;i>0;i--)ans+= i *v[i] +pref[i-1]-pref[0]

link

answered 28 Sep '17, 09:22

we7d's gravatar image

2★we7d
222
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×4

question asked: 27 Sep '17, 23:02

question was seen: 270 times

last updated: 30 Sep '17, 00:07