Frez's blog

Choose n distinct number from n set
By Frez, history, 9 years ago, In English

Suppose we have n set of numbers . we want to choose a number from each set that they were distinct . how we can do it efficiently ?

A -> 1 <= n <= 20 , 1 <= |s| <= 100 , 1 <= numbers <= 10^9

B -> 1 <= n <= 10^5 , 1 <= |s| <= 10^5 , 1 <= numbers <= 10^9

C -> In General ?

thanks in advance.

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Frez (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
← Rev. 23   Vote: I like it +17 Vote: I do not like it

Denote the n sets as (Ai)i = 1..n, then let . Now consider a bipartite graph with a vertex for each set on the left side, a vertex on the right set for each element , and an edge from the vertex representing set Ai to the vertex representing the element x if and only if . Clearly any maximum bipartite matching induces a selection of elements from the sets such that each element is distinct (prove this yourself).

In other words, the problem can certainly be solve in polynomial time. However, the complexity isn't great. The number of vertices is n + |S| (recall that S is the set of distinct elements), and the number of edges is . Hopcroft-Karp gives an algorithm. (Note: using a appropriate datastructures (maps etc) this reduction takes time, it is important that the complexity of the new problem supersedes the complexity of the reduction).

However, the reduction works the other way around. Given a bipartite graph, denote the left side as V1 and the right side as V2. For , let . If we can select a distinct element from each set, this clearly induces a complete bipartite matching. Note that this reduction takes O(V1 + V2 + E) time, less than the best known bound on bipartite matching.

In other words, this problem is equivalent to deciding whether a bipartite graph has a maximal matching.

EDIT: Hopcroft-Karp is , not .

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    THANKS:) really awesome! This was hard for me to understand but I got it finally.

    related problem is here. I hope I can solve it now :D

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      That problem is a bit different from the one you mentioned above (or maybe I misinterpreted it). But you can also solve it using bipartite matching.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      I just tried the problem and (as expected) it worked. Of course I would recommend first trying it yourself, but if you can't figure it out, here is my solution. All relevant code is in the main (the rest is just generic max flow code), I added some comments to make everything clear.

      → Reply