PROBLEM LINK:
Author: Devendra Agarwal
Tester: Surya Kiran
Editorialist: Amit Pandey
DIFFICULTY:
Easy-Medium
PREREQUISITES:
None
PROBLEM:
Special Sum of 4 numbers (a, b, c, d) is defined as:
|a+b-c-d| + |a+c-b-d| + |a+d-b-c| + |c+d-a-b| + |b+d-a-c| + |b+c-a-d|
You have to find \sum_{i=1}^{N} \sum_{j=i+1}^{N} \sum_{k=j+1}^{N} \sum_{l=k+1}^{N} Special Sum(A[i], A[j], A[k], A[l])
Solution:
Before solving this problem we will be solving a different version of this problem.
Problem Version 1:
Given an array A, find the sum of all |a-b| where a and b are from different indices of A.
Solution for Version 1:
Sort the array A in increasing order.
Now let us find the answer when A_i is used.
A_i is greater than i-1 elements and Less than N-i elements.
Hence the value contributed by A_i will be 2*( (i-1)*A_i - (N-i)*A_i )
Now we can sum this up to find our solution.
Let us call this problem version as Function1(Array A) which will give us the solution of this version.
Main Problem:
SpecialSum(a,b,c,d) = (|(a+b)-(c+d)| + |(c+d)-(a+b)|) + (|(a+c)-(b+d)| + |(b+d)-(a+c)|) + (|(a+d)-(b+c)| + |(b+c)-(a+d)|)
You will get an intuition to find all N choose 2 sum and store in the array and call the above function to solve it but it will be wrong.
So, we will first find all N choose 2 sum and store them in an array.
Let us assume our original array was A, then
For i=1 to N:
For j = i+1 to N:
New_Array.Insert(A[i] + A[j])
What will be wrong in calling Function1(New_Array) ?
Lets go by an example 1 2 3 4.
We will be calling |(1+2) - (1+3)| in some stage, which was not required by specialsum definition.
So, How to eliminate those cases ?
|(a+b)-(a+c)| = |b-c| will be coming exactly N-2 times. [ Reason: There will be N-2 different indices for selection of a ]
Hence our answer will be Function1(New_Array) - (N-2)*Function1(A)