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\).
◆ Finding the answer
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)\).
◆ Sample Implementation
posted:
last update: