9671669 | CodeChef


I am not able to score 100, only 4 out 6 test cases are passed. Please check my code and find the mistake I am doing.
.
.
https://www.codechef.com/viewsolution/33122242

access denied to this page

Ok then code is here

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

int main(){
long long n;
cin>>n;
long long a[n],i,j,s = 0;
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
for(i=0;i<n-1;i++){
for(j=i+1;j<n;j++){
s += (a[j]-a[i]);
}
}
cout<<s;
return 0;
}

Is it TLE or WA? Your code seems to be strictly O(n^2).

This is the O(n log n) solution:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	long long int n;
	cin>>n;
	long long int arr[n];
	for(int i=0;i<n;i++)
	    cin>>arr[i];
	sort(arr,arr+n);
	long long int sum=0;
    for (int i=0; i<n; i++)
        sum += i*arr[i] - (n-1-i)*arr[i];
	cout<<sum<<"\n";
	return 0;
}

But I don’t know why it works? (I actually forgot :thinking:, this is my own solution)

1 Like

Your code is O(n^2) which will TLE.
Let us consider the properties of |a-b|.
|a-b| is equivalent to the following pseudocode.

if(a>b):
    return a-b
else:
    return b-a

We want the sum of all pairs.
Let the array be A and A_i denotes the ith element of the array after sorting
(0 indexed).

We know A_i\ge A_j if i\gt j.
So |A_i - A_j| = A_i - A_j if i\gt j and it is A_j - A_i if i<j.
Let us consider how many times A_i was added and subtracted.
For all j such that j \gt i, A_i was subtracted, which is n-i-1 times, and for all j such that j<i, A_i is added, which is i times.
So the answer is
\sum iA_i - (n-i-1)A_i.

2 Likes

TLE

It is the explanation of my implementation… You can’t get TLE

Can you explain me the (sum+=…) part in loop ?

That’s what @everule1 explained…

Yes, I got it from there

1 Like

Thanx