Sequence (Line)
Given an array of n integers, find the minimum number of elements to change so the result is an arithmetic sequence a + bi for positions i = 0, 1,, n-1.
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
Given an array of $n$ integers, find the minimum number of elements to change so the result is an arithmetic sequence $a + bi$ for positions $i = 0, 1, \ldots, n-1$.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Key Observation
If we keep elements at positions $i$ and $j$ ($i < j$), the common difference is $d = (\text{arr}[j] - \text{arr}[i]) / (j - i)$, which must be an integer. The starting value is $a = \text{arr}[i] - d \cdot i$.
Lemma.
If the optimal solution keeps $\ge 3$ elements, then at least two of the first three positions ($0, 1, 2$) are kept.
Proof.
If none of positions $0, 1, 2$ is kept, at most $n - 3$ elements are kept, which can only be optimal when $n \le 5$. If exactly one is kept, any single element can be paired with any other to define a candidate, but we need at least two kept elements to fix the arithmetic sequence. The lemma follows from a case analysis: among any three consecutive kept positions, at least one pair involves position $0$, $1$, or $2$.
Algorithm
For each pair $(i, j)$ where $i \in \{0, 1, 2\}$ and $j > i$: compute $d$ and $a$, then count matches in $O(n)$.
This gives $O(n)$ candidate sequences, each checked in $O(n)$ time.
Handle edge cases: $n \le 2$ always has answer $0$.
Complexity Analysis
Time: $O(n^2)$ -- $O(n)$ candidate pairs, each checked in $O(n)$.
Space: $O(n)$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
int minimum_changes(vector<int>& arr) {
int n = arr.size();
if (n <= 2) return 0;
int best = 2; // We can always keep at least 2 elements (or 1)
// Try all pairs involving positions 0, 1, or 2
// If the optimal keeps >= 3 elements, at least 2 must be among {0, 1, 2}.
// Actually, at least one of the first 3 positions must be kept.
// More precisely: if we keep elements at positions p1 < p2 < p3 < ...,
// and p1 >= 3, then we only keep n-3 or fewer from positions 3..n-1,
// so kept <= n-3. If n-3 > best so far, we'd need to try.
// The standard approach: try pairs from first 3 positions with all others.
auto try_seq = [&](long long a, long long d) {
int cnt = 0;
for (int i = 0; i < n; i++) {
if ((long long)arr[i] == a + (long long)d * i)
cnt++;
}
best = max(best, cnt);
};
for (int i = 0; i < min(n, 3); i++) {
for (int j = i + 1; j < n; j++) {
long long diff = (long long)arr[j] - arr[i];
long long gap = j - i;
if (diff % gap != 0) continue;
long long d = diff / gap;
long long a = (long long)arr[i] - d * i;
try_seq(a, d);
}
}
// Also try keeping just one element with various d values:
// For n <= small, we could try all pairs. For large n, the above covers it.
return n - best;
}
int main() {
int n;
scanf("%d", &n);
vector<int> arr(n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("%d\n", minimum_changes(arr));
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.