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?
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?
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?
Isn't it just bipartite matching?
yes it is...
Thanks, it does seem like a bipartite matching problem. Could you expand how to solve it using bipartite matching? Not really familiar with 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 :)