Find minimum number of changes in array to make k-arithmetic progression

Question

I recently encountered this problem:

In the challenge, you are given an array of n numbers and an integer k. In one minute, you can change any element of the array to any integer you want. Find the minimum amount of time you have to spend so that the following condition is satisfied: for all i from to 1, n - 1, a[i] - a[i - 1] = k. Since n, k <= 10^5 the solution should be linear (O(n)) or maybe O(n * logn) which I doubt.

I greedy and realized that this problem is probably DP, but I couldn't find an answer. This topic is similar, but the answers there are not of use (in my opinion). I'm just looking for a pseudo (or cpp) code.

UPD: I code a brute force solution in O(n^2), if it helps you here is the code:

    #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);  

    int n, k;
    cin >> n >> k;

    vi a(n);
    for (auto& i : a)
        cin >> i;

    int res = INT32_MAX;
    for (int i = 0; i < n; ++i){
        int s = a[i], sol = 0;
        for (int j = i + 1; j < n; ++j){
            s += k;
            if (a[j] != s)
                ++sol;
        }
        s = a[i];
        for (int j = i - 1; j > -1; --j){
            s -= k;
            if (a[j] != s)
                ++sol;
        }
        res = min(sol, res);
    }

    cout << res << '\n';
}

Have you tried to apply dynamic programming to this problem yourself? Where specifically you have an issue with that? People here are much more likely to help a person who showed some actual effort in the question. — SergGr, Jun 19 '18 at 10:27
@SergGr My try was completely wrong. I don't think it would help anyone, instead I gave brute force in UPD. — Dean Ambrose, Jun 19 '18 at 10:30
In similar theme https://stackoverflow.com/questions/50922702/ I has been warned that question is from ongoing contest — MBo, Jun 19 '18 at 12:05
Ooooh, that I did not know. Should I remove my answer? Feels a bit late now. — Qubit, Jun 19 '18 at 14:22
@Qubit Yes, you should remove your answer until the contest is ended. — Prune, Jun 19 '18 at 15:54
I'm voting to close this question as off-topic because asking for outside help is a violation of the contest rules. — Prune, Jun 19 '18 at 15:55
I am sorry for making this situation. I didn't know that I shouldn't ask while there is a contest (which I am not a part of). — Dean Ambrose, Jun 19 '18 at 17:51

Qubit · Accepted Answer · 2018-06-19T10:50:23.563

I'm not entirely sure this fits here, you're asking for an algorithm, if I understood correctly.

You need to find the smallest number of elements to change such that the progression is satisfied. I'd suggest you substract the slope, i.e. a[i]-=k*i, now all you have to do is find the number which occurs most often in the new array (more importantly, how many times it appears). Basically, you want to ask how many points lie on certain lines (a[i]=k*i+m), so you substract the slope and count the occurances of each m. The value of m which appears most often has the highest number of points with appropriate value, so all we have to do is fix all the other points.

Given that your values can be large (I assume), you can use std::map to do the counting, this should give you O(n*log(n)) at worst. The final result is then n-maxReps, where maxReps is the number of repetitions of the most repeated value in the new array. As we said, the number of values we still need to change such that they satisfy our condition.

Essentially you just count the number of points you have to fix so that they lie on your line.

I'll leave the implementation to you.

That should be clear, at worst, look at the question. – Qubit Jun 20 '18 at 08:23 — Qubit, Jun 20 '18 at 08:23

Find minimum number of changes in array to make k-arithmetic progression

1 Answers1