SUMPAIR - Editorial

PROBLEM LINK:

Practice
Contest

Author: Devendra Agarwal
Tester: Surya Kiran
Editorialist: Amit Pandey

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given an array A of N positive integers, you can pair two numbers if difference between them is D. Find out maximum sum of disjoint sum of pairs you can obtain.

QUICK EXPLANATION:

Sort the array A in increasing (non-decreasing) order. Let us go from the end to beginning of the array. If last number should be matched, then the best number with which it can be matched is the next-to-last one only because the difference between numbers can only increase if we consider elements prior to the next-to-last one (i.e. element at positions N - 2 or less). Remove the last element and optionally the next-to-last element if a pair is made and keep doing the same for the remaining array.

Explanation

Greedy solution

Let us look only at the last number i.e. the number at position N. If we want to match this number of any number, then we will prove that it’s best to match it with the next-to-last number, i.e., at position N-1. First, as the array is sorted, if we go from index N to 1, difference between A* and A[N] will only increase, so the least difference will be only at position N-1. Now, let’s assume that N is matched to some i other than N-1, then we can always swap this assignment and get a better solution which leads to contradiction.

So, for last number, we find whether the difference between last and next last number is less than D or not. If yes, then we form a pair. Now, we will remove the last element and its pairing element too (if one exists), and solve the problem for the remaining array similarly.

ans = 0;
for i = N to 2:
	if (A* - A[i-1] < D)
		ans += A* + A[i-1];
		i -= 2;
	else
		i -= 1;

Time complexity of the algorithm is dominated by the sorting part, i.e. \mathcal{O} (N * log N) time.

Dynamic programming based solution

Let dp* denotes the maximum disjoint pair sum we can get using first i elements of the array.
Assume, we are currently at i-th position, there are two possibilities for us.

  • Pair up i with i-1, i.e. dp* = dp[i-2] + A* + A[i-1]
  • Don’t pair up, i.e. dp* = dp[i-1]

Pseudo code of this idea follows.

int dp[N+1];
for i from 1 to N:
	dp* = max(dp[i-2] + A* + A[i-1], dp[i-1]);
ans = 0;
for i from 1 to N:
	ans = max(ans, dp*);

Time complexity of this algorithm is \mathcal{O}(N * log N) (for sorting) + \mathcal{O}(N) (for DP). Overall, we can say that time complexity is \mathcal{O}(N * log N).

AUTHOR’S, TESTER’S SOLUTIONS:

setter’s solution
tester’s solution

1 Like

https://www.codechef.com/viewsolution/7507828
This code gives WA. Can anyone tell me in which test case it fails?

hey can u pls help me out with this ! i am getting WA
https://www.codechef.com/viewsolution/7511049

https://www.codechef.com/viewsolution/7510184
I don’t get the error in my code. Help please!

Can anyone please explain the case when the numbers in the array would be :-

Value of D = 3;

8 10 10 12

Is the disjoint pairs can have same numbers as in the above case…

(8,10) & (10,12) (diff is strictly less than D)

Can someone explain me the solution for this question if the condition “DISJOINT” is not there?

Well well what tragedy.
wrong editorial for solution 1.
it is for loop so in if condition it should be i-=1 and no else is needed

i did exactly same still i got wa …my code 7508528

you did same mistake as i did, make that ans variable long long int, it give you AC(considering that your quicksort works well correctly), its int tragedy :frowning:

Can you reset the link?

thanks @sagarpatel,its got ac now ,…, and now i feel like crying:( for not noticing such a common mistake

its really annoying:( when you commit suh a mistake

u need not remove duplicates
TC
1
4 3
10 12 10 12

ans: 44
not 22

@kislaya123 yes you can have such a case.As in the question its written that the indices(position) of a,b,c,d in the array should be different.So (8,10) and (10,12) are disjoint pairs as 1 of the 10 has index 2 andd the other one has index 3.

make sum long long int…