Two Sets(CF)

How to approach Two Sets?

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.
4 Likes

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

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

Thank you :slight_smile:

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.

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

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

Thanks…got it.