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

Subtask 1

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

Time Complexity: \mathcal O(QN^{M+1})

Subtask 2

For the second subtask, note that if we have three consecutive buckets, and the first is poured into a times and the second b times, then we must pour into the third one c = M - bK - a 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 M, we don't have a solution.

Time Complexity: \mathcal O(QNM^2)

Subtask 3

Note first that if NM is not divisible by K + 2, we do not have a solution.

Furthermore, note that if M is divisible by K + 2, a possible solution is \frac{M}{K + 2}, repeated N times.

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

In fact, our buckets are in a circle, so let's make A infinite in both directions, where we have A_i = A_{i + N}.

Now, let a, b, c, d be arbitrary consecutive elements of a.

Note that we must have a + bK + c = M, as mentioned in subtask 2.

For this subtask, if K = 1, we have:

\displaystyle a + b + c = M \displaystyle b + c + d = M

Or:

\displaystyle a - d = 0 \displaystyle a = d

So every third element is equal.

It should be clear that if every third element is equal, unless N is divisible by 3, A_i = A_{i + 1} (that is, all elements are equal).

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

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

\displaystyle 0, 0, M, 0, 0, M, 0, \ldots

And this is all that is required for the K = 1 subtask.

Time Complexity: \mathcal O(QN)

Subtask 4

For this subtask, we consider K = 2. We now have:

\displaystyle a + 2b + c = M \displaystyle b + 2c + d = M

So we have:

\displaystyle a + b - c - d = 0 \displaystyle a + b = c + d

If N is odd, we have:

\displaystyle A_i + A_{i + 1} = A_{i + 2} + A_{i + 3} = A_{i + N - 1} + A_{i + N} = A_{i - 1} + A_{i}

Or:

\displaystyle A_{i + 1} = A_{i - 1}

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

\displaystyle A_i = A_{i + 2} = A_{i + N + 1} = A_{i + 1}

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

However, if N is even, the case proceeds differently. Let X = a + b. Then:

\displaystyle \sum_{i = 1}^N A_i = A_1 + A_2 + \ldots + A_N = \frac{N}{2} \times X

Also, let Y = b + c. Then:

\displaystyle \sum_{i = 1}^N A_i = A_1 + A_2 + \ldots + A_N = A_2 + A_3 + \ldots + A_{N + 1} = \frac{N}{2} \times Y

So X = Y, or a + b = b + c, or a = c.

So every other element is equal. Then:

\displaystyle a + 2b + c = M \displaystyle 2a + 2b = M

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

In fact, our lexicographically smallest pattern is:

\displaystyle 0, \frac{M}{2}, 0, \frac{M}{2}, 0, \ldots

This concludes the K = 2 case.

Time Complexity: \mathcal O(QN)

Subtask 5

For this subtask, we have K \ge 3. We have:

\displaystyle a + bK + c = M \displaystyle b + cK + d = M

Or:

\displaystyle a - b + (b - c)K + (c - d) = 0 \displaystyle (b - c)(K - 1) = d - a

Without loss of generality, assume b \ge c, since if b < c, we can consider the array backward.

Then, since K > 2:

\displaystyle  1 < K - 1 \displaystyle  (b - c) \le (K - 1)(b - c) = (d - a)

We have equality only when b = c. Assume that b > c. Then:

\displaystyle (b - c) < (d - a) \displaystyle a + b < c + d

This means that:

\displaystyle A_i + A_{i + 1} < A_{i + 2} + A_{i + 3} < A_{i + 4} + A_{i + 5} < \ldots

However, this means:

\displaystyle A_i + A_{i + 1} < A_{i + 2N} + A_{i + 2N + 1} = A_i + A_{i + 1}

Which is a contradiction.

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

In fact, when K > 2, we have a solution if and only if M is divisible by K + 2.

Time Complexity: \mathcal O(QN)

Subtask 6

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

Suppose our answer contains a repeating cycle C of length L. Note that for this problem, L \le 3. Let Y = \frac{N}{L}, and note that it must be an integer. Then we need to compute:

\displaystyle \sum_{i = 1}^N A_i \times B^{i - 1} = \sum_{i = 1}^Y \sum_{j = 1}^L C_j \times B^{L(i - 1) + (j - 1)} \displaystyle \sum_{i = 1}^Y (B^L)^{i - 1} \sum_{j = 1}C_j \times B^{j - 1}

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

\displaystyle \sum_{i = 1}^{Y} Z \times (B^L)^{i - 1}

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

\displaystyle Z \times \frac{\left(B^L\right)^Y - 1}{B^L - 1}

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

Time Complexity: \mathcal O(Q \log N)

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 \frac{M}{K + 2} N times and got AC on the K \ge 3 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.


Comments

There are no comments at the moment.