You have two friends, call them A and B. They each are given two wine bottles: o

Question

You have two friends, call them A and B. They each are given two wine bottles: one bottle holds k_1 litres and the other k_2 litres. Both A and B can perform these operations: - completely fill a wine bottle with wine - completely empty a wine bottle - pour the wine of one bottle into the other bottle, making sure to stop only when either the bottle being filled is full or if when the bottle being emptied is completely empty. Assume the litres of wine are all positive ints.

Q: Determine if there exist a seq of operations that leaves exactly k_3 litres of wine in the bigger wine bottle. Try representing this as a graph problem.

My idea: define the vertices to be a pair of integers in a graph. I got this as a recent interview question. But couldn't solve the entire problem in time. Then they said you could have apparently applied some algo to this problem too, and that it had a complexity that was fast enough. Any ideas?

Explanation / Answer

The idea is to construct a directed graph whose vertices are labelled by pairs of integers (a1,a2), where 0?ai?ki (I'm assuming that k1,k2 are integers). There is also an additional vertex t. The vertex (a1,a2) represents the fact that bottle i holds ai litres. Connect (a1,a2) to (b1,b2) if a single operation can take you from state (a1,a2) to state (b1,b2). Connect (a1,a2) to t if a1=k3 (assuming k1?k2). Now check using your favorite graph search algorithm whether t is reachable from (0,0).

This algorithm runs in time O(k1k2). One wonders whether there is a faster algorithm running in time polynomial in the input size log(k1k2).

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.