Minimize Cost
Tag(s):

## Basic Programming, Greedy algorithm, Medium

Problem
Editorial
Analytics

You are given an array of numbers $A_{i}$ which contains positive as well as negative numbers . The cost of the array can be defined as $C(X)$

$C(x) = |A_{1} + T_{1}| + |A_{2}+T_{2}| + ........ |A_{n}+T_{n}|$ , where T is the transfer array which contains N zeros initially.

You need to minimize this cost . You can transfer value from one array element to another if and only if the distance between them is at most K.

Also, transfer value can't be transferred further.

Say array contains $3, -1 , -2$ and $K = 1$

if we transfer 3 from $1^{st}$ element to $2^{nd}$ , the array becomes

Original Value $3, -1,-2$

Transferred value $-3 , 3, 0$

$C(x) = |3-3| + |-1+3| + ........ |-2+0| = 4$ which is minimum in this case

Note :

Only positive value can be transferred

It is not necessary to transfer whole value i.e partial transfer is also acceptable. This means that if you have $A[i] = 5$ then you can distribute the value 5 across many other array elements provided that they finally sum to a number less than equal to 5. For example 5 can be transferred in chunks of smaller values say 2 , 3 but their sum should not exceed 5.

Input:

First line contains N and K separated by space

Second line denotes an array of size N

Output

Minimum value of $C(X)$

Constraints

$1\le N,K \le 10^{5}$

$-10^{9}\le A_{i} \le 10^{9}$

SAMPLE INPUT
3 2
3 -1 -2

SAMPLE OUTPUT
0
Explanation

Array contains $3, -1 , -2$ and $K = 2$

if we transfer 1 from $1^{st}$ element to $2^{nd}$ and 2 from $1^{st}$ element to $3^{rd}$, the array becomes

Original Value $3, -1,-2$

Transferred value $-3 , +1, +2$

$C(x) = |3-3| + |-1+1| + |-2+2| = 0$ which is minimum in this case

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

National Instruments Intern Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming