INTEG - Editorial

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

https://www.codechef.com/viewsolution/13694068

what is wrong with my solution?
khopri udd gaya

What is wrong with my code?CodeChef: Practical coding for everyone

test cases contain an array with at least one negative element. so, 0 as an answer is not possible.
this is my solution using prefix sum and sorting.
link text

All links to the solutions broken

1 Like

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

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]: CodeChef: Practical coding for everyone

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

Thanks here’s the [modified solution][1] but I’m still getting WA. I need the test case where it fails
[1]: CodeChef: Practical coding for everyone

did not handle x = 0 case

2 Likes

That solved the problem… Thanks!

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