Attraction Force as coding

Question

There are N particles present on the X axis, where, each particle has two properties associated with it, i.e. the Position of the particle and its Attraction-Value

The Attraction-Force between two particles i and j is defined as :

Attraction-Force(i,j) = Distance(i,j) × MAX(Attraction_Value[i],Attraction_Value[j])

Since all of them are in a straight line, distance between any 2 particles is equal to the absolute difference between their positions.

You are supposed to calculate the following :

∑N−1i=1∑Nj=i+1(Attraction−Force(i,j)) means

Summation(i,N-1)Summation(j=i+1,N) of (Attraction Of Force(i,j))

Constraints:

1≤N≤2×10^5

1≤Attraction−Value≤10^4

1≤Position≤10^4

Sample Input:

3
1 2
2 4
3 6

Sample Output:

22

I tried in O(n^2) as following

import java.util.*;

class TestClass {

public static void main(String args[] ) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int a[]=new int[n];
    int b[]=new int[n];
    for(int i=0;i<n;i++)
    {
        a[i]=sc.nextInt();
        b[i]=sc.nextInt();
    }
    long sol=0;
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
          sol +=Math.abs(a[i]-a[j])*(Math.max(b[i],b[j]));   
        }
    }
    System.out.println(sol);
    }

}

Please let me know if there are any other optimized way to solve this problem.

Any idea will be appreciated

Thanks in Advance

Answer 1

There are O(nlogn) approximation algorithms like the Barnes-Hut simulation and Particle mesh method. But you will have to compromise on accuracy of the output. I assume that accuracy of the answer is very important in your case.

For more information:

1. Similar question
2. Wiki

Answer 2

I think there is a O(n log(n)) algorithm. First here are my notations: we want to compute

S = Sum[i] Sum[j>i] abs(x[i] - x[j]) max(m[i], m[j])

In this sum, every (unordered) pair {i, j} appears exactly once and upon sorting the particles we can suppose that the positions x[i] are in ascending order. By sorting the masses m[i], we can get an array r[1], ..., r[n] such that the m[r[i]] are in ascending order.

My idea is to build a balanced binary search tree containing the particles, based on their positions, such that at the root of every subtree T, one stores the number of the subtree's particles and the sum of the subtree's particles positions.

With this data, for any real number x, the Sum[i] abs(x - x[i]) can be determined in time O(log(n)).

Now taking the heaviest particle with rank r[n], its contribution to the sum S is m[r[n]] Sum[i] abs(x[r[n]] - x[i]). This contribution can be computed in time 0(log(n)). We can then remove the heaviest particle from the binary tree, either by using standard algorithms on balanced trees, or more simply by modifying the data contained on the nodes.

By removing inductively the heaviest particles one after the other, we obtain the sum S in time O(n log(n)).