SPOJ AMR10G getting WA. Any specific test cases?

#include<stdio.h>
int main()
{
int n,k,T,i,x,x1,p,y;
long long int arr1[2000],arr2[2000],min,t;
scanf("%d",&T);
for(x=0;x<T;x++)
{
i=0;
scanf("%d%d",&n,&k);
for(x1=0;x1<n;x1++)
scanf("%lld",&arr1[x1]);

     //sort
   for(x1=0;x1<n;x1++)
   {
      p=x1;
      for(y=x1+1;y<n;y++)
      {
      if(arr1[y]<arr1[p])
      p=y;
      }
     t=arr1[x1];
     arr1[x1]=arr1[p];
     arr1[p]=t;
   }

     t=0;
     while((i+k-1)<n){

     arr2[i]=arr1[i+k-1]-arr1[i];

     t++;
     i++;
     }

 min=arr2[0];
   for(x1=0;x1<t;x1++)
   {
   if(arr2[x1]<min)
   min=arr2[x1];
   }
printf("%lld\n",min);
}
return 0;
}

look at the constraints…

1 <= K <= N <= 20000 

u are taking 2000…pls correct that and use a faster method to sort…bubble,insertion sort may give TLE…hope this helps…:slight_smile:

this is your corrected code…:slight_smile:

2 Likes

There are several problems with your code.

  • Constraints

    1 <= K <= N <= 20000

    1 <= height <= 1000000000

    Since value of height easily fits in 32 bit integer, there is no need to use long long int.

  • Sorting Method

    Simple sorting methods like insertion, bubble have time complexity of O(N*2). Since value N can be upto 20000, these sorting methods are not feasible. You can use O(Nlog(N))complexity methods such as quicksort or a mergesort (these two are simple as compared to others).
    Or if you are familiar with C++ STL functions then you can use STL sort function. You can find it here.

Hope it helps, Best Luck :slight_smile:

2 Likes

thank you. It works now on C++ 4.7.2