Minimize the maximum absolute difference of adjacent elements when at most k elements can changed to any integer

user_14618354 0
Viewed 1224

We have given an array of integers A with n elements, and an integer k.

We need to minimize the maximum absolute difference between the adjacent elements, such that at most k elements can be changed to any integer.

With constraints: n <= 2000 and -10^9 <= A[i] <= 10^9 for all 0 <= i < n. Also, k <= n.

My approach was to try binary search. I kept lower limit as zero and upper limit as maximum absolute difference of adjacent elements currently in the array. Then check if it is possible to make an array having some amount, let's say m = (l + (r - l) / 2), is possible after changing k elements to have as the maximum absolute difference of adjacent elements.

But I was not able to check this possibility efficiently? I tried to brute force my way by changing the adjacent elements if the difference is greater than said m. But I am missing something here. Can anyone suggest any solutions?

binary-search algorithm c++
1 Answers

This problem is possible to solve using Dynamic Programming approach.

We will reduce full task to sub-tasks recursively. For each position i within array if we're allowed to modify k0 elements lets build an array d[i][k0] that says what is the answer for sub-task of array A[0..i] and custum k0 values to change. With one exception - d[i][k0] gives optimal solution for the case if A[i] is not being changed.

Now if we can build an answer for d[i][k0] if we know all answers for smaller i. Remember that by definition A[i] is not changed. It means we can build a segment of changed values A[l+1..i-1] (here segment_len = i - l - 1) plus use answer d[l][k0 - segment_len], out of these two we can see that d[i][k0] is maximum of d[l][k0 - segment_len] and minimized difference inside changed segment. We can see that segment can be built optimally just by taking step equal to (last - first + segment_len - 1) / segment_len.

Now iterating over all lengths of a segments we can find minimal possible d[i][k0]. Final answer for whole task is d[n][k].

I think better optimization is possible, but I solved this Dynamic Programming task through 3 nested loops. If I give random input to my code, it returns answer after exactly 1 second for n = 1000, k = 500 and after 8 seconds for n = 2000, k = 1000.

I even have ideas how to speedup this considerably. But probably I'll implement them later if I have time.

So time complexity of my algorithm is O(n * k^2) of simple operations and memory complexity is O(n * k).

Try it online!

#include <cstdint>
#include <vector>
#include <limits>

using i32 = int32_t;

i32 Solve(std::vector<i32> const & A, i32 n, i32 k) {
    std::vector<std::vector<i32>> d(n + 1, std::vector<i32>(k + 1));
    for (i32 i = 0; i <= n; ++i)
        for (i32 k0 = 0; k0 <= k; ++k0) {
            i32 rmin = std::numeric_limits<i32>::max();
            for (i32 j = 0; j <= k0; ++j) {
                i32 r = 0;
                if (i - 1 - j < 0)
                    r = 0;
                else if (i >= n)
                    r = d[i - 1 - j][k0 - j];
                else {
                    i32 step = (std::abs(A[i] - A[i - 1 - j]) + j) / (j + 1),
                        prev = d[i - 1 - j][k0 - j];
                    r = std::max(step, prev);
                }
                rmin = std::min(rmin, r);
            }
            d[i][k0] = rmin;
        }
    return d[n][k];
}

#include <random>
#include <chrono>
#include <iomanip>
#include <iostream>

void Test() {
    auto Time = []{
        static auto const gtb = std::chrono::high_resolution_clock::now();
        return std::chrono::duration_cast<std::chrono::duration<double>>(
            std::chrono::high_resolution_clock::now() - gtb).count();
    };

    std::mt19937_64 rng{std::random_device{}()};
    std::uniform_int_distribution<i32> distr(-1'000'000'000, 1'000'000'000);
    i32 n = 1'000, k = 500;
    std::vector<i32> A(n);
    for (size_t i = 0; i < A.size(); ++i)
        A[i] = distr(rng);
    //for (auto x: A) std::cout << x << " "; std::cout << std::endl;
    auto tim = Time();
    i32 res = Solve(A, n, k);
    tim = Time() - tim;
    std::cout << "Result " << res << ", time " << std::fixed
        << std::setprecision(4) << tim << " sec" << std::endl;
}

int main() {
    Test();
}

Output:

Result 295187479, time 1.0335 sec
user_9415310
Related