[Guest]

You have n pots, each having a random amount of water in it, the total amount of water in all the pots is 2*n, you need to distribute the water among the pots equally so that each pot will have exactly 2 liters in it...

Find an algorithm to come up with the best solution with the minimum amount of steps, in each step you can only pour water from 1 pot to another...

Doesn't matter the complexity of the algorithm itself, only that the solution is shortest, but ofcourse faster algorithms are better...

[bushindo]

You have n pots, each having a random amount of water in it, the total amount of water in all the pots is 2*n, you need to distribute the water among the pots equally so that each pot will have exactly 2 liters in it...

Find an algorithm to come up with the best solution with the minimum amount of steps, in each step you can only pour water from 1 pot to another...

Doesn't matter the complexity of the algorithm itself, only that the solution is shortest, but ofcourse faster algorithms are better...

How about this strategy

1) Sort the n pots into two sets A and B, where A consist of all pots with more than 2 liters, and B consist of all pots with less than 2 liters.

2) At every turn, pick a pot from A and a pot from B. There is a way to pour the water so that you'd get 1 pot with exactly 2 liters, and the other pot will belong to either A and B. (For instance, if pot a has 2.5 liters, and pot b has 1.7 liters, then pour .3 liters from a to b, and we end up with pots of 2 liters and 2.2 liters, respectively). Put the pot with exactly 2 liters aside, and put the other pot back into either A or B depending on its content. If we are lucky, then we might get two pots that are exactly 2 liters each, but that situation is trivial to deal with.

3) Repeat 2) for (n-1) times. Each time we remove 1 pot from A or B. After a maximum of (n-1) turns, we should be done.

[Guest]

^ You've got the upper bound right, but I think you could optimize it a bit more, here's the solution I thought of when I first started thinking of this riddle:

Let's say you have K pots with 2*K liters of water in them, you can sort them from fullest to least full and then take the first (fullest) pot and pour all but 2 liters into the second, take the second and pour all but 2 into the third and so on and so on, this would distribute the water in exactly K-1 steps, let's call this the trivial algorithm.

To improve on the trivial algorithm we can divide the pots into groups if there were 6 pots with 12 liters of water and we managed to divide them into 2 groups of 3 pots with 6 liters in each, then if we solve each group separately using the trivial algorithm we can do it in 4 steps instead of 5, ..

The general idea is that the more groups you divide the pots into the more steps you save, you save exactly one step each time you divide a single group into 2 groups.

So the algorithm is as follows, for each number K, starting from 1, search for goups of K pots that have 2*K liters in them and solve them separately using the trivial algorithm, so first you search for single pots that have 2 liters and solve them in 0 steps, then pairs of pots that have 4 liters and solve them in 1 step, then groups of 3 and solve in 2 steps and so on and so on..

you do not need to search for groups larger than N/2, because for example if there were 20 pots, if you haven't found any groups of size 1-10 you surely won't find a group of size 11 because if that group had 22 liters of water then the other 9 pots have 18 liters of water and so they are a group of 9...

The upper bond for this algorithm is still N-1 steps, there is always a distribution that cannot be solved in less than that (you can put all the water into a single pot, or you can distribute the water so that each pot holds an amount that has a fraction value of 1/N, for example if there were 20 pots make sure each pot has .05 liters)

Edited August 25, 2011 by Anza Power

[bushindo]

^ You've got the upper bound right, but I think you could optimize it a bit more, here's the solution I thought of when I first started thinking of this riddle:

Let's say you have K pots with 2*K liters of water in them, you can sort them from fullest to least full and then take the first (fullest) pot and pour all but 2 liters into the second, take the second and pour all but 2 into the third and so on and so on, this would distribute the water in exactly K-1 steps, let's call this the trivial algorithm.

To improve on the trivial algorithm we can divide the pots into groups if there were 6 pots with 12 liters of water and we managed to divide them into 2 groups of 3 pots with 6 liters in each, then if we solve each group separately using the trivial algorithm we can do it in 4 steps instead of 5, ..

The general idea is that the more groups you divide the pots into the more steps you save, you save exactly one step each time you divide a single group into 2 groups.

So the algorithm is as follows, for each number K, starting from 1, search for goups of K pots that have 2*K liters in them and solve them separately using the trivial algorithm, so first you search for single pots that have 2 liters and solve them in 0 steps, then pairs of pots that have 4 liters and solve them in 1 step, then groups of 3 and solve in 2 steps and so on and so on..

you do not need to search for groups larger than N/2, because for example if there were 20 pots, if you haven't found any groups of size 1-10 you surely won't find a group of size 11 because if that group had 22 liters of water then the other 9 pots have 18 liters of water and so they are a group of 9...

The upper bond for this algorithm is still N-1 steps, there is always a distribution that cannot be solved in less than that (you can put all the water into a single pot, or you can distribute the water so that each pot holds an amount that has a fraction value of 1/N, for example if there were 20 pots make sure each pot has .05 liters)

Since you are interested in the 'fastest' algorithm, an computational complexity analysis is in order

The efficiency of an algorithm is often measured by the number of operations it needs to make. I'll just handwave here some and say that operations are steps that the computer must take in order to carry out an algorithm. For instance, we can think of an if comparison as an operation. We can also think of an addition procedure as an operation as well. The idea is the less operations we need, the faster the algorithm is.

In the trivial algorithm you mentioned, we first need to sort an list of size n. Optimal sorting is known to have on average (n log n ) operations. That is not bad, but there are ways to construct a trivial algorithm with linear complexity of (n).

The optimization you mentioned where you search for all subgroups of size k = (1, 2, ..., n/2) such that their total water is 2*k is probably more trouble than it is worth. There are a total of (_nC₁ + _nC₂ + ... + _nC_n/2 = 2^n-1) comparisons that you need to check. So let's say that n = 21. If we do a search for all possible subgroups, we will waste about 1,000,000 comparisons just to find what the subgroups are. On the other hand, if we apply the trivial algorithm without the subgroup search, we would be done in less than 30 operations.

[bonanova]

Another consideration is that the probability of finding subgroups is zero.

Well not exactly zero, since "exactly 2 liters" is an integer number of HOH molecules.

If we discuss balls in urns, subgroups would occur with more useful probability.