DEVUGRAP TLE error

Can someone pls help? What am I doing wrong?http://www.codechef.com/viewsolution/7055464
Here’s the code Home » May Lunchtime 2015 » Devu and Grapes » All Submissions » Saptarshi [7055464]

Average:
Poor
Okay
Good
Great
Awesome
No votes yet
Problem Title:
Devu and Grapes
CodeChef submission 7055464 (C++ 4.9.2) plaintext list. Status: TLE, problem DEVUGRAP, contest LTIME24. By tataisap (tataisap), 2015-05-31 13:15:25.
#include
#include
using namespace std;

unsigned long i,j,n,k,l,t,count,gcd,arr[100001],arr1[50001],arr2[50001];
void merge(unsigned long arr[100001],unsigned long p,unsigned long q, unsigned long r){

for(i=1;i<=(q-p+1);++i){
	arr1[i]=arr[p+i-1];
}arr1[i]=INT_MAX;

for(i=1;i<=(r-q);++i){
	arr2[i]=arr[q+i];
}arr2[i]=INT_MAX;

for(i=p,j=1,l=1;i<=r;++i){
	if(arr1[j]<=arr2[l]){
		arr[i]=arr1[j];
		j++;
	}
	else{
		arr[i]=arr2[l];
		l++;
	}
}
	
return;

}

void msort(unsigned long arr[100001], unsigned long m, unsigned long n){

int o;
if(m<n){
	o=(m+n)/2;
	msort(arr,m,o);
	msort(arr,o+1,n);
	merge(arr,m,o,n);
}

return;

}

int main()
{
scanf("%lu",&t);
while(t–){
scanf("%lu%lu",&n,&k);
for(i=1;i<=n;++i){
scanf("%lu",&arr[i]);
}
msort(arr,1,n);
/for(i=1;i<=n;++i)
printf("%lu ",arr[i]);
/
count=0;
for(gcd=k;arr[1]-gcd>k;gcd+=k);
count+=arr[1]-gcd;
//printf("\n%lu",gcd);
for(i=2;i<=n;++i){
for(j=gcd;arr[i]-j>gcd;j+=gcd);
if((arr[i]-j)>(j+gcd-arr[i])){
count+=-arr[i]+j+gcd;
}
else
count+=arr[i]-j;
}
printf("%lu\n",count);
}

return 0;

}

Thaking you in anticipation.

your sol is not yet public
copy paste the code here

I think that for each test case you are calling merge sort which is of O(nlogn). I think you should avoid that and I am not able to get your logic.
It has to be a O(n) solution .You can have a look at my code

1 Like
//