DPAIRS - EDITORIAL

data-structure
dpairs
easy
jan19
observations
taran_1407

#1

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. :slight_smile:


#2

This problem can be solved even without sorting the arrays.


#3

The tests are too weak. How do you like these “solutions”? :slight_smile:

https://www.codechef.com/viewsolution/22488840

https://www.codechef.com/viewsolution/22488851


#4

I solve with binary search. The idea it’s search a sum biggest then last you have find


#5

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


#6

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.


#7

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


#8

why sorting of the vector is necessary for subtask 2.without sorting the vector code is working just for subtask 1.


#9

@satheesh2k14 read the question again, it is already mentioned that all the elements of the array are distinct.


#10

(post withdrawn by author, will be automatically deleted in 24 hours unless flagged)


#11

@officialnizam Try

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.


#12

IT CAN BE SOLVED WITHOUT SORTING. JUST FIND THE MINIMUM ELEMENT OF ONE SEQUENCE AND THE MAXIMUM ELEMENT OF THE OTHER SEQUENCE.


#13

All the test cases, except 3 in the first subtask, have n = m.

https://www.codechef.com/viewsolution/22515213


#14

can this problem be solved using SET?
adding elements and then inserting in the set, if size increases then display indexes.


#15

What does it mean “Ax+By for all pairs is pairwise distinct”? Anyone.


#16

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?


#17

exactly !!
just find index of minimum and maximum values…


#18

Can you elaborate?


#19

vector< pair< int,int > > B(n); - should be m.


#20

I didn’t understand what you were trying to say, but no sorting is necessary for either subtask. :slight_smile: