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: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
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)


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)


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


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)


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)


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)


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)


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)


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