The minimum difference between the sum of two numbers in an array

Question

I am trying to solve this problem problem :

A physics professor gave projects to students of his class. Students must form a two-person team to complete the project. The professor left the students to decide the team. The number of students in the class will be even.

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

Students decide to form groups so that the difference between the team with the highest knowledge and the least knowledge is minimal.

Enter

The first line of input will contain the number of test cases t; In the following t-lines, the first number is equal to n the number of students in the class, followed by n integers indicating the knowledge levels of n students

Output

Your result should be one line containing the smallest possible difference between the team with the highest knowledge and those with the lowest knowledge.

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

• Sort an array.
• Add elements at positions i and ni-1 and take its absolute difference with the sum of elements at positions i + 1 and ni.
• Keep the differences in the priority queue.
• Put the highest priority line to get an answer.

And here is the code I 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 decision exceeds the time limit, and my intuition may be unsuccessful for some cases. Description and tags hint at a dynamic programming solution, but for some reason I can’t 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 optimal result (see the proof below).

However, you did not calculate the cost of this solution correctly. You must run all the pairs of your combination to find the quality value of the best and worst pairs, and only after you find them, you can subtract their values. Btw. you do not need a priority queue to find the minimum (they are considered for more complex use cases, when you insert and set several times and even update the values ​​in the queue), I will do simple battery variables ( min and max ). Assuming array a already sorted, the code might 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 prove why the pairing you have chosen (iteratively, pairs of the best remaining students with the worst remaining student) is optimal, which is significant here. If this fails, we need a whole different algorithm.

We prove this by showing that it is not possible to improve the solution given by this pairing.

If we wanted to improve it, we would have to reduce the difference between the best and the worst pair, which means either a decrease in the best pair or an increase in the worst pair (or both).

Let them first show why lowering the best pair is impossible.

Let pair indices be given: the pair containing the largest 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, up to p_n. For instance:

 pab 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 these pairs, let it be called 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 this pair. But with whom can we pair a_m , so that the new pair has a lower amount? We need to find a b , let's call it b_y below b_m (otherwise this would not be an improvement). We can only find the bottom b_y by going up the list, i.e. y < m . But the same thing happens for all pairs: if we have a pair up ( p_x with x < m ) and try to find a new partner b_y for the old a_x , we must take into account that a_x >= a_m , which makes it impossible to choose from y . If we choose a y>=m , this means 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 should be below m . Given this limitation, m possible values ​​for a ( {a_1,...,a_m} ) have only m-1 possible partners {b_1,...b_(m-1)} , so pairing is not possible. Therefore, a decrease in the value of the best pair was impossible.

In the above example: To reduce the maximum of 15, all pairs must have values ​​lower than 15. This means that all left values ​​of the pairs are higher or equal to the maximum pair (8, 8, 9, 10) partners will be required that are lower than the maximum partner on the right side (7); therefore, only 1, 4, and 5 are possible.

The proof that increasing the worst pair is impossible works the same with the inverse comparison operators and switches to a and b (in this case, too much b for too few a s).

Answer 2

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

Step 2 and the next in your approach is wrong. We do not need a priority queue. We only need to find the maximum and minimum amount of the created pairs.

pseudo code:

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

---

(†) Why is this so?

Consider the considered array containing 1 2 3 6 . It looks like this:

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

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

Well, we cannot do this, we can clearly see it in the image. We can move 3 above average only one place below average. But there are 2 such places, size 2 and 1.

It’s better if we fill in the biggest gap, so first left. Thus, we got the sums 7 and 5, which are slightly different from the average, but minimally - by 1. Any other pairing will be the same or worse.

Answer 3

This can help if, after sorting the array, you start adding values ​​from two ends (from the first to the last, etc.), saving only the max and minimum results instead of the queue. Then you can get the 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 

Brief proof of solution: After the sort values ​​can be displayed in this way, <= b <= c ... <= k <= n. Now suppose that all values ​​are different, therefore a <b <c <... <k <n. If the values ​​differ then (ba> = 1) so (b => a + 1), as well as (n => k + 1). For a + n and b + k, the difference will be at least (a + n) - (b + k) = (a + n) - (a + 1 + n-1) = 0. For a + k and b + n the difference will be at least (b + n) - (a + k) = (a + 1 + n) - (a + n-1) = 2. This can be expanded at <= c and so on. If some values ​​are the same, the replacement will have no effect.