INTEG - Editorial

Problem Link:

Practice

Contest

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:

  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

(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

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 :frowning:

I implemented the solution in the following way. I am able to get the correct answer in my machine
But i still dont know where i am wrong…please help

#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;

}

Please can any body please help explain why i got WA. My procedure is thus

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));
        
        cumulate = cumulate.add(c);
        
        k+=a;
    }
    
    cumulate = cumulate.add(sum);
    //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.

Please explain this to me.

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 {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());

        long[] array = new long[n];
        String[] numbers = in.readLine().split(" ");
        for(int i=0;i<n;++i)
            array[i]=Long.parseLong(numbers[i]);
        
        long x = Long.parseLong(in.readLine());
                
        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);     	
        }
}

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… :slight_smile:

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 … :stuck_out_tongue:

Link to my solution : CodeChef: Practical coding for everyone

10 Likes

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.io.BufferedReader;
import java.util.Arrays;


public class Main{

    public static void main (String[] args) throws java.lang.Exception{
    BufferedReader r = new BufferedReader (new java.io.InputStreamReader (System.in));

        String input = r.readLine();
        int n = Integer.parseInt(input);
        long[] arr = new long[n];
        input = r.readLine();
        for(int i = 0; i<n;i++){
              arr[i] = Long.parseLong(input.split(" ")[i]);
        }
        
        int X = Integer.parseInt(r.readLine());
        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);
  }
}

Where could i have possibly gone wrong?? o.O

int main(){
long long array[100],correction,cost,size,i,j=0,temp=0,minimum,maximum,sum=0;

cin>>size;
for(i=0;i<size;i++)
  if(cin>>temp && temp<0)
    array[j++]=temp;	
cin>>cost;
size=j;
i=1;
sort(array,array+size);
minimum=array[size-1];
maximum=array[0];
temp=0;
if((size-i)>=cost)
{
  while(maximum<-1*cost)
  {
	sum-=minimum*cost;
	maximum-=minimum;
	temp+=minimum;
	array[size- ++i]-=temp;
	minimum=array[size- i];
  }
  for(j=0;j<size-i;j++)
    sum-=array[j];
  correction=maximum-array[0];
  cout<<correction<<endl;
  sum-=correction*((size>i)?(size-i):(i-size));
  if(maximum==array[0])
    sum+=1;
}
else
for(j=0;j<size;j++)
    sum-=array[j];
cout<<endl<<sum;
return 0;

}

Can anyone help me , I am getting a TLE

import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class ChefInt {

private static int costOp1;
private static int[] nums;
private static int sum;

public static void main(String[] args) {
    
        Scanner reader = new Scanner((System.in));
        PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));
        int n = reader.nextInt();
        nums = new int[n];
        for (int i = 0; i < n; i++) {
            int temp = Integer.parseInt(reader.next());
            if (temp < 0) {
                nums[i] = temp;
            }
        }
        costOp1 = reader.nextInt();
        int negativeElements = 0;
        boolean flag = false;
        while ((negativeElements = getNegativeElements(nums)) != 0) {

            switch (getBestOperation(negativeElements)) {
                case 1:

                    for (int i = 0; i < nums.length; i++) {
                        if (nums[i] < 0) {
                            sum += (-nums[i]);
                            flag = true;
                        }
                    }

                    break;
                case 2:
                    for (int i = 0; i < nums.length; i++) {
                        nums[i] += 1;
                    }
                    sum += costOp1;
                    break;
                default:

                    break;
            }
            if (flag) {
                writer.println(sum);
                writer.close();
                break;
            }
        }
        if (negativeElements == 0) {
            flag = true;
            writer.println(sum);
            writer.close();
        }
        reader.close();
    } 


private static int getBestOperation(int negativeElements) {
    if (1 * negativeElements >= costOp1) {
        return 2;
    } else {
        return 1;
    }

}

private static int getNegativeElements(int[] nums) {
    int ctr = 0;
    for (int i = 0; i < nums.length; i++) {
        int j = nums[i];
        if (j < 0) {
            ctr++;
        }
    }
    return ctr;
}

}

Cold you anyone help me? why do i have wrong answer??? (?o?;;)/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

/**
 * @param args
 * @throws IOException 
 * @throws NumberFormatException 
 */
