CODEWITHSUNDEEP
c++arrayssorting
Aayush Kumar
Aayush Kumar

Reputation: 23

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.

#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??

Upvotes: 2

Views: 883

Answers (5)

amol13
amol13

Reputation: 362

What exactly we are doing in this problem is: For all combinations of pairs of elements, we are adding up the absolute values of the differences between the elements of the pair. i.e. Consider the sample input

3 10 3 5

Ans (Take only absolute values) = (3-10) + (3-3) + (3-5) + (10-3) + (10-5) + (3-5) = 7 + 0 + 2 + 7 + 5 + 2 = 23

Notice that I have fixed 3, iterated through the remaining elements, found the differences and added them to Ans, then fixed 10, iterated through the remaining elements and so on till the last element

Unfortunately, N(N-1)/2 iterations are required for the above procedure, which wouldn't be ok for the time limit.

Could we better it?

Let's sort the array and repeat this procedure. After sorting, the sample input is now 3 3 5 10

Let's start by fixing the greatest element, 10 and iterating through the array like how we did before (of course, the time complexity is the same)

Ans = (10-3) + (10-3) + (10-5) + (5-3) + (5-3) + (3-3) = 7 + 7 + 5 + 2 + 2 = 23

We could rearrange the above as

Ans = (10)(3)-(3+3+5) + 5(2) - (3+3) + 3(1) - (3)

Notice a pattern? Let's generalize it.

Suppose we have an array of strengths arr[N] of size N indexed from 0

Ans = (arr[N-1])(N-1) - (arr[0] + arr[1] + ... + arr[N-2]) + (arr[N-2])(N-2) - (arr[0] + arr[1] + arr[N-3]) + (arr[N-3])(N-3) - (arr[0] + arr[1] + arr[N-4]) + ... and so on

Right. So let's put this new idea to work. We'll introduce a 'sum' variable. Some basic DP to the rescue.

For i=0 to N-1

sum = sum + arr[i]

Ans = Ans + (arr[i+1]*(i+1)-sum)

That's it, you just have to sort the array and iterate only once through it. Excluding the sorting part, it's down to N iterations from N(N-1)/2, I suppose that's called O(N) time EDIT: That is O(N log N) time overall

Hope it helped!

Upvotes: 1

Mohit Jain
Mohit Jain

Reputation: 30489

Rewrite your loop as:

sort(stren);
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:

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

Upvotes: 4

Barry
Barry

Reputation: 302767

An interesting approach might be to collapse down the strengths from an array - if that distribution is pretty small.

So:

std::unordered_map<int, int> strengths;
for (int i = 0; i < n; ++i) {
    int next;
    cin >> next;
    ++strengths[next];
}

This way, we can reduce the number of things we have to sum:

long long rev = 0;
for (auto a = strengths.begin(); a != strengths.end(); ++a) {
    for (auto b = std::next(a), b != strengths.end(); ++b) {
        rev += abs(a->first - b->first) * (a->second * b->second);
        //     ^^^^ stren diff ^^^^^^^^   ^^ number of occurences ^^
    }
}
cout << rev;

If the strengths tend to be repeated a lot, this could save a lot of cycles.

Upvotes: 1

Bathsheba
Bathsheba

Reputation: 234665

In place of the if statement, use

rev += std::abs(stren[pos]-stren[c]);

abs returns the positive difference between two integers. This will be much quicker than an if test and ensuing branching. The (long long) cast is also unnecessary although the compiler will probably optimise that out.

There are other optimisations you could make, but this one should do it. If your abs function is poorly implemented on your system, you could always make use of this fast version for computing the absolute value of i:

(i + (i >> 31)) ^ (i >> 31) for a 32 bit int.

This has no branching at all and would beat even an inline ternary! (But you should use int32_t as your data type; if you have 64 bit int then you'll need to adjust my formula.) But we are in the realms of micro-optimisation here.

Upvotes: 4

Resource
Resource

Reputation: 544

for(int b = 0; b < n; b++)
{
    for(int c = b; c < n; c++)
    {
        rev += abs(stren[b]-stren[c]);
    }
}

This should give you a speed increase, might be enough.

Upvotes: 2

Related Questions