Aayush Kumar Aayush Kumar - 1 year ago 115
C++ Question

How to reduce execution time in C++ for the following code?

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 × (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.

Input format

Line 1 : A single integer, N.

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

using namespace std;

int main()
int n;
int stren[200000];
for(int a=0;a<n;a++)
long long rev=0;
for(int b=0;b<n;b++)
int pos=b;
for(int c=pos;c<n;c++)
rev+=(long long)(stren[pos]-stren[c]);
rev+=(long long)(stren[c]-stren[pos]);

Can you please give me a solution??

Answer Source

Rewrite your loop as:

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

Live code here

Why does it work
Your loops make all pairs of 2 numbers and add the difference to rev. So in a sorted array, bth 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:

for(int b = 0, m = 1 - n; b < n; b++, m += 2)
   rev += m * static_cast<long long>(stren[b]);
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download