Sum of differences#12231

Sum of differences (Editorial)

Written By : MathModel

Claim #1 : Under all arrangements of $a$ the expression :

i = 1 \sum n j = i + 1 \sum ∣ a_{i} - a_{j} ∣

\sum_{i=1}^n \sum_{j=i+1} |a_i-a_j|

will be fixed.

Proof :

Rejecting the absolute value notation , there're two cases for each pair of integers , suppose $a_{i} < a_{j}$ a_i<a_j then if in an arrangement $a_{j}$ a_j appeared before $a_{i}$ a_i then we've $a_{j} - a_{i}$ a_j-a_i which is negative , otherwise $a_{i}$ a_i appeared before $a_{j}$ a_j then we've $a_{i} - a_{j}$ a_i-a_j and then $a_{i} - a_{j} = - (a_{j} - a_{i})$ a_i-a_j=-(a_j-a_i) then

∣ a_{i} - a_{j} ∣ = ∣ a_{j} - a_{i} ∣

|a_i-a_j|=|a_j-a_i|

thus our proof is complete.

Without Loss of Generality , we can sort the array $a$ in non-decreasing order so we've

a_{1} \leq a_{2} \leq a_{3} \leq ... \leq a_{n}

a_1 \le a_2 \le a_3 \le ... \le a_n

Now we can notice a pattern :

$(a_{2} - a_{1})$ (a_2-a_1)
$(a_{3} - a_{1}) + (a_{3} - a_{2})$ (a_3-a_1)+(a_3-a_2)
$(a_{4} - a_{1}) + (a_{4} - a_{2}) + (a_{4} - a_{3})$ (a_4-a_1)+(a_4-a_2)+(a_4-a_3)
$...$
$..$
$(a_{n} - a_{1}) + (a_{n} - a_{2}) + ... + (a_{n} - a_{n - 1})$ (a_n-a_1)+(a_n-a_2)+...+(a_n-a_{n-1})

Notice that index $i$ contributes positively with $i - 1$ i-1 copies of $a_{i}$ a_i and removes the prefix sum of $a$ from $1$ to $i - 1$ i-1.

Let $p [i]$ be the prefix sum of $a$ upto index $i$ which can be pre-calculated in $O (n)$ then our expression is :

i = 2 \sum n a_{i} \times (i - 1) + p [i - 1]

\sum_{i=2}^n a_i \times (i-1) + p[i-1]

n=int(input())
a=list(map(int,input().split()))
a.sort()
p=[]
cur=0
for i in range(n):
    cur+=a[i]
    p.append(cur)

ans=0
for i in range(1,n):
    ans+=a[i]*(i)-p[i-1]
print(ans)

Python

Complexity $O (n lo g n)$ \mathcal{O}(n \log n).