OrBiTal (easy)

A particle contributes $K^2$ in total. With $S=\sum A_i$, only strengths satisfying $K^2\mid S$ need checking. A particle has peak $K$, so also require $K\leq\max A_i$.

Fix $K$ and scan from left to right. After subtracting contributions of triangles already started, the remaining value at the current position forces the number of triangles starting there: the leftmost coefficient is $1$. Reject a negative count or a positive count at a position without room for a complete length-$2K-1$ triangle.

To implement the scan in linear time, set $A_0=A_{-1}=0$ and $C_i=A_i-2A_{i-1}+A_i$. Let count triangles starting at position , with out-of-range earlier counts zero. Then compute

$$X_i=C_i+2X_{i-K}-X_{i-2K}.$$

Require $0\leq X_i\leq A_i$ and require $X_i=0$ for .

For $D$ candidate strengths, the time complexity is $O(ND+N)$ and the space complexity is $O(N)$. Subtask 1 permits checking all $K\leq10$ in time. In subtask 2, checking every strength without the sum filter gives a sufficient solution.

Proof

Consider the leftmost position $i$ not yet matched. A triangle starting later cannot affect it. After contributions of earlier triangles are removed, only triangles starting at $i$ can supply the remainder. Their leading coefficient is $1$, so their count is forced. Repeating this argument never discards a feasible solution.

The second difference of a triangle is $1$ at its start, $-2$ after $$ positions, and after positions. Thus the recurrence computes precisely the forced counts. If every count is nonnegative and every start is allowed, all triangles lie within the line. The produced sequence and the target have the same left boundary values and second differences, hence agree at every position.

Solution written by GPT6