Zonal Computing Olympiad 2013, 10 Nov 2012
N teams participate in a league cricket tournament on Mars, where each pair of distinct teams plays each other exactly once. Thus, there are a total of (N × (N-1))/2 matches. An expert has assigned a strength to each team, a positive integer. Strangely, the Martian crowds love one-sided matches and the advertising revenue earned from a match is the absolute value of the difference between the strengths of the two matches. Given the strengths of the N teams, find the total advertising revenue earned from all the matches.

For example, suppose N is 4 and the team strengths for teams 1, 2, 3, and 4 are 3, 10, 3, and 5 respectively. Then the advertising revenues from the 6 matches are as follows:

Match Team A Team B Ad revenue 1 1 2 7  2 1 3 0  3 1 4 2  4 2 3 7  5 2 4 5  6 3 4 2 

Thus the total advertising revenue is 23.

-----Input format-----
Line 1 : A single integer, N.
Line 2 : N space-separated integers, the strengths of the N teams.

-----Output format-----
A single integer, the total advertising revenue from the tournament.

-----Sample input-----
4
3 10 3 5

-----Sample output-----
23

-----Test data-----
In all subtasks, the strength of each team is an integer between 1 and 1,000 inclusive.
- Subtask 1 (30 marks) : 2 ≤ N ≤ 1,000.
- Subtask 2 (70 marks) : 2 ≤ N ≤ 200,000.

-----Live evaluation data-----
- Subtask 1: Testcases 0,1,2.
- Subtask 2: Testcases 3,4,5.

-----Note-----
The answer might not fit in a variable of type int. We recommend that type long long be used for computing all advertising revenues. If you use printf and scanf, you can use %lld for long long.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
# cook your dish here
from itertools import combinations
n = int(input())
t = list(combinations(list(map(int, input().split())), 2))
ar = 0
for i in t:
    ar += abs(i[0] - i[1])
print(ar)

# cook your dish here
n=int(input())
strength=list(map(int,input().split()))
revenue=0
for i in range(0,n-1):
    for j in range(i+1,n):
        x=abs(strength[i]-strength[j])
        revenue+=x
print(revenue)

t=input()
arr=input().split()
arr=[int(i) for i in arr]
c=0
if len(arr)==t:
 for i in range(0,t):
	 for j in range(i,t):
		 c+=abs(arr[i]-arr[j])
 print(c)

# cook your dish here
n=int(input())
l=list(map(int,input().split()))
c=0
for i in range(0,n):
    for j in range(0,i):
        a=abs(l[i]-l[j])
        c+=a
print(c)

n=int(input())
a=list(map(int,input().strip().split()))
a.sort()
s=0
for i in range(len(a)):
    s+=a[i]*(i-(len(a)-1-i))
    
print(s)

n=int(input())
a=list(map(int,input().strip().split()))
s=0
for i in range(len(a)):
    for j in range(i+1,len(a)):
        s+=abs(a[j]-a[i])
print(s)

n=int(input())
z=[]
s=list(map(int,input().split()))[:n]

for i in range(0,n):
    for j in range(i+1,n):
        p=abs(s[i]-s[j])
        z.append(p)
print(sum(z))

def abs(x): 
    if x < 0:
        return -x
    else: 
        return x

# cook your dish here
precalculated = {}
N = int(input())
tmp = input() 
while(tmp[-1] == " "): 
    tmp = tmp[:-1]
values = list(map(int, tmp.split(" ")))
total = 0
saved_sum = sum(values) 
saved_length = len(values) - 1
for val in values:
    if val in precalculated:
         precalculated[val][1] += 1
    else: 
        precalculated[val] = [0, 1]
for pre in precalculated:
    for pre1 in precalculated: 
        precalculated[pre][0] += precalculated[pre1][1] * abs(pre1 - pre)
for pre in precalculated: 
    total += precalculated[pre][0] * precalculated[pre][1]

