INTEG - Editorial

Yup!

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

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

1 Like

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

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

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

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.

1 Like

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

}

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

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.

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.

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

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
  • 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

//