Editorial for DMOPC '20 Contest 3 P3 - A Ring of 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.

Author: Riolku

For the first subtask, some very naive brute force will work. Each bucket will be poured into at most times, and there are of them, so there are possible combinations, each taking operations to check

Time Complexity:

For the second subtask, note that if we have three consecutive buckets, and the first is poured into times and the second times, then we must pour into the third one times. We can thus brute force all possibilities for the first two values of the answer array, and use this formula to get the remaining ones. If any values are negative or larger than , we don't have a solution.

Time Complexity:

Note first that if is not divisible by , we do not have a solution.

Furthermore, note that if is divisible by , a possible solution is , repeated times.

For the remainder of this editorial, let be our answer array, where is the amount we pour into the first bucket, and is the amount we pour into the th bucket.

In fact, our buckets are in a circle, so let's make infinite in both directions, where we have .

Now, let be arbitrary consecutive elements of .

Note that we must have , as mentioned in subtask 2.

For this subtask, if , we have:

Or:

So every third element is equal.

It should be clear that if every third element is equal, unless is divisible by , (that is, all elements are equal).

If is not divisible by , then we must have a solution with all identical elements, or no solution at all.

If is divisible by , the following pattern yields the lexicographically smallest solution:

And this is all that is required for the subtask.

Time Complexity:

For this subtask, we consider . We now have:

So we have:

If is odd, we have:

Or:

So every other element is equal. In fact, if is odd:

So every element is equal. This case proceeds similar to the case mentioned above.

However, if is even, the case proceeds differently. Let . Then:

Also, let . Then:

So , or , or .

So every other element is equal. Then:

So must be even in order for a solution to exist.

In fact, our lexicographically smallest pattern is:

This concludes the case.

Time Complexity:

For this subtask, we have . We have:

Or:

Without loss of generality, assume , since if , we can consider the array backward.

Then, since :

We have equality only when . Assume that . Then:

This means that:

However, this means:

Thus, we must have , which tells us that every element of the array must be equal.

In fact, when , we have a solution if and only if is divisible by .

Time Complexity:

To finish off the solution, we need help from a little math.

Suppose our answer contains a repeating cycle of length . Note that for this problem, . Let , and note that it must be an integer. Then we need to compute:

Note that this inner sum can be precomputed. Assign it the value :

This should look very similar to the geometric sequence formula, and we can apply it here:

Note that since we are computing our answer modulo , instead of dividing, we need to multiply by the multiplicative modular inverse.

Time Complexity:

Final Thoughts

Although this problem has an (admittedly exhausting) proof, this problem should teach you to try solutions. Many who solved this problem attempted submitting times and got AC on the case, and proceeded from there. The other way to approach this is bottom up; look at the subtasks and solve them individually, and then combine them together.

This problem isn't meant for you to sit and stare at for hours. Don't be afraid to guess.