PROBLEM LINK:Practice Setter: Noszály Áron DIFFICULTY: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
EXPLANATIONSubtask 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. 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) Time ComplexityThe time complexity is $(|A|*log(|A|)+|B|*log(|B|))$ due to sorting. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 14 Jan, 16:02 ![]()
|
This problem can be solved even without sorting the arrays. answered 14 Jan, 19:50 ![]()
|
I solve with binary search. The idea it's search a sum biggest then last you have find answered 15 Jan, 01:08 ![]()
|
The tests are too weak. How do you like these "solutions"? :) answered 15 Jan, 00:27 ![]()
|
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? answered 15 Jan, 01:09 ![]()
|
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 ![]()
|
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? answered 15 Jan, 12:53 ![]()
|
Answer is hidden as author is suspended. Click here to view.
answered 16 Jan, 11:26 ![]()
|
@officialnizam Try
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 ![]()
|
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 ![]()
|
All the test cases, except 3 in the first subtask, have n = m. answered 17 Jan, 11:54 ![]()
|
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 ![]()
|
What does it mean "Ax+By for all pairs is pairwise distinct"? Anyone. answered 18 Jan, 09:47 ![]()
|
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 ![]()
|