Minimum difference between sum of two numbers in an array

Question

I am trying to solve this problem:

A Professor of Physics gave projects to the students of his class. The students have to form a team of two for doing the project. The professor left the students to decide the teams. The number of students in a class will be even.

Each student has a knowledge level. It tells how much knowledge each student has. The knowledge level of a team is the sum of the knowledge levels of both the students.

The students decide to form groups such that the difference between the team with highest knowledge and the one with lowest knowledge is minimum.

Input

First line of the input will contain number of test cases t; In the next t lines the first number is n the number of students in the class followed by n integers denoting the knowledge levels of the n students

Output

Your output should be a single line containing the lowest possible difference between the team with highest knowledge and the one with lowest knowledge.

The solution boils down to calculate minimum difference between sum of two numbers in an unsorted array. So far I have tried:

1. Sort the array.
2. Add elements at positions i and n-i-1 and take its absolute difference with sum of elements at position i+1 and n-i.
3. Store the differences in priority queue.
4. Pop the top of priority queue to get the answer.

And, here is the code I have tried:

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

int main()
{
    ios_base::sync_with_stdio(false);

    int T=0,num=0;
    cin >> T;
    
    while(T--){
        cin >> num;
        int *a = new int[num];
        for(int i = 0; i < num; i++){
            cin >> a[i];
        }
        sort(a,a+num);
        priority_queue<int> pq;
        for(int i = 0; i < num-2; i++){
            int j = i+1;
            pq.push(abs(a[i]+a[num-1-i]-a[j]-a[num-j-1]));
        }
        cout << pq.top()<< endl;
    }
    return 0;
}

This solution exceeds the time limit and my intuition is it may fail for some cases. The description and tags hint of a dynamic programming solution but somehow I am not able to deduce the optimal substructure. Can anyone help?

Answer 1

First of all, you are right that iteratively combining the best remaining student with the worst remaining student gives you the optimum result (see proof below).

However, you don't calculate the cost of that solution correctly. You have to run through all pairs of your combination in order to find the quality value of the best and the worst pair, and only after you found them both you can subtract their values. Btw. you don't need a priority queue to find the minimum (they are thought for more complex use cases where you insert and pop several times and even update the values in the queue), simple accumulator variables (min and max) will do. Assuming the array a is already sorted, the code could look like this:

int min = 2 * MAXIMUM_KNOWLEDGE_LEVEL;
int max = 2 * MINIMUM_KNOWLEDGE_LEVEL;
for (int i = 0; i < num / 2; i++) {
    int quality = a[i]+a[num-1-i];
    if (quality < min) {
        min = quality;
    }
    if (quality > max) {
        max = quality;
    }
}
int result = max - min;

---

Now I want to proof why the pairing that you chose (iteratively pair the best remaining student with the worst remaining student) is optimal, which is essential here. If that doesn't hold, we need a whole other algorithm.

We prove it by showing that it's impossible to improve the solution given by that pairing.

If we wanted to improve it, we would have to reduce the difference between the best and the worst pair, which means either lower the best pair or raise the worst pair (or both).

Let's first show why lowering the best pair is impossible.

Let's give the pairs indices: The pair containing the highest number and the lowest number will be p_1 = (a_1, b_1), the pair with the next highest number and the next lowest number will be p_2 = (a_2, b_2) and so on, till p_n. For example:

p                   a   b     quality(p)
p_1 = (a_1, b_1) = (10, 1) -> 11 (= min)
p_2 = (a_2, b_2) = ( 9, 4) -> 13
p_3 = (a_3, b_3) = ( 8, 5) -> 13
p_4 = (a_4, b_4) = ( 8, 7) -> 15 (= max)
p_5 = (a_5, b_5) = ( 7, 7) -> 14

Now one of those pairs, let's call it p_m = (a_m, b_m) (with 1 <= m <= n) will be the maximum pair. If we want to lower the maximum, we will have to break that pair up. But who can we pair a_m with, so the new pair has a lower sum? We need to find a b, let's call it b_y that is lower than b_m (otherwise this wouldn't be an improvement). We can only find a lower b_y by going upwards the list, i.e. y < m. But the same goes for all pairs further up: If we have a pair further up (p_x with x < m) and try to find a new partner b_y for the old a_x, we have to take into account that a_x >= a_m, which makes certain choices of y impossible. If we choose a y>=m, this implies that b_y >= b_m and therefore quality(a_x, b_y) = a_x + b_y >= a_m + b_y >= a_m + b_m = quality(p_m), which we wanted to avoid. So y has to be lower than m. If we take into account that restriction, the m possible values for a ({a_1,...,a_m}) have only m-1 possible partners {b_1,...b_(m-1)}, so pairing is impossible. Therefore lowering the value of the best pair was impossible.

In the above example: In order to reduce the maximum of 15, all pairs have to have values below 15. That implies that all the left-hand-side values of the pairs above or equal to the maximum pair (8, 8, 9, 10) would need partners that are below the maximum pair's right-hand-side partner (7), so only 1, 4, and 5 are possible.

The proof for showing that raising the worst pair is impossible works the same way with reversed comparison operators and switched a and b (in that case we have too many bs for too few as).

Answer 2

You are right, the best arrangement can be obtained by sorting and pairing first elements with last ones. (†)

Step 2 and following in your approach are wrong. We don't need priority queue. We only need to find the maximum and minimum sum from created pairs.

Pseudocode:

Sort the array.
min = MAX_INT
max = 0
for (i = 0; i < n / 2; i++):
    sum = array[i] + array[n-i-1]
    if (min > sum) min = sum
    if (max < sum) max = sum
return max - min

---

(†) Why is that true?

Let's consider sorted array containing 1 2 3 6. It looks like this:

      #
      #
      #
---------- average = 12 / 4 = 3
    # #
  # # #
# # # #

Ideally, we pair them in such way, that the difference is 0. If the average is 3, then ideal, average pair will be 6.

Well, we can't do that, we can see it clearly on the image. We can move overflowing 3 above the average only in one place below the average. But there are 2 such places, of sizes 2 and 1.

Better if we fill the biggest gap possible, so first on the left. This way we got sums 7 and 5, which are a bit off the average, but minimally - by 1. Any other pairing will be the same or worse.

Answer 3

It can help if after sorting array you start adding values from two ends(first to last and so on) storing only max and min results instead of queue. Then you can obtain answer by subtracting min from max.

Example: 4 2 6 4 3 1
1. Sort: 1 2 3 4 4 6
2. Iterate:
a. currentValue = a[0] + a[5] = 7; max = min = currentValue = 7
b. currentValue = a[1] + a[4] = 6; max = 7; min = 6
c. currentValue = a[2] + a[3] = 7; max = 7; min = 6
3. Obtain result: difference = max - min = 7 - 6 = 1 

Short proof of solution: After sorting values can be imaging this way a<=b<=c...<=k<=n. Let's assume for now all values are distinct so a < b < c <...< k < n. If values distinct then (b-a>=1) so (b=>a+1) as well as (n=>k+1). For a+n and b+k difference will be at least (a+n)-(b+k)=(a+n)-(a+1+n-1)=0. For a+k and b+n difference will be at least (b+n)-(a+k)=(a+1+n)-(a+n-1)=2. This can be expand for a<=c and so on. If some values will be the same then replacement will have no effect.