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

Revision en1, by eleganc, 2022-10-11 09:27:56

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.

Tags dynamic programming, binary search, ad hoc

History

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