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

Subtask 1

Let cur(x) be the current amount of water in bucket x and cap(x) be the maximum amount of water in bucket x.

Note that when we pour bucket x into bucket y, if the answer z is less than cur(x), we know cap(y) = cur(y) + z. Otherwise, we know cap(x) = z.

That's all well and good if we know cur(x) and cur(y), 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 cur(x) and a full bucket of unknown capacity y, then we can dump y into x to start. Call this return value a. Then we fill y again, and dump from y into x. We get the return value b. Evidently, cur(x) = cur(x) + a + b.

Now, if b = 0, we know that x is full, so cap(x) = cur(x), and we need to determine the bucket y, which is empty.

If b = a, we know that cap(y) = a.

If b < a, 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 N - 1 pairs. After 3 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 1.

After our 3(N - 1) + 1 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 M, since if it is equal to M, we know the capacity is M.

Operations: 3N + 2M

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 k of known volume. A little paper work should reveal this. In this case, we can do the following, assuming x is the empty bucket.

  • dump y into x
  • dump k into x

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

Case 2: the bucket of unknown capacity has positive volume

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

  • dump y into x
  • dump x into y

Recall that we know cur(x) > 0. After the first operation, if there was no overflow, we have cur(x) > cap(y). In such case, the second operation will overflow, and we will know cap(y).

On the other hand, if the second operation does not overflow, we know that cur(x) \le cap(y), and thus that cap(x) = cur(x), so this tells us cap(x).

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 2M strategy above.

Operations: 2N + 2M

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.


Comments

There are no comments at the moment.