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

## B - Sum of Three Terms Editorial by evima

### [1] Structure of the solutions of the simultaneous linear

equations

First, let us consider what kind of sequences $$A$$ satisfy $$S_i = A_i + A_{i+1} + A_{i+2}$$, including ones with $$A_i < 0$$.

This equation can be rephrased into $$A_{i+2} = S_i - A_i - A_{i+1}$$. Thus, deciding $$A_1$$ and $$A_2$$ produces exactly one sequence satisfying the condition by the recurrence relation $$A_{i+2} = S_i - A_i - A_{i+1}$$.

By letting $$A_1 = a$$, $$A_2 = b$$ and calculating the values of $$A_i$$, we can see that the solutions of the equations can be represented as follows, using some sequence of constants $$(x_1, \ldots, x_{N+2})$$ and parameters $$a, b$$.

$\begin{cases} A_i = x_i + a & (i = 1, 4, 7, \ldots)\\ A_i = x_i + b & (i = 2, 5, 8, \ldots)\\ A_i = x_i - a - b & (i = 3, 6, 9, \ldots)\\ \end{cases}$

### [2] The solution to the problem

The problem asks us to determine the existence of a solution in the form above and to construct one if it exists. By rephrasing this to conditions regarding the parameters $$a, b$$, we have the following problem.

You are given constants $$c_1, c_2, c_3$$. Determine the existence of a pair $$(a, b)$$ that satisfies all of the inequalities, and construct one if it exists.

• $$c_1\leq a$$
• $$c_2\leq b$$
• $$a+b\leq c_3$$

This problem can be solved as follows:

• If $$c_1 + c_2 > c_3$$, no solution exists.
• If $$c_1 + c_2\leq c_3$$, $$(a, b) = (c_1, c_2)$$ is one of the valid solutions.

Summing up the above, the original problem can be solved in $$\Theta(N)$$ time.

posted:
last update: