TLE in eko

[beauty]

Plz.. help
question : www.spoj.pl/problems/EKO/
Logic : a[0] a[1] a[2] a[3] a[4] SUM min
Step1 4 42 40 26 46 158 4
Step2 0 38 36 22 42 138 22
Step3 0 16 14 0 20 50 14
Step4 0 2 0 0 6 8
thus , ans=sum of all SUM except last one + ......

#include<stdio.h>
#include<limits.h>
long long findmin(long long a[],long size)
{
     long long min=INT_MAX;
     long i;
     for(i=0;i<size ;i++)
        if(min>a[i] && a[i])
            min=a[i];
     return min;
} 
int main()
{   
    long i,n=0,m=0;int c;
    scanf("%ld %ld",&n,&m);  
    long long a[n],b[n],sum=0L,min,summin=0L;
    for(i=0;i<n;i++){
        scanf("%lld",a[i]);
        sum=sum+a[i];b[i]=a[i];
    }
    while(sum>m)
    {
        min=findmin(a,n);
        for(i=0;i<n ;i++)
        {
            b[i]=a[i];
            if(a[i]) {
                a[i]-=min;
                sum=sum-min;
            }
        }
        summin+=min;
    }
    if(sum<m)
    {   long nonzero=0;
        for(i=0;i<n;i++)
            if(b[i]) nonzero++;     
        summin=summin-(m-sum)/nonzero;
        if((m-sum)%nonzero)   summin-=1;
    }
    printf("%lld\n",summin);
    return 0;
}

[leppyr64]

Do you understand why you get TLE? Do you understand what the worst case complexity of your algorithm is?

[beauty]

No , I dont know why i'm getting TLE . I think the complexity of my approach is quite ok . Shall I use some other algo ??

[leppyr64]

What is e complexity of findmin? In the worst case, how many times will it be called?

[beauty]

Complexity of findmin is O(n) . Ok , got it . Worst case complexity is O(n^2) .
Can you suggest any other algo ? any hint ...

[leppyr64]

I haven't solved it myself, but if you could find a way tha findmin could be executed in O(1) that would help greatly.

[beauty]

findmin is just finding the minimum value . I think we've to traverse the whole array . So , complexity cant be less than O(n) . Or maybe , we could first sort the array using mergesort(O(nlogn)) . and then calculate the summin . I'll try .

[leppyr64]

Exactly Good luck. Not certain that will be fast enough but it's much better than what you had before.

[beauty]

I have tried new method using merge sort . Its complexity is O(n)+O(nlogn)

But it gives runtime error in 9th test case . What should i do

#include<stdio.h>
void merge(long long a[], long long low, long long high, long long mid);
int mergesort(long long a[], long long low,long long high)
{
long long mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
return(0);
}
void merge(long long a[], long long low, long long high, long long mid)
{
long long i, j, k, c[200000];
i=low;
j=mid+1;
k=low;
while((i<=mid)&&(j<=high))
{
if(a[i]<a[j])
{
c[k]=a[i];
k++;
i++;
}
else
{
c[k]=a[j];
k++;
j++;
}
}
while(i<=mid)
{
c[k]=a[i];
k++;
i++;
}
while(j<=high)
{
c[k]=a[j];
k++;
j++;
}
for(i=low;i<k;i++)
{
a[i]=c[i];
}
}
int main()
{   
    long long i,j=0,n=0,m=0,min,sum=0L;
    scanf("%lld %lld",&n,&m);
    long long a[n],b[n];
    for(i=0;i<n;i++){
        scanf("%lld",&a[i]);
        sum+=a[i];
    }
    mergesort(a,0,n-1);
    long long sub=0L;
    for(i=0;i<n;i++)
    {
        min=a[i]-sub;
        if((sum-(n-i)*min)>m)
             sub=a[i];
        if((sum-(n-i)*min)==m)
        {    sub=a[i];
             break;
        }
        if((sum-(n-i)*min)<m)
        {    sub+=(sum-m)/(n-i);
             break;
        }
        a[i]-=sub;
        sum-=(n-i)*min;
    }
    printf("%lld\n",sub);
    return 0;
}

[leppyr64]

What kind of runtime error?

I notice you're allocating memory for arrays often. Declare them once and large enough for all test cases. This will save a lot of time.

[beauty]

I've tried to allocate the maximum of array size .
for long long , array size cannot be greater than 200000 on my machine else it gives segmentation fault .
and for long , array size cannot be greater than 520929 .
I've tried both . but still giving runtime error SIGSEGV .

[leppyr64]

Declare them globally.

[beauty]

still showing same error
????