Editorial for DMOPC '20 Contest 6 P6 - Dumping Buckets

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: d, Riolku

Let be the current amount of water in bucket and be the maximum amount of water in bucket .

Note that when we pour bucket into bucket , if the answer is less than , we know . Otherwise, we know .

That's all well and good if we know and , but what if we don't?

Well if we take a full bucket, for instance, and pour it into a bucket with known volume, and then fill it and pour again, we have quite a bit of information. To be specific, if we take a bucket with known volume and a full bucket of unknown capacity , then we can dump into to start. Call this return value . Then we fill again, and dump from into . We get the return value . Evidently, .

Now, if , we know that is full, so , and we need to determine the bucket , which is empty.

If , we know that .

If , we can actually apply both observations, the reasoning of which is left as an exercise to the reader.

We can move left-to-right in our array and consider our pairs. After operations, we have necessarily found one of our two buckets, and have left the other with a known volume.

In order to start with a bucket of known volume, we empty out bucket .

After our operations, we can take any bucket, and keep filling and dumping it into the remaining bucket we require. We keep doing this while our dump operations return a positive number, and while the current volume is smaller than , since if it is equal to , we know the capacity is .

Operations:

Full Solution

We are quite close to the full solution. Let's split up our pair processing part into two cases. In all cases, we have one bucket of unknown capacity and known volume and a full bucket (also of unknown capacity).

Case 1: the bucket of unknown capacity has zero volume

In this case, other than the very start, we can actually prove that we will always get here with another bucket of known volume. A little paper work should reveal this. In this case, we can do the following, assuming is the empty bucket.

• dump into
• dump into

If the second operation returns , we know the capacity of . Otherwise, we know the capacity of .

Case 2: the bucket of unknown capacity has positive volume

In this case, we do the following, assuming is the full bucket.

• dump into
• dump into

Recall that we know . After the first operation, if there was no overflow, we have . In such case, the second operation will overflow, and we will know .

On the other hand, if the second operation does not overflow, we know that , and thus that , so this tells us .

Final Thoughts

The main observation here is that after processing a pair, we have a bucket of known volume, and a full bucket. If the bucket we don't know is empty, we have an extra bucket of known volume which is non-empty. Otherwise, if the bucket we don't know is non-empty, we can apply case 2, and reach one of our cases again.

To wrap this up, we can apply the strategy above.

Operations:

P.S.: since a dump operation empties the source bucket, we don't need the empty operation.

P.S.S: We can actually save one operation in the second phase of the problem, since we have a bucket of known volume (alongside our last required bucket). Thanks to wleung_bvg for pointing this out.