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;}
you have to put your code someplace we could read it, for example to http://pastebin.com
the above code is pasted in pastebin.com as trip.c by JASKARAN_1.
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 - aObLPD - Online C++ Compiler & Debugging Tool - Ideone.com 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 
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?
can you give the link? I can’t find it.