PROBLEM SETTER -
ZCO 2013
DIFFICULTY –
Easy
PREREQUISITES –
Sorting
FIRST SUBTASK SOLUTION –
A simple brute for iterating on all the C(N,2) combinations can do the task easily for N<5000, by taking the sum of difference of all pairs of elements.
int ans=0; for(int i = 1;i < n+1;i++) for(int j = i+1;j < n+1;j++) answer += abs(a[j]-a[i]); cout << answer;
TIME COMPLEXITY -
O(N^2)
KEY OBSERVATIONS –
- Sorting the array will not cause any change to the answer as the answer does not depend on the indices of the elements.
- Let us define a function diff(i), which denotes the sum of difference between a[i] and a[j] for all (i,j) where a[j] < a[i]. After sorting in ascending order, the above condition of a[j] < a[i] changes to j < i.
Mathematically, after sorting, diff(i) = $ \sum_{j=1}^{i-1} \hspace{2mm} ( a[i] - a[j] ). \hspace{2mm} $Now,
The above mathematical formula clearly defines dependency of diff(i) upon diff(i-1). Consequently, the transition from i to i+1 is in O(1) time. The answer we need is summation of diff(i) for all i. Don’t forget that this observation is valid only after the array is sorted.
SECOND SUBTASK SOLUTION –
We first sort the array in ascending order in accordance with observation 1. We have to iterate on the sorted array and maintain 2 variables – answer and diff_i.
sort(a+1,a+n+1);
ll answer=0,diff_i=0;
a[0] = 0;
for(ll i=1;i < n+1;i++)
{
diff_i += (i-1)*(a[i]-a[i-1]);
answer += diff_i;
}
cout << answer;
As we iterate, diff(i) can be updated in O(1) time using the formula in observation 2. answer can be maintained by adding the value of diff(i) to it after updating diff(i).
Time Complexity –
O(N * log(N))