webstorms's blog

Pick distinct numbers problem
By webstorms, history, 9 years ago, In English

Say you are given an array. Every cell in the array stores three numbers. The objective is to determine if you can select a number (from the 3 given) for each cell such that all numbers are distinct.

Example: Input: (1,2,3),(1,2,5),(2,5,6) Output: 1,5,6 (all of distinct, good)

Input: (1,1,1),(1,1,1),(2,5,6) Output: 1,1,6 (not all distinct, hence impossible)

Any ideas how this problem could be solved in good time complexity? My ideas where to think of this as a graph problem. Maybe there is a greedy approach to this?

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

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

Thinking in graphs is always a good idea. You could make a vertex for each cell and one for each (distinct) number, connecting a cell and a number when we the number is one of the three numbers you can put in this cell. How can you characterize a solution to the problem in this graph?

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

    Ah. Not sure if this would be correct.

    Build the graph like you suggested.

    Now iteratively do the following: Look for nodes that have 0 edges. If such a node exists then a solution is impossible. Look for nodes that have 1 edge (i.e only one distinct number) then we are forced to use that number and hence we choose it. We prune all other edges that connect from that distinct number to all other cells. We continue this process seeking cells that have one edge. If no cell has 0 or 1 incoming edge then I guess we can pick any of the numbers that the cell links too, right?

    At the end simply print the numbers that node links too.

    Would that work?

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

Isn't it just bipartite matching?

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

    yes it is...

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

    Thanks, it does seem like a bipartite matching problem. Could you expand how to solve it using bipartite matching? Not really familiar with it.

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

      First of all, if the numbers are big, you can compress them so that every number is in the interval [1;3*N]. Let's say the three numbers for position i are A[i], B[i], C[i]. Build a bipartite graph where on the left are the indices — 1,..,N and on the right are the numbers 1,..,3*N. For each vertex V on the left side, add an edge to A[V], B[V] and C[V]. Then the maximum matching will give you the solution.

      PS: http://mirror.codeforces.com/blog/entry/19718 :)

      → Reply