ZCO13001 - Editorial

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

  1. Sorting the array will not cause any change to the answer as the answer does not depend on the indices of the elements.
  2. 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,

\sum_{j=1}^{i-1} \hspace{2mm} ( a[i] - a[j] ) \hspace{2mm} = \hspace{2mm} (a[i]-a[i-1]) * (i-1) \hspace{2mm} + \hspace{2mm} \sum_{j=1}^{i-2} \hspace{2mm} ( a[i-1] -a[j ] )
\hspace{2mm} diff(i) \hspace{2mm} = \hspace{2mm} (a[i]-a[i-1]) * (i-1) \hspace{2mm} + \hspace{2mm} diff(i-1) \hspace{2mm}

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))