×

# DPAIRS - EDITORIAL

Setter: Noszály Áron
Tester: Xiuhan Wang
Editorialist: Taranpreet Singh

Easy

# PREREQUISITES:

Sorting and maps and a nice Observation.

# PROBLEM:

Given two sets of distinct integers $A$ and $B$. Choose $|A|+|B|-1$ pairs $(x,y)$ such that values $A_x+B_y$ for all pairs is pairwise distinct where $|X|$ means size of set $X$.

# SUPER QUICK EXPLANATION

• Simple way to find distinct $|A|+|B|-1$ values is to sort both $|A|$ and $|B|$ in ascending order, pair smallest element of one set with all element from the second set and largest element of the second set with all but first element of the first set. This way, we get $|B|+(|A|-1) = |A|+|B|-1$ distinct values which is what we want.
• The reason these values are distinct is that $x+y < x+z$ if $y < z$. This is happening for all consecutive pairs generated in this manner. Indices can be taken care of using maps or arrays itself.

# EXPLANATION

Subtask 1: $|A|, |B| \leq 10^3$.

Here, constraints are small enough to try each pair of elements in both sets, finding pairs having distinct values and printing $|A|+|B|-1$ pairs with distinct sums.

Subtask 2: $|A|, |B| \leq 2*10^5$

Now, we cannot iterate over every pair of values. We need to be smart.

Let us sort both sets in ascending order, and pair first element of $A$ with all elements of $B$, getting $|B|$ pairs. If the first element of $A$ is $x$, Sum of these $|B|$ pairs is pairwise distinct as the set of sums of these pairs is nothing but all values of $B$ increased by $x$.

Now, suppose $y$ is the largest value present in $B$ and $z$ be second value in $A$. Since $z > x$, we have $y+z > y+x$. So, we can now pair the second element of $A$ with the last element of $B$ to get a distinct sum value.

This way, we can continue to pair all values in $A$ with the largest element of $B$ (except first, as it is already paired), getting $|A|-1$ more pairs.

Hence, we have got our required $|A|+|B|-1$ pairs. Indices can be preserved using maps, or arrays itself.

Want to solve it faster? See the box below.

View Content

Exercise:

Prove that the minimum number of pairs that can be generated having distinct sums is $|A|+|B|-1$ irrespective of the value present in set $A$ and $B$ have distinct values.

Also, Generate a large test case where this minimum value is achieved. (Hint in box)

View Content

# Time Complexity

The time complexity is $(|A|*log(|A|)+|B|*log(|B|))$ due to sorting.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

4.0k31103
accept rate: 22%

19.8k350498541

 2 This problem can be solved even without sorting the arrays. answered 14 Jan, 19:50 21●1 accept rate: 0% exactly !! just find index of minimum and maximum values... (14 Jan, 22:15)
 1 I solve with binary search. The idea it's search a sum biggest then last you have find answered 15 Jan, 01:08 12●1 accept rate: 0% Can you elaborate? (15 Jan, 01:30) eugalt3★
 0 The tests are too weak. How do you like these "solutions"? :) https://www.codechef.com/viewsolution/22488840 https://www.codechef.com/viewsolution/22488851 answered 15 Jan, 00:27 3★eugalt 282●7 accept rate: 4%
 0 Can someone tell me why my solution didn't work? I put A and B into vectors and sorted A and B. Then I took the smallest index of A which is 0 and paired with all indexes of B and then I took the largest index of B which is B.size() - 1 and paired it with all values of A starting from index 1 since 0 is smallest index of A. Why didn't this solution work? https://www.codechef.com/viewsolution/22488614 answered 15 Jan, 01:09 1 accept rate: 0%
 0 Hello @michael_123, I think your solution is failing because you're printing the new indexes (the ones you have after the sort) instead of the previous ones. So your solution can only works when the smallest element of A is at index 0 and when the biggest element of B is at index m-1. answered 15 Jan, 01:21 29●4 accept rate: 11%
 0 Can anyone help me out here..My solution is still getting WA for some test cases. I have paired minsetA with all values of setB to get |B| values. Further I have paired maxSetB with all values of setA but first_(minsetA)_ hence getting another |A|-1 values, original indices have also been maintained. Where I have possibly gone wrong? https://www.codechef.com/viewsolution/22490725 answered 15 Jan, 12:53 1●1 accept rate: 0% vector< pair< int,int > > B(n); - should be m. (15 Jan, 19:28) eugalt3★
 0 why sorting of the vector is necessary for subtask 2.without sorting the vector code is working just for subtask 1. answered 15 Jan, 20:17 1 accept rate: 0% I didn't understand what you were trying to say, but no sorting is necessary for either subtask. :) (16 Jan, 08:48) eugalt3★
 0 @satheesh2k14 read the question again, it is already mentioned that all the elements of the array are distinct. answered 16 Jan, 11:26 -863●9 accept rate: 0%
 0 can someone help I'm failing only 1 test case in the first sub task remaining is ok click here answered 16 Jan, 12:39 17 accept rate: 20%
 0 3 4 1 2 3 2 3 4 6  You pick both (1, 6) and (3, 4) which have the same sum. Unbelievably, you almost got an AC, showing test cases are so weak. answered 17 Jan, 07:47 4★petch 18●1 accept rate: 14%
 0 IT CAN BE SOLVED WITHOUT SORTING. JUST FIND THE MINIMUM ELEMENT OF ONE SEQUENCE AND THE MAXIMUM ELEMENT OF THE OTHER SEQUENCE. answered 17 Jan, 08:27 0●1 accept rate: 0% Everybody has figured that out - no need to SCREAM. xD (17 Jan, 10:20) eugalt3★
 0 All the test cases, except 3 in the first subtask, have n = m. https://www.codechef.com/viewsolution/22515213 answered 17 Jan, 11:54 3★eugalt 282●7 accept rate: 4%
 0 can this problem be solved using SET? adding elements and then inserting in the set, if size increases then display indexes. answered 17 Jan, 12:13 1 accept rate: 0%
 0 What does it mean "Ax+By for all pairs is pairwise distinct"? Anyone. answered 18 Jan, 09:47 2★yash005 2●2 accept rate: 0%
 0 For the editorial solution to work, either sequence A or sequence B should be unique. But no where in the problem it was mentioned or is it mentioned in the problem? answered 03 Feb, 21:10 2★Sabari 2●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×3,820
×1,409
×721
×264
×112
×4