silversRayleigh's blog

Help in forming two disjoint sets
By silversRayleigh, history, 6 years ago, In English

Hello Everyone,

I was trying to solve a problem in which I was given a set of number(in range 1-10^5 and size of set is at max 10^5). Task was to form the two disjoint sets from the given set such that sum of elements of each set is at least X(in range 1-10^5) and sum of size of both sets is minimized.

I tried a lot but could only come up with O(n^2) solution. Can anyone please suggest some idea on how to do it?

Note : Union of disjoint sets need not be the original set.

TIA

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How about binary searching for the minimal sum of sizes? Clearly, if you can form such two sets with k elements, you can also form two such sets with the k largest elements in your set.

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think it's the same as this problem?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I could not understand the editorial so I was looking for alternate method or better explanation of the given method.

    → Reply