2
$\begingroup$

The ACM Contest Problem 102 (HTML or PDF) can be paraphrased as:

Given 3 bins each containing possibly different number of bottles of 3 colors, move the bottles so that there is one color per bin, minimizing the number of bottle movements.

Specifically, we wish to decide on an allocation of colors to bins so that moving from the initial position to the "sorted" position requires the least number of bottle moves. The bins are assumed to have infinite capacity.

For the problem as stated, one can brute-force check all $3! = 6$ permutations to see which has the fewest number of bottle movements. However, for $N > 3$ colors of glass, $N!$ grows very large. Is there a way to solve this problem for general $N$ that runs in polynomial time?

$\endgroup$
  • $\begingroup$ Can you define what counts as a "bottle move"? Does it involve moving a single bottle? Or moving an arbitrary number of bottles from one bin to another bin? $\endgroup$ – D.W. Oct 26 '14 at 16:47
1
$\begingroup$

Yes, this can be solved in polynomial time, for arbitrary $N$. This is an instance of the assignment problem, for which polynomial-time algorithms are known.

You want to assign a color of glass to each bin, such that each bin gets exactly one color, and each color is assigned to exactly one bin. The cost of assigning bin $b$ to color $c$ is the number of bottle moves needed to move all bottles of color $c$ that aren't currently in bin $b$, into bin $b$. Therefore, this is an assignment problem.

(You can compute this cost function more efficiently as follows: the cost of assigning bin $b$ to color $c$ is the number of moves needed to move all bottles that aren't colour $c$ out of bin $b$. Thanks to @David Richerby for this insight.)

The assignment problem can be solved using standard methods, e.g., the Hungarian algorithm or algorithms for min cost max flow.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.