TLE in trip

general
, ,
1

Could somebody please tell me why am I getting TLE in the trip problem
Could anyone please tell me why am I getting a TLE in my code:

include stdio.h

include stdlib.h

inline int next_int() {

int n = 0;

char c = getchar();

while (!(‘0’ <= c && c <= ‘9’)) {

c = getchar(); } while (‘0’ <= c && c <= ‘9’) {

n = n * 10 + c - ‘0’;

c = getchar();

}

return n;

} int main() { int m,n,i;

n=next_int();

m=next_int();

int a=(int )malloc(n *sizeof(int));

int ways=(int )malloc(n *sizeof(int));

int ans=(int )malloc(n *sizeof(int));

for(i=0;i<n;i++)

*(a+i)=next_int();

for(i=0;i<n;i++)

*(ans+i)=n;

ans[0]=0;

ways[0]=1;

i=0;//i points to the current location

int j=i+1;//j points to the location just after i

while(i<=n-1) {

while(a[j]-a[i]<=m)

{if(ans[j]==ans[i]+1)

ways[j]++;

else if(ans[i]+1<ans[j]) {ans[j]=ans[i]+1;

ways[j]=ways[i];}

j++;

}

i++;

j=i+1;

}

printf("%d %dn",ans[n-1]-1,ways[n-1]%1000000007);

return 0;}

2

you have to put your code someplace we could read it, for example to http://pastebin.com

3

the above code is pasted in pastebin.com as trip.c by JASKARAN_1.

4

can you give the link? I can’t find it.

5

http://www.codechef.com/viewsolution/1637494

6

If you want to test your code to find where is TLE problem, you have to generate some big input.

I tried your algorithm on ideone with 15s timelimit - http://ideone.com/aObLPD and I got TLE.

Input is generated by this C++ code:

#include <cstdio>

int main() {
	printf( "100000 1000\n");
	for ( int i = 0; i < 100*1000; ++i ) {
		printf( "%d\n", i );
	}
	return 0;
}

You can try it on your PC :wink:

7

I don’t know how you got the TLE for 15s limit.I took the output from your code and wrote it in a file and made my program read the input file just like codechef does.It takes less than a second.
Could anybody please explain me the editorial solution or help me out with my solution.I’m not able to understand how to calculate the number of ways?