How to solve this efficiently?

Question

I have two arrays:

score[n]
pos[n], where n <= 10^5; pos[i],score[i] <= 10^4

Define:

f(i,j) = abs(pos[i]-pos[j])*max(score[i],score[j])

I need to find sum of f(i,j) for all i,js.
I have an algorithm that can solve it in O(n^2) but i want to optimize.
I have spent much time but could not.

Any help is appreciated. Worst case code http://ideone.com/q4qSNh

Can you provide a snippet or snippets of your code for better context please? — ganjeii, Dec 18 '16 at 16:17
Your function f is symmetric in i and j, i.e. f(i,j) = f(j,i) so a simple optimization is to only evaluate a triangle and then double the result. Still O(n^2) but only half the effort. — Henry, Dec 18 '16 at 16:27
Provide your code then this question belongs on another site in the Stack Exchange network: http://codereview.stackexchange.com/ — AChampion, Dec 18 '16 at 16:32

score 0 · Accepted Answer · edited May 23 '17 at 12:24

0

There is a similar question asked earlier. See here.

@Gribouillis has provided a nice algorithm which has O(nlogn) complexity, consisting of sorting and using balanced binary search trees. Look here for the complete answer

Implementation has been left as an exercise.

edited May 23 '17 at 12:24

Community

1
1

answered Dec 18 '16 at 16:53

User_Targaryen

4,125
4
30
51

How to solve this efficiently?

1 Answers1