PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Noszály Áron
Tester: Xiuhan Wang
Editorialist: Taranpreet Singh
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
- 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.
Click to view
We can find the smallest element of A and largest element of B in linear time too, bringing down the complexity to O(|A|+|B|).
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)
Click to view
Roll a pair of dice. Another hint?
Click to view
Roll a pair of dice once again!!
Time Complexity
The time complexity is (|A|*log(|A|)+|B|*log(|B|)) due to sorting.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 