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

## A - Arithmetic Sequence Editorial by evima

### ◆ Dimensionality reduction

The sequence $$A$$ is arithmetic if and only if $$2A_2 - A_1 - A_3 = 0$$, so it is the value $$2A_2 - A_1 - A_3$$ that matters, rather than $$A_i$$ themselves.

Therefore, let us define $$X = 2A_2 - A_1 - A_3$$. We can compute the value of $$X$$ after doing some operations without using the values of $$A_i$$ themselves, so let us ignore them. In the end, our problem is as follows.

Given is an integer $$X$$. We can do the following two kinds of operations.

• Add $$-1$$ to $$X$$. (Equivalent to choosing $$i = 1$$ or $$3$$.)
• Add $$2$$ to $$X$$. (Equivalent to choosing $$i = 2$$.)

Find the minimum number of operations to make $$X = 0$$.

Now our situation is simpler with just one variable (dimension) $$X$$ instead of three: $$A_1, A_2, A_3$$.

Let $$k$$ be the number of times we add $$2$$ to $$X$$. Then, it is necessary that $$k\geqq 0$$ and $$X + 2k\geqq 0$$, which can be represented as $$k\geqq k_0$$ where $$k_0 = \max(0, \lceil (-X)/2\rceil)$$.
If we fix $$k\geqq k_0$$, we need to do $$X + 2k$$ additions of $$-1$$, for a total of $$X + 3k$$ operations. In order to minimize this number, we should minimize $$k$$, which means the answer is $$X + 3k_0$$. The time complexity of our approach is $$\Theta(1)$$.