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

×

Two Sets(CF)

How to approach Two Sets?

asked 26 Sep '14, 18:28

amitpandeykgp's gravatar image

4★amitpandeykgp
25911522
accept rate: 0%

edited 26 Sep '14, 19:33


There are different ways to approach this question. I am presenting the greedy approach.
Assuming a is less than b, if not you can swap them to make it so.
Sort the given numbers.
We start checking from the smallest number x.
1) First we see if b-x exists.If it does then both x and b-x will go to set B.(The reason we can say this with certainty is suppose a-x also exists and we assign x and a-x to the set A, then b-x will not be able to go set B as numbers are distinct and only one x exists, and for it to go to set A it will need a number smaller than x,(because a<b) but there is no such number(as we are considering the smallest number available). Thus we can say that if b-x exists, both x and b-x will be put in set B.
2) After this the problem is easy. If b-x does not exist, check if a-x exist. If it does assign both x and a-x to set A. If it does not we can not divide the numbers in two sets as required.
3) Continue the same with the remaining numbers.

link

answered 26 Sep '14, 20:40

thunderking's gravatar image

6★thunderking
166137
accept rate: 0%

@thunderking, Thanks for the approach. I am having doubt for this case:

x,x,a-x,b-x,b-x.

So A[0] = x; A[1] = x; A[2] = a-x; A[3] = b-x; A[4] = b-x;

Now suppose you sent element x,x,b-x,b-x to Set B. Then answer for the following case will be "NO". Please correct me if I am wrong.

(27 Sep '14, 02:36) amitpandeykgp4★

It is given in the problem statement that the all numbers are distinct, therefore this case never arises.

(27 Sep '14, 05:24) thunderking6★

Thank you :)

(28 Sep '14, 09:47) amitpandeykgp4★

suppose the array is {6,7} a=13 b=12. Then this approach will not give the correct answer. I think we need to handle the case when x=a/2 or x=b/2.

(28 Sep '14, 15:11) sikander_nsit5★

@sikander_nsit if the array is {6,7} and a=13,b=12, then this approach will give the correct answer because as I have written in the explanation, we assume b is greater and if it is not, we swap A and B to make it so then both 6 and 7 will go to set B which is 13. This will also handle the case if x=a/2 or b/2 as we are trying to find a-x or b-x except x itself.

(29 Sep '14, 01:15) thunderking6★

Thanks...got it.

(02 Oct '14, 02:56) sikander_nsit5★
showing 5 of 6 show all

Another obvious approach could be by formulating the problem as a perfect bipartite matching problem and then use Hopcroft-Karp algorithm for solving it.

How to identify it as a bipartite matching problem?

It's quite easy to make a note that the array needs to be split into 2 disjoint sets. This pretty much indicates that one can use bipartite matching algortihm.

Why perfect?

This part was easy enough to figure out as it was clearly mentioned in the problem:

He wants to divide all of them into two sets A and B

here's a link to code

Hope that helps :)

link

answered 29 Sep '14, 00:54

chandan721's gravatar image

3★chandan721
2113919
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:

×623

question asked: 26 Sep '14, 18:28

question was seen: 926 times

last updated: 02 Oct '14, 02:56