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:

Sample Output:

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

Please correct it: `sol +=Math.abs(a[i]-a[j])*(Math.max(b[i],b[j]));` — User_Targaryen, Dec 18 '16 at 06:51

score 3 · Accepted Answer · answered Dec 18 '16 at 12:01

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)).

I may code it later but I don't have enough time right now. I think the idea is relatively simple and it can be implemented with a fixed binary tree. Try with your java skills! — Gribouillis, Dec 18 '16 at 12:24

score 0 · Answer 2 · edited May 23 '17 at 10:30

0

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:

edited May 23 '17 at 10:30

Community

1
1

answered Dec 18 '16 at 07:04

User_Targaryen

4,125
4
30
51

Thanks for valuable response. – Shree Prakash Dec 18 '16 at 08:09
2

I think it's a quite different problem, because here the *attraction force* (which would be better described as a *potential* imho as it is a scalar quantity) is proportional to the distance between the particles. Nothing to do with gravity. Particles that are far away contribute much more to the desired sum. – Gribouillis Dec 18 '16 at 09:43
@Gribouillis yeah correct, that's why I am also thinking how it is relate to Gravity and N body Simulation ? – Shree Prakash Dec 18 '16 at 09:50

Attraction Force as coding

2 Answers2

Linked