[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.

• Sample Code (Python)：https://atcoder.jp/contests/arc135/submissions/29021066