public static void main(String[] args) throws IOException {
	// TODO 自動生成されたメソッド・スタブ
	BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	int num = Integer.valueOf(input.readLine());
	String str1 = input.readLine();
	String[] str2 = str1.split(" ");
	ArrayList<Integer> test = new ArrayList<Integer>();

	for (int i = 0 ; i < num ; i++ ){
		test.add(Integer.valueOf(str2[i]));
	}
	int cost = Integer.valueOf(input.readLine());

	Collections.sort(test);

	int sum = 0 ;
	int bar = 0;
	if ( 0 < cost ) {
		if (cost <= num){
			if ( test.get( cost - 1 ) < 0){
				bar = ( - test.get(cost - 1) );
				sum += ( - test.get(cost - 1) ) * cost;
			}
		}
		for (int i = 0 ; i < Math.min(cost,num) ; i++ ){
			if ( test.get(i) < 0 ){
				sum += ( - test.get(i) ) - bar;
			}
		}
	}
	System.out.println(sum);

}

}

why my code is not working please help…
flag is for counting negative number

#include <stdio.h>
int main(void) {
long long i,t,x,flag=0,cost=0,j;
scanf("%lld",&t);
long long int p[t];
for(i=0;i<t;i++){
    scanf("%lld",&p[i]);
	if(p[i]<0){
		flag++;
	}
}
scanf("%lld",&x);
while(flag>1){
	flag=0;
	cost=cost+x;
	for(i=0;i<t;i++){
		p[i]++;
		if(p[i]<0){
		flag++;
	}
}
}
if(flag==1){
	for(i=0;i<t;i++){
		if(p[i]<0){
			j=i;
			break;
		}
	}
	cost=cost-p[j];
}
printf("%lld",cost);
// your code goes here
return 0;

}

For this test case -4, -1, 0, -2, -3, -2 and X = 3, shouldn’t the ans be 10??

let’s sort the array in descending order

0 -1 -2 -2 -3 -4

Apply coins

1 0 -1 -1 -2 -3 - 3 coins

2 1 0 0 -1 -2 - 3 coins

3 2 1 1 0 -1 - 3 coins

3 2 1 1 0 0 - 1 coin

Total number of coins are 10 which is optimal. Please correct me if my understanding is wrong.

could not find any case which gives WA for my solution … please someone give the wrong test case!!

#include<stdio.h>
#include
using namespace std;

int partition(long long *arr, const int left, const int right) {
const int mid = left + (right - left) / 2;
const int pivot = arr[mid];
// move the mid point value to the front.
swap(arr[mid],arr);
int i = left + 1;
int j = right;
while (i <= j) {
while(i <= j && arr[i] <= pivot) {
i++;
}

    while(i <= j && arr[j] > pivot) {
        j--;
    }

    if (i < j) {
        std::swap(arr[i], arr[j]);
    }
}
swap(arr[i - 1],arr);
return i - 1;

}

void quicksort(long long *arr, const int left, const int right, const int sz){

if (left >= right) {
    return;
}


int part = partition(arr, left, right);
//std::cout << "QSC:" << left << "," << right << " part=" << part << "\n";
//print (arr, sz);

quicksort(arr, left, part - 1, sz);
quicksort(arr, part + 1, right, sz);

}

int main(){
int n;
cin>>n;
long long a[100005],temp,x,sum;
long long d=0;
for(int i=0;i<n;i++){
cin>>temp;
if(temp<0){
a[d]=temp*(-1);
d++;
sum+=a[d];
}
}
d++;
cin>>x;
if(x<=d){
long long diff=d-x;
sum=0;
quicksort(a,0,d-1,d);
sum=sum+a[diff]*x;
//cout<<a[diff]*x<<endl;
for(int i=diff+1;i<d;i++){
sum+=a[i]-a[diff];
//cout<<a[i]-a[diff]<<endl;
}
cout<<sum;
}
else{
cout<<sum;
}

return 0;
}

