Repair an Arithmetic Progression
National Olympiad — National round (2019 season)
Submission name: progres.cpp
Problem summary
Change the fewest values without reordering to obtain an arithmetic progression of prescribed positive difference d.
Input
N d and N values.
Output
Minimum changed positions.
Constraints
2 ≤ N < 10^6; 1 ≤ d < 50; positive input values below 30000000.
Worked example
Input and output for the worked example discussed below.
Input
8 2 9 4 6 8 8 12 14 1
Output
3
Solution analysis
- At 0-based position i, a progression starting at x has x+i×d. Keeping a[i] unchanged requires x=a[i]−i×d.
- Transform all entries to their implied first values and find the largest frequency. Keep those positions and change all others; sorting provides deterministic frequency runs.
- Five sample entries imply first value 2. Changing positions 1,5,8 gives 2,4,6,8,10,12,14,16, requiring three changes.
Why it works
Exactly the positions with one common implied first value can remain unchanged together.
Complexity: O(N log N) time and O(N) space.
Watch out. Compute transforms before sorting. Implied first values can be negative; new progression values are unrestricted integers.
Commented C++17 solution
An independently written complete program with standard headers.
// Exactly the positions with one common implied first value can remain unchanged together.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int count,difference;
cin>>count>>difference;
vector<long long>first(count);
for(int index=0;index<count;index++){
long long value;
cin>>value;
first[index]=value-1LL*index*difference;
}
sort(first.begin(),first.end());
int best=0;
for(int left=0;left<count;){
int right=left+1;
while(right<count&&first[right]==first[left]){
right++;
}
best=max(best,right-left);
left=right;
}
cout<<count-best<<'\n';
}