You are not logged in. Please login at www.codechef.com to post your questions!

×

DPAIRS - EDITORIAL

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.

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:

Setter's solution
Tester's solution
Editorialist'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

taran_1407's gravatar image

6★taran_1407
3.9k2791
accept rate: 22%

edited 14 Jan, 19:34

admin's gravatar image

0★admin ♦♦
19.8k350498541


This problem can be solved even without sorting the arrays.

link

answered 14 Jan, 19:50

kakneprateek's gravatar image

3★kakneprateek
211
accept rate: 0%

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

(14 Jan, 22:15) l_returns5★

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

link

answered 15 Jan, 01:08

gustavocandido's gravatar image

3★gustavocandido
121
accept rate: 0%

Can you elaborate?

(15 Jan, 01:30) eugalt2★

The tests are too weak. How do you like these "solutions"? :)

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

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

link

answered 15 Jan, 00:27

eugalt's gravatar image

2★eugalt
2827
accept rate: 4%

edited 15 Jan, 03:23

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

link

answered 15 Jan, 01:09

michael_123's gravatar image

2★michael_123
1
accept rate: 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.

link

answered 15 Jan, 01:21

semantycs's gravatar image

3★semantycs
294
accept rate: 11%

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

link

answered 15 Jan, 12:53

suyash_888's gravatar image

2★suyash_888
11
accept rate: 0%

edited 15 Jan, 12:54

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

(15 Jan, 19:28) eugalt2★

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

link

answered 15 Jan, 20:17

cyber_ghost's gravatar image

2★cyber_ghost
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) eugalt2★
Answer is hidden as author is suspended. Click here to view.

answered 16 Jan, 11:26

karangreat234's gravatar image

4★karangreat234
(suspended)
accept rate: 0%

can someone help I'm failing only 1 test case in the first sub task remaining is ok click here

link

answered 16 Jan, 12:39

officialnizam's gravatar image

2★officialnizam
0
accept rate: 0%

@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.

link

answered 17 Jan, 07:47

petch's gravatar image

4★petch
181
accept rate: 14%

edited 17 Jan, 07:53

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

link

answered 17 Jan, 08:27

sandy5858's gravatar image

3★sandy5858
01
accept rate: 0%

Everybody has figured that out - no need to SCREAM. xD

(17 Jan, 10:20) eugalt2★

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

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

link

answered 17 Jan, 11:54

eugalt's gravatar image

2★eugalt
2827
accept rate: 4%

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

link

answered 17 Jan, 12:13

sarthak281998's gravatar image

1★sarthak281998
1
accept rate: 0%

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

link

answered 18 Jan, 09:47

yash005's gravatar image

1★yash005
01
accept rate: 0%

edited 18 Jan, 09:48

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?

link

answered 03 Feb, 21:10

Sabari's gravatar image

2★Sabari
21
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,741
×1,401
×649
×228
×109
×4

question asked: 14 Jan, 16:02

question was seen: 3,009 times

last updated: 03 Feb, 21:12