# Problem Link:

# Difficulty:

Simple

# Pre-requisites:

None

# Problem:

Given a list of **N** integers **A[1], A[2], … A[N]**, and an integer **X**, find the minimum cost of making all elements non-negative. There are two kinds of operations that are allowed:

- Increase all elements in the array by 1. Cost of this operation is
**X**. - Choose an element and increase it by 1. Cost is 1.

# Short explanation:

It is clear that we will apply operation 2 only on negative array elements. Therefore, if there are **K** negative elements in the array, they can all be incremented by 1 at a total cost of **K**. In this way, operation 2 can simulate operation 1 at a *non-fixed cost* of **K**(=number of negative elements in current array). Therefore

- Let K = number of negative elements in current array
- If
**K ≥ X**apply operation 1. - else apply operation 2 on all negative entries once.
- repeat the above if there exists a negative entry.

Optimality of this strategy will be proved in next section.

# Long Explanation:

Consider the following *very naive* algorithm:

```
while(some A[i] is negative)
apply operation 1.
```

Lets try to simulate this algorithm for a small list of numbers:

A = {-4, -1, 0, -2, -3, -2}

and let X = 3

after successive steps, it becomes:

A = {-4, -1, 0, -2, -3, -2}, cost so far = 0

A = {-3, 0, 1, -1, -2, -1}, cost so far = 3

A = { -2, 1, 2, 0, -1, 0} , cost so far = 6

A = { -1, 2, 3, 1, 0, 1 } , cost so far = 9

A = { 0 , 3, 4, 2, 1, 2 } , cost so far = 12

As one can see, it makes sense to apply operation 1 initially, as we have lots of negative entries. The cost(3) paid for the first step makes perfect sense because the only alternative we had was to increase all the element by 1 by applying operation 2. That would cost us at least 5 units. Likewise, immediately after first step, A has 4(>X=3) negative entries so it again makes sense to apply operation 1. But after that(in step 3), there are only two negative entries, and we could have as well applied operation 2 twice(costing 2*1=2) at the third step as compared to operation 1.

The above example illustrates that we can

- Apply operation 1 as long as there are
**X**or more negative entries. - Apply operation 2 from there on to increase only the negative entries by one at a time.

In fact this algorithm is optimal and its proof of correctness follows shortly. However, we cant simulate the entire process because we may need to apply the operation 1 upto 10^{9} times(and operation 2 upto 10^{9} x 10^{5} times).

To find the total cost of the above, the following observation is handy:

When operation 1 is applied, the relative order of elements in the array do not change.

Therefore if the array A was sorted initially, it will be sorted after applying operation 1 any number of times. Hence operation 1 is applicable as long as **A[X]** is negative(so the number of negative elements is at least **X**). Operation 1 is applied a total of **op1** times costing **op1 * X** where

op1 = max(0, -A[x])

The total number of times operation 2 is applied is

max(-(A[1] + op1), 0) + max(-(A[2] + op1), 0) + … + max(-(A[X-1] + op1), 0)

## Proof of correctness

Consider an optimum strategy, and let it use operation 1 **op1** times, operation 2 is applied **n _{1} times** on

**a**

_{1}^{th}element,

**n**times on

_{2}**a**

_{2}^{th}element …

**n**times on

_{K}**a**

_{K}^{th}element, with n

_{1}, n

_{2}… n

_{K}> 0.

The total cost of these operations is **op1 * X + n _{1} + n_{2} + … + n_{K}**.

If **K ≥ X** then we could as well apply operation 1 one more time (total of op1+1 times) and apply operation 2 to all the elements one less time, which costs a total of

(op1+1) * X + n_{1}-1 + n_{2}-1 + … + n_{K}-1 = op1 * X + n_{1}+ n_{2}+ … + n_{K}+ X-K

Which is no more than original cost.

Therefore, If the array has **X** or more negative entries, we need to apply operation 1 at least once to this array. This is because otherwise operation 2 will be applied to all the negative elements leading to **K ≥ X**. Thus we have justified the first point about *Applying operation 1 if there are X or more negative entries.*

Justification of the second point is relatively easy because any application of operation 1 can be replaced by an application of operation 2 on **K(< X)** array elements, and in the process we reduce the total cost.

# Setter’s Solution:

Can be found here

# Tester’s Solution:

- Mahbub’s

```
(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester1/INTEG.cpp)
2. Sergey's
```

(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester2/INTEG.cpp)

# Editorialist’s Solution:

Can be found here