INTEG - Editorial

mangatmodi · September 20, 2013, 2:45pm

Yup!

I did the same thing. However I am getting TLE for such a simple code. Might be JAVA

betlista · September 20, 2013, 4:32pm

Why are you doing input.split(" ") in for loop?

rsaha77 · September 20, 2013, 5:27pm

JAVA cannot be the problem for the TLE , if you are applying the same approach as described above…

I tried the same approach using JAVA couple of days back…And it was AC well within the time limit… …

See this : http://www.codechef.com/viewsolution/2687909

There might be some other problem for the TLE…!!

mangatmodi · September 20, 2013, 10:53pm

Oops! That was so stupid and careless of me. I don’t have much experience with JAVA. I did changed that particular code to

    String[] temp = input.split(" ");
    for(int i = 0; i<n;i++){
        arr[i] = Long.parseLong(temp[i]);
    }

Now solution is accepted with a nice time of 0.84. Thank you for the help.

agarwal95 · September 22, 2013, 3:56pm

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;

}

rahulbawa1991 · September 23, 2013, 5:41pm

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

}

rsaha77 · September 23, 2013, 6:59pm

Explanation to the 3rd STEP : http://discuss.codechef.com/questions/24406/integ-user-rsaha-solution-to-this-problem …

suganoo · September 29, 2013, 9:03pm

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

}

}

ag0965 · May 18, 2014, 3:45pm

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;

}

eddy007 · August 29, 2015, 1:24am

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.

eddy007 · August 29, 2015, 1:26am

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.

ceilks · August 29, 2015, 2:56am

Yes you’re wrong. The optimal number is 9, since you can increment two elements for 2 in the third step.

Don’get confused by the example in the editorial. It’s purpose is to demonstrate that always using operation 2 doesn’t yield an optimal result

paavini · July 24, 2016, 8:44pm

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

akki9 · December 25, 2016, 5:24pm

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

albert_012 · May 21, 2017, 4:50pm

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