This is a problem from usaco, which I solved, but I don't know how to estimate the number of times you can pour milk among the jugs, my solutions just uses a big enough number.

Here's the problem statement:

Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.

Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

For example, if the input is 8, 9, 10 then the output is 1, 2, 8, 9, 10.

Another example: if the input is 2, 5, 10 then the output is 5, 6, 7, 8, 9, 10.

My approach is to recursively try all possible move sequences, keeping track of the contents of bucket C each time bucket A is empty. Currently I stop the recursion at the arbitrary depth 200. What is the correct depth to stop the recursion at?

  • $\begingroup$ Please replace your code with pseudocode. If I understand correctly, you want to know whether there is an a priori bound on the length of solutions to this problem. If so, please make it clear. $\endgroup$ – Yuval Filmus Mar 14 '16 at 10:12
  • $\begingroup$ @YuvalFilmus this is my pseudocode. Where it is unclear what it does I wrote comments, such as TreeSet is a red black tree, I think everything else is pretty clear... I try to recursively find all possible distributions of milk in jugs, but I don't know how to estimate recursion depth of the recurse function. $\endgroup$ – Pavel Mar 14 '16 at 10:14
  • $\begingroup$ Maybe you shouldn't have taken out the code... There are many ways to solve this, including DP with 3 nested loops. And some other ways. $\endgroup$ – Pavel Mar 14 '16 at 10:18
  • 1
    $\begingroup$ We don't answer programming questions here. If your question requires code then it is out of scope here. Your question was about setting a bound on the depth for your particular algorithm, which can be summarized in one sentence instead of as code. If you're unhappy, try to explain your question better. $\endgroup$ – Yuval Filmus Mar 14 '16 at 10:20

Since the total amount of water is C liters (C being the capacity of bucket C), the number of possible states is at most the number of non-negative integer solutions of $x+y+z = C$, which is $\binom{C+2}{2}$. Any sequence of moves longer than that must repeat a state. Therefore it is enough to recurse up to level $\binom{C+2}{2}$.

  • $\begingroup$ Can you please tell me how you got C+2 choose 2? $\endgroup$ – Pavel Mar 14 '16 at 10:22
  • $\begingroup$ That's a standard result in combinatorics. More generally, the number of solutions of $x_1+\cdots+x_n=C$ is $\binom{C+n-1}{n-1}$. $\endgroup$ – Yuval Filmus Mar 14 '16 at 10:59
  • $\begingroup$ thanks, good upper bound. However I think it can be done better, because there are constraints on the numbers. $\endgroup$ – Pavel Mar 14 '16 at 11:02

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.