COMB4SUM - Editorial

PROBLEM LINK:

Practice
Contest

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)

AUTHOR’S, TESTER’S SOLUTIONS:

setter’s solution
tester’s solution

2 Likes

“Cakewalk”

7 Likes

Eh…Cakewalk?

1 Like

ooh…so it was cakewalk eh?

seriously Cakewalk???
I got that idea of storing sum of two elements in array, but couldn’t go ahead, because couldn’t apply idea of function1…

I still can’t understand, how that expression in function1 for Ai came?

EDIT:
got it…now, when it will be less, it’ll be subtracted, when it will be greater, it will be added…!!!
Uhhhh… srsly it is cakewalk…

Is there any trick to questions like this? how to think like this?

1 Like

Cakewalk seems too harsh a judgement for this problem, but easy-medium fits, I guess. I was able to solve this in less than a hour and unable to solve the third one, which has greater number of submissions, in over an hour.

I noticed the function reduces to 2 times (summation of (max pair - min pair) ) for the 3 pairs formed by a,b,c,d as ((a,b),(c,d)),((a,c),(b,d)) and ((a,d),(b,c)) over all possible pair. I constructed and sorted the pair array and noticed the extra single elements I was getting when the two pairs had a common index, so, the solution became summation of (k-2i+1).pair[i] over all i minus extra occurrences of single elements. A bit of math showed that the coefficient of b[i] (b=sorted version of a) in the extra occurrences is (2ni-n^2+3n-4i-2). This solved the problem.

Code is here : https://www.codechef.com/viewsolution/7507781

The attached solutions are of SUMPAIR problem.

My editorial: https://aleigorithms.wordpress.com/2015/07/19/adding-special-sum/

2 Likes

there seems to be a mix-up here…except for problem and solution itself everything in this editorial is of SUMPAIR…practice link, contest link and even setter’s and tester’s solution are of SUMPAIR

PS: nice prob and solution

Link to :

Setter’s Solution

Tester’s Solution

Nice question and nice editorial.

Anyone can please make me understand the meaning of this statement:-

Hence the value contributed by Ai will be 2∗((i−1)∗Ai−(N−i)∗Ai)

Thanks!