print(total // 2)

def abs(x): 
    if x < 0:
        return -x
    else: 
        return x

# cook your dish here
precalculated = {}
N = int(input())
tmp = input() 
while(tmp[-1] == " "): 
    tmp = tmp[:-1]
values = list(map(int, tmp.split(" ")))
total = 0
saved_sum = sum(values) 
saved_length = len(values) - 1
for val in values:
    if val in precalculated:
         precalculated[val][1] += 1
    else: 
        precalculated[val] = [0, 1]
        for val1 in values: 
            precalculated[val][0] += abs(val - val1)
for pre in precalculated: 
    total += precalculated[pre][0] * precalculated[pre][1]
print(total // 2)

teams=int(input())
strength=list(map(int, input().split()))
strength.sort()
rev=0
for i in range(0,teams):
    rev+=strength[i]*(i-(teams-1-i))

print(rev)

teams=int(input())
strength=list(map(int, input().split()))
strength.sort()
rev=0
for i in range(0,teams):
    for j in range(i+1,teams):
            rev+=strength[j]-strength[i]
            
print(rev)

n=int(input())
strength=list(map(int,input().split()))
res=0
strength.sort()
for i in range(n):
    res=res+(strength[i]*(i-((n-1)-i)))
print(res)


n=int(input())
strength=list(map(int,input().split()))
sum=0
i=0
while(i<n-1):
    j=i+1
    while(j<n):
        sum=sum+abs(strength[i]-strength[j])
        j+=1
    i+=1
print(sum)


# cook your dish here
n=int(input())
strength=list(map(int,input().split()))
revenue=0
for i in range(0,n-1):
    for j in range(i+1,n):
        x=strength[i]-strength[j]
        if x<0:
            x=0-x
        revenue+=x
print(revenue)

t = int(input())
s = list(map(int, input().split()))
revenue = 0
s.sort()
s.reverse()

for i in range(t) :
    revenue -= i * s[i]
    revenue += (t - i - 1) * s[i]
    
print(revenue)

t = int(input())
s = list(map(int, input().split()))
revenue = 0

for i in range(t-1) : 
    for j in range(i+1, t) :
        add = s[i] - s[j]
        if add > 0 :
            revenue += add
        else :
            revenue -= add

print(revenue)

t = int(input())
s = list(map(int, input().split()))
i = 0
j = t
revenue = 0

for i in range(t-1) : 
    for j in range(i+1, t) :
        revenue += ((s[i]>s[j])*((2*s[i])-(2*s[j])) + s[j]-s[i])

print(revenue)

teams=int(input())
strength=list(map(int, input().split()))
rev=0
for i in range(0,teams):
    for j in range(i+1,teams):
        if(strength[i]>strength[j]):
            rev+=strength[i]-strength[j]
            
        else:
            rev+=strength[j]-strength[i]
            
print(rev)


teams=int(input())
strength=list(map(int, input().split()))
rev=0
for i in range(0,teams):
    for j in range(i,teams):
        if(i==j):
            continue
        elif(strength[i]>strength[j]):
            rev+=strength[i]-strength[j]
            
        else:
            rev+=strength[j]-strength[i]
            
print(rev)


# cook your dish here
N = int(input())
l = list(map(int, input().strip().split(" ")))
s=0
for i in range(N):
    for j in range(i+1, N):
        s+= abs(l[j]-l[i])
print(s)


"""
l.sort()

s = 0
for i in range(len(l)):
    s -= (len(l) - i - 1) * l[i]
    s += i * l[i]
print(s)
"""

# cook your dish here
N = int(input())
l = list(map(int, input().strip().split(" ")))

l.sort()

s = 0
for i in range(len(l)):
    s -= (len(l) - i - 1) * l[i]
    s += i * l[i]
print(s)

# cook your dish here
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def lcm(x, y):
    return (x*y)//(gcd(x,y))


abc="abcdefghijklmnopqrstuvwxyz"

pi=3.141592653589793238

n = int(input())
arr = list(map(int,input().split()))
revenue = 0
for i in range(n-1):
    for j in range(i+1,n):
        cur = abs(arr[i] - arr[j])
        revenue += cur
print(revenue)

n = int(input())
strengths = list(map(int, input().split()))
strengths.sort(reverse = True)
summ = 0
for i in range(0, len(strengths)):
    summ += strengths[i]*(len(strengths)-2*(i+1)+1)
print(summ)

n = int(input())
l = list(map(int,input().split()))
l.sort()
c,sum = 0,0
for i in l:
    if c < len(l):
        c+=1 
        for x in l[c:]:
            sum = sum + abs(i-x)

print(sum)