ronith
12/5/2018 - 7:57 PM

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

Tournament.cpp
content_copyfile_download
#include <bits/stdc++.h>
using namespace std;

void merge (int a[], int l, int m, int r) {
    int n1= m-l+1, n2= r-m;
    int b[n1], c[n2];
    for (int i=0;i<n1;i++)
        b[i]= a[l+i];
    for (int i=0;i<n2;i++)
        c[i]= a[m+1+i];
    int i=0, j=0, k=l;
    while (i<n1 && j<n2) {
        if (c[j]<b[i])
            a[k++]= c[j++];
        else
            a[k++]= b[i++];
    }
    while (i<n1) {
        a[k++]= b[i++];
    }
    while (j<n2) {
        a[k++]= c[j++];
    }
}

void mergesort (int a[], int l, int r) {
    if (l<r) {
        int m= (l+r)/2;
        mergesort(a, l,m);
        mergesort(a, m+1, r);
        merge (a, l,m,r);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    int a[n];
    for (int i=0;i<n;i++)
        cin>> a[i];

    mergesort (a, 0, n-1);
    int p= n-1, q= 0;
    long long ans= 0;

    for (int i=n-1;i>=0;i--) {
        ans= ans + i*a[i] - (n-1-i)*a[i];
        p--;
        q++;
    }
    cout<<ans;
}