Contest Duration: - (local time) (120 minutes) Back to Home
Official

## F - Gateau Editorial by evima

Let $$b_i$$ be the number of strawberries on Piece $$i$$. Then, we can express the request of Friend $$i$$ as follows:

• if $$i < N$$, $$b_i + b_{i+1} + \cdots + b_{i+N-1} \geq A_i$$;
• if $$i \geq N$$, $$b_i + b_{i+1} + \cdots + b_{2N-1} + b_0 + \cdots + b_{i-N-1} \geq A_i$$.

We want to minimize the total number of strawberries $$b_0 + b_1 + \cdots + b_{2N-1}$$ while satisfying these conditions.

Let $$X_{opt}$$ be the minimum number of strawberries needed. Then, for any $$X \geq X_{opt}$$, we can have exactly $$X$$ strawberries on the whole cake, so let us do a binary search on the answer to turn the problem into a decision problem: can we have exactly $$X$$ strawberries on the whole cake?

Conveniently, for a fixed total number of strawberries, the condition for $$i \geq N$$, $$b_i + b_{i+1} + \cdots + b_{2N-1} + b_0 + \cdots + b_{i-N-1} \geq A_i$$, is equivalent to $$b_{i-N} + b_{i-N+1} + \cdots + b_{i-1} \leq X - A_i$$.

Additionally, let $$s_i = d_0 + d_1 + \cdots + d_{i-1}$$. Then, the request of Friend $$i$$ can be expressed as follows:

• if $$i < N$$, $$s_{i+N} - s_i \geq A_i$$;
• if $$i \geq N$$, $$s_i - s_{i-N} \leq X - A_i$$.

Thus, the problem is equivalent to determining whether it is possible to satisfy all of the following conditions, where $$L_i = A_i, R_i = X - A_{i+N}$$:

• $$0 = s_0 \leq s_1 \leq \cdots \leq s_{2N} = X$$;
• $$L_i \leq s_{i+N} - s_i \leq R_i$$ for every $$i = 0, 1, \dots, N-1$$.

Let us first consider the case the value of $$s_N$$ is fixed to $$M$$. We can solve this case as follows:

1. First, we have $$s_0 = 0, s_N = M$$.
2. For each $$i = 1, 2, \dots, N-1$$ in this order, do the following:
• if $$L_i \leq s_{i+N-1} - s_{i-1} \leq R_i$$, let $$(s_i, s_{i+N}) = (s_{i-1}, s_{i+N-1})$$;
• if $$s_{i+N-1} - s_{i-1} < L_i$$, let $$(s_i, s_{i+N}) = (s_{i-1}, s_{i-1} + L_i)$$;
• if $$s_{i+N-1} - s_{i-1} > R_i$$, let $$(s_i, s_{i+N}) = (s_{i+N-1} - R_i, s_{i+N-1})$$.
3. If we end up with both $$s_{N-1} \leq s_N$$ and $$s_{2N-1} \leq X$$, we have made a sequence satisfying the conditions. Otherwise, there is no sequence satisfying them.

We have no time to do this for all possible values of $$s_N$$, but notice the following property:

Let $$f_1(a, b), f_2(a, b)$$ be respectively the values of $$s_{N-1}, s_{2N-1}$$ obtained in the greedy algorithm above when we first set $$s_0 = a, s_N = b$$. If $$a \leq a', b \leq b'$$, then $$f_1(a, b) \leq f_1(a', b')$$ and $$f_2(a, b) \leq f_2(a', b')$$ hold.

From this, the larger $$s_N$$ is, the larger $$s_{2N-1}$$ will be, so the condition $$s_{2N-1} \leq X$$ will hold when $$s_N$$ is not larger than some constant value (possibly $$-\infty$$).

Additionally, the larger $$s_N$$ is, the smaller $$s_N - s_{N-1}$$ will be, because if we hypothetically let $$s_0 = -M, s_N = 0$$, the smaller $$M$$ is, the larger $$s_{N-1}$$ will be. Thus, the condition $$s_{N-1} \leq s_N$$ will hold when $$s_N$$ is not less than some constant value (possibly $$\infty$$).

Therefore, we can do a binary search to find the range of $$s_N$$ where we can make a sequence, which solves the decision problem in $$O(N \log A)$$ time, and the whole problem in $$O(N \log^2 A)$$ time.

It is also possible to solve the decision problem in $$O(N)$$ time, resulting in the total complexity of $$O(N \log A)$$.

(Although it will not run in time, we note that it is possible to solve the decision problem using the Bellman-Ford algorithm in $$O(N^2)$$ time by seeing it as a special case of a linear programming problem.)

Sample Implementations:

posted:
last update: