DISTINCT PAIRS
Pages: 12
Chef has two integer sequences A1,A2,…,AN and B1,B2,…,BM. You should choose N+M−1 pairs, each in the form (Ax,By), such that the sums Ax+By are all pairwise distinct.
It is guaranteed that under the given constraints, a solution always exists. If there are multiple solutions, you may find any one
Example Input
3 2
10 1 100
4 3
Example Output
2 1
0 0
1 0
0 1
Explanation
The chosen pairs and their sums are:
A3+B2=100+3=103
A1+B1=10+4=14
A2+B1=1+4=5
A1+B2=10+3=13
Since all sums are distinct, this is a correct output.
Problem link: https://www.codechef.com/JAN19B/problems/DPAIRS
It is guaranteed that under the given constraints, a solution always exists. If there are multiple solutions, you may find any one
Example Input
3 2
10 1 100
4 3
Example Output
2 1
0 0
1 0
0 1
Explanation
The chosen pairs and their sums are:
A3+B2=100+3=103
A1+B1=10+4=14
A2+B1=1+4=5
A1+B2=10+3=13
Since all sums are distinct, this is a correct output.
Problem link: https://www.codechef.com/JAN19B/problems/DPAIRS
Last edited on
I'm not sure where a binary search would come into play.
What have you tried so far? Have you tried simply iterating through each pair of numbers and looking for distinct sums?
What have you tried so far? Have you tried simply iterating through each pair of numbers and looking for distinct sums?
By your 25th post you should know that "NEED HELP!!" is a totally useless title. Obviously you need help. Be more specific (like "Codechef prolem whatever_it's_called"). And you should include a link to the problem.
well u need to give only n+m-1 pairs
why that specific amount of pairs...ummm!!!
well there goes your hint.
why that specific amount of pairs...ummm!!!
well there goes your hint.
I tried but I didn't get exactly why only n+m-1 pairs is given
can anyone give some more idea about it?
can anyone give some more idea about it?
@cool123dude, Thanks for fixing your title and adding the link. :-)
But explaining why n+m-1 pairs are requested pretty much gives the whole thing away.
Look more closely at the constraints. They ensure that n+m-1 distinct pairs are possible
Another little(?) hint is that you don't need to store all the values (so you don't need vectors or arrays at all),
Make up a small input example following the constraints and try to see why n+m-1 distinct sums are always possible. Doing that is the key to these kinds of problems.
But explaining why n+m-1 pairs are requested pretty much gives the whole thing away.
Look more closely at the constraints. They ensure that n+m-1 distinct pairs are possible
Another little(?) hint is that you don't need to store all the values (so you don't need vectors or arrays at all),
Make up a small input example following the constraints and try to see why n+m-1 distinct sums are always possible. Doing that is the key to these kinds of problems.
Last edited on
I'm not a fan of this batch of problems. They are much more about finding patterns than about math or programming. I guess you could call "finding patterns" math but it's not very interesting to me.
I gave up on competitive programming problems long ago. It's all boring to me. I just helped out on this one because I had told him he should fix his title and give a link, and he actually did! I thought he deserved a reward for that.
And obviously finding patterns is a BIG part of math and programming!
BTW, some loser spammed the "report" button! Hilarious! What do you expect to happen? Get a life, loser!
And obviously finding patterns is a BIG part of math and programming!
BTW, some loser spammed the "report" button! Hilarious! What do you expect to happen? Get a life, loser!
Last edited on
| dutch wrote: |
|---|
| And obviously finding patterns is a BIG part of math and programming! |
Yeah, you're right. I do find these particular problems boring, though. I like the problems that require implementation of search algorithms and complex data structures (at least beyond the data structures most languages provide). These problems are just "spot the pattern and you win." The December long challenge had more of a focus on search and data structures, and I learned stuff that I have applied in "real world" applications since then. These problems are just mini-puzzles that are trivial to solve once you spot a simple pattern.
| dutch wrote: |
|---|
| BTW, some loser spammed the "report" button! Hilarious! What do you expect to happen? Get a life, loser! |
Well it is a "competition." People shouldn't seek help until the contest is over and the problems are archived. No it was not me who reported the posts. I don't really care.
Last edited on
@Browni3141, I didn't think it was you. Your first post was reported, too, as you gave an extremely small hint there. It was an anonymous hit and run. I don't care, either, but "reporting" may just make me do it more!
Last edited on
@Browni3141 this platform has helped me grow as programmer
Obviously discussing your whole approach to a problem is not good for anyone
But getting a little hint to problem you don't even have a clue about how to start is better than waiting for 10 days to get an answer according to me.
Obviously discussing your whole approach to a problem is not good for anyone
But getting a little hint to problem you don't even have a clue about how to start is better than waiting for 10 days to get an answer according to me.
Last edited on
i had an idea to just sort the values and do it my complexity is around nlogn
but it is not working
but it is not working
Last edited on
I think that concentrating N+M-1 pairs is a decent enough hint.
@ks692 Sorting is not wrong.I also sorted it. Also think about the cases when the length of both the arrays is different. In my algorithm I had to handle this case a little differently. @ks692 you maybe on the right track.Think harder! I think that anymore hints might just give the question away
@ks692 Sorting is not wrong.I also sorted it. Also think about the cases when the length of both the arrays is different. In my algorithm I had to handle this case a little differently. @ks692 you maybe on the right track.Think harder! I think that anymore hints might just give the question away
Pages: 12