Aayush Kumar - 9 months ago 51

C++ Question

I have written this code which has an execution time of 3.664 sec but the time limit is 3 seconds.

The question is this-

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 × (N1))/2 matches. An expert has assigned a strength to each team,

a positive integer. Strangely, the Martian crowds love onesided 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.

**Input format**

Line 1 : A single integer, N.

Line 2 : N space separated integers, the strengths of the N teams.

`#include<iostream>`

using namespace std;

int main()

{

int n;

cin>>n;

int stren[200000];

for(int a=0;a<n;a++)

cin>>stren[a];

long long rev=0;

for(int b=0;b<n;b++)

{

int pos=b;

for(int c=pos;c<n;c++)

{

if(stren[pos]>stren[c])

rev+=(long long)(stren[pos]-stren[c]);

else

rev+=(long long)(stren[c]-stren[pos]);

}

}

cout<<rev;

}

Can you please give me a solution??

Answer

Rewrite your loop as:

```
sort(stren);
for(int b=0;b<n;b++)
{
rev += (2 * b - n + 1) * static_cast<long long>(stren[b]);
}
```

**Why does it work**

Your loops make all pairs of 2 numbers and add the difference to rev. So in a sorted array, b^{th} item is subtracted (n-1-b) times and added b times. Hence the number `2 * b - n + 1`

There can be 1 micro optimization that possibly is not needed:

```
sort(stren);
for(int b = 0, m = 1 - n; b < n; b++, m += 2)
{
rev += m * static_cast<long long>(stren[b]);
}
```

Source (Stackoverflow)