Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Minimize absolute difference between adjacent elements where atmost K changes allowed.

Revision en2, by eleganc, 2022-10-11 09:30:53

Hi, I recently faced this problem in an OA. Any approaches to solve this?

An array consists of N elements. We want to minimize the absolute difference between adjacent elements of the array. We can change any integer to any other integer however at most K changes are allowed. If n <= 1 return 0.

Here is the exact problem link: https://www.codechef.com/CRK32020/problems/KEVIN?tab=statement There is some hint toward binary search, but I don't precisely infer how it is to be applied.

Constraints: 1 ≤ k ≤ n ≤ 2000 -1e9 ≤ Ai ≤ 1e9

Eg. N = 6, K = 3 Arr = [1 2 3 7 8 9] Here Arr can be transformed to [1 2 3 4 5 6] in 3 changes. And the answer becomes 1.

#### History

Revisions

Rev. Lang. By When Δ Comment
en2 eleganc 2022-10-11 09:30:53 179
en1 eleganc 2022-10-11 09:27:56 578 Initial revision (published)