how you get the 12 answer in this sample input after last operation pay 1 coin get total cost 10, according to the questions

  • List item
  • #include<stdio.h>
    #include<stdlib.h>
    long long int sum=0;
    int count(int a[],int x,int n)
    {
    long long int i,k=0;
    for(i=0;i<n;i++)
    {
    if(a[i]<0) k++;
    }
    if(x<=k)
    {
    for(i=0;i<n;i++)
    {
    a[i]=a[i]+1;
    }
    sum = sum + x;
    count(a,x,n);
    }
    else if(x>k)
    {
    for(i=0;i<n;i++)
    {
    if(a[i]<0)
    {
    sum = sum + abs(a[i]);
    }
    }
    //printf("%d “,sum);
    }
    return sum;
    }
    int main()
    {
    int n,i,x,a[10005];
    scanf(”%d",&n);
    for(i=0;i<n;i++)
    {
    scanf("%d",&a[i]);
    }
    scanf("%d",&x);
    if(x!=0)
    {
    sum = count(a,x,n);
    printf("%d",sum);
    }
    else if(x==0)
    printf("%d",0);
    return 0;
    }

why this code is giving run time error

enter code here
#include<stdio.h>
#include<stdlib.h>
long long int sum=0;
int count(int a[],int x,int n)
{
long long int i,k=0;
for(i=0;i<n;i++)
{
if(a[i]<0) k++;
}
if(x<=k)
{
for(i=0;i<n;i++)
{
a[i]=a[i]+1;
}
sum = sum + x;
count(a,x,n);
}
else if(x>k)
{
for(i=0;i<n;i++)
{
if(a[i]<0)
{
sum = sum + abs(a[i]);
}
}
//printf("%d “,sum);
}
return sum;
}
int main()
{
int n,i,x,a[10005];
scanf(”%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&x);
if(x!=0)
{
sum = count(a,x,n);
printf("%d",sum);
}
else if(x==0)
printf("%d",0);
return 0;
}

why this code is giving run time error

Heading

#include<stdio.h>
#include<stdlib.h>
long long int sum=0;
int count(int a[],int x,int n)
{
long long int i,k=0;
for(i=0;i<n;i++)
{
if(a[i]<0) k++;
}
if(x<=k)
{
for(i=0;i<n;i++)
{
a[i]=a[i]+1;
}
sum = sum + x;
count(a,x,n);
}
else if(x>k)
{
for(i=0;i<n;i++)
{
if(a[i]<0)
{
sum = sum + abs(a[i]);
}
}
//printf("%d “,sum);
}
return sum;
}
int main()
{
int n,i,x,a[10005];
scanf(”%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&x);
if(x!=0)
{
sum = count(a,x,n);
printf("%d",sum);
}
else if(x==0)
printf("%d",0);
return 0;
}

why this code is giving run time error


#include<stdio.h>
#include<stdlib.h>
long long int sum=0;
int count(int a[],int x,int n)
{
long long int i,k=0;
for(i=0;i<n;i++)
{
if(a[i]<0) k++;
}
if(x<=k)
{
for(i=0;i<n;i++)
{
a[i]=a[i]+1;
}
sum = sum + x;
count(a,x,n);
}
else if(x>k)
{
for(i=0;i<n;i++)
{
if(a[i]<0)
{
sum = sum + abs(a[i]);
}
}
//printf("%d “,sum);
}
return sum;
}
int main()
{
int n,i,x,a[10005];
scanf(”%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&x);
if(x!=0)
{
sum = count(a,x,n);
printf("%d",sum);
}
else if(x==0)
printf("%d",0);
return 0;
}

why this code is giving run time error

  1. List item
  2. #include<stdio.h>
    #include<stdlib.h>
    long long int sum=0;
    int count(int a[],int x,int n)
    {
    long long int i,k=0;
    for(i=0;i<n;i++)
    {
    if(a[i]<0) k++;
    }
    if(x<=k)
    {
    for(i=0;i<n;i++)
    {
    a[i]=a[i]+1;
    }
    sum = sum + x;
    count(a,x,n);
    }
    else if(x>k)
    {
    for(i=0;i<n;i++)
    {
    if(a[i]<0)
    {
    sum = sum + abs(a[i]);
    }
    }
    //printf("%d “,sum);
    }
    return sum;
    }
    int main()
    {
    int n,i,x,a[10005];
    scanf(”%d",&n);
    for(i=0;i<n;i++)
    {
    scanf("%d",&a[i]);
    }
    scanf("%d",&x);
    if(x!=0)
    {
    sum = count(a,x,n);
    printf("%d",sum);
    }
    else if(x==0)
    printf("%d",0);
    return 0;
    }

why this code is giving run time error

1 Like