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

Правка en2, от 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.

Теги dynamic programming, binary search, ad hoc

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский eleganc 2022-10-11 09:30:53 179
en1 Английский eleganc 2022-10-11 09:27:56 578 Initial revision (published)