Practice

Contest

Simple

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:

1. Increase all elements in the array by 1. Cost of this operation is X.
2. 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

1. Apply operation 1 as long as there are X or more negative entries.
2. 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 109 times(and operation 2 upto 109 x 105 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 n1 times on a1th element, n2 times on a2th element … nK times on aKth element, with n1, n2 … nK > 0.

The total cost of these operations is op1 * X + n1 + n2 + … + nK.

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 + n1-1 + n2-1 + … + nK-1 = op1 * X + n1 + n2 + … + nK + 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:

1. Mahbub’s
``````
2. Sergey's

``````

# Editorialist’s Solution:

Can be found here

1 Like

All links to the solutions broken

1 Like

I tried to solve this problem in this way… plz tell me where I’m going wrong

1. push all negative number in a vector and while pushing I changed the sign and take sum of all element

(sum += v[i])

1. if cost == 0 print 0

2. if ( cost >= vector.size() ) print sum

3. else sort( v.begin(), v.end() )

and at last

``````
long long int negative = 0;
long long int temp = v[v.size()-cost] * cost
for( long long int i = cost ; i < v.size(); i++) {
negative = negative + v[i] - v[cost-1];
}
negative = negative + temp;
printf("%lld",  negative);

``````

I still couldn’t figure out why it is still not a correct solution

Change the statement :-
long long int temp = v[v.size()-cost] * cost
to
long long int temp = v[cost-1] * cost, then it will be AC…)

2 Likes

I implemented the solution in the following way. I am able to get the correct answer in my machine

#include
#include<stdio.h>
#include
#include

using namespace std;

std::vector a;
unsigned long int allArrayCost;

long int MinCost(unsigned long int n)
{
unsigned long int minCost = 0;
unsigned long int count = 0;

``````/* count the number of negatives */
while(1)
{
count = 0;
for(unsigned long int i=0; i<n; i++)
{
if(a[i] < 0)
count++;
else
break;
}

if(count == 0) break;

if(count > allArrayCost)
{

unsigned long int incFactor = abs(a[allArrayCost]) ;
for(unsigned long int i=0; i<n; i++)
a[i] += incFactor;
minCost += incFactor * allArrayCost;
}
else
{
/* sum up all negatives */
for(unsigned long int i=0; i<n; i++)
if(a[i] < 0)
minCost += abs(a[i]);
else
break;
return minCost;
}
}
return minCost;
``````

}

int main()
{
unsigned long int n;
long int myint;

``````cin>>n;
for(unsigned long int i=0; i<n; i++)
{
cin>>myint;
a.push_back(myint);
}
cin>>allArrayCost;

sort(a.begin(),a.end());

cout<<MinCost(n)<<endl;
return 0;
``````

}

1.Consider only negative numbers and put them in a list as positive//goal is to reduce them to zero.
//after each iteration remove any zero element.

2.As long as list.size is more than X apply operation X.

else it makes sense to apply only add 1 forever since X will be more expensive here is main section of my
code.

private static void solve(){
//cumulate is the cumulative cost.

``````  //cost is X,the data is in PQ
int k=0;

while(cost<PQ.size()){

int a = PQ.poll();

a-=k;

BigInteger aa = new BigInteger(String.valueOf((a*(PQ.size()+1))));

sum = sum.subtract(aa);

BigInteger c = new BigInteger(String.valueOf(cost*a));

k+=a;
}

//PQ.clear();

}``````

The problem has been defined in this manner…correct?

• Step 1. Let K = number of negative elements in current array.
• Step 2. If K ≤ X apply operation 1.
• Step 3. else apply operation 2 on all negative entries once.
• Step 4. repeat the above if there exists a negative entry.

Why is there only one condition check in step 2? I mean if we have 3 numbers in the array :- -1, -2, -3
And the value of X input by the user is = 100

Now, K= 3 and X=100;

And K<=X

According to the described algorithm we should apply operation 1…but this will result in a higher cost, whereas the minimum cost is still 6.

Sorry, that was a typo. it should be K ≥ X. Corrected. Thanks for pointing out.

for which test case does my [solution][1] fail?
[1]: http://www.codechef.com/viewsolution/2684663

You need to store answer in long long as it can exceed limits of int

Can anyone help me with my code?? i’m getting an nzec here

``````import java.io.*;
import java.util.*;

public class Integ {
public static void main (String[] args) throws Exception {

long[] array = new long[n];
for(int i=0;i<n;++i)
array[i]=Long.parseLong(numbers[i]);

Arrays.sort(array);

int nneg=0;
long op1times=0, op2times=0;

for(int i=0;i<n;++i)
nneg++;

if(x<nneg)
op1times = Math.max(0, -array[(int)x-1]);

for(int i=0;i<n;++i)
op2times+= Math.max(0, -(array[i]+op1times));

System.out.println(op1times*x+op2times);
}
}``````

Thanks here’s the [modified solution][1] but I’m still getting WA. I need the test case where it fails
[1]: http://www.codechef.com/viewsolution/2684891

did not handle x = 0 case

2 Likes

That solved the problem… Thanks!

This was one of the most interesting problem I found in the contest … After I worked out this problem using Pen & Paper , I found an interesting solution to this problem…

Let X = COST OF THE FIRST TYPE OPERATION

STEP 1 : While taking Input to the Array …IGNORE THE +ve INTEGERS & IF THE INTEGER IS NEGATIVE , MAKE IT POSITIVE AND INSERT IT INTO THE ARRAY…

STEP 2 : if(Array length obtained from step(1) <= X) , PRINT THE SUM OF THE ARRAY ELEMENTS and EXIT…

STEP 3 : else , SORT THE ARRAY AND PRINT THE SUM OF THE LAST Xth ELEMENTS and EXIT…

This was all that was needed to solve this problem …

Link to my solution : http://www.codechef.com/viewsolution/2637235

10 Likes

Looks like `abs` in C works only for 32 bit numbers.

``````
if(x >= count_negetive)
return abs(sum_negetive);

``````

was the curlprit. Changing it gets AC

1 Like

Thank you so much for your help @utkarsh_lath

really a neat approach…

1 Like

Yup!.. There is a nice logic behind STEP 3…

Hey!

I did the same thing, i.e. Adding Magnitude of X greatest elements. I am getting TLE for the following code. Could somebody please help me in tracking the bug?

``````//INTEG SEP LONG 13

import java.util.Arrays;

public class Main{

public static void main (String[] args) throws java.lang.Exception{

int n = Integer.parseInt(input);
long[] arr = new long[n];
for(int i = 0; i<n;i++){
arr[i] = Long.parseLong(input.split(" ")[i]);
}

long cost = 0;
if(n<X){
for( int i = 0;i<n;i++){
cost+=arr[i];         // sum of all the elements
}
}
else{

Arrays.sort(arr);

for( int i = 0;i<X;i++){
cost+=arr[i];         // sum of X biggest elements
}
}
System.out.println(-1*cost);
}
}``````
//