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