runtime error(sigsegv) in trip

general
1

I tried to solve the easy practice problem “TRIP” using recursion but I encountered a runtime error(sigsegv). Here is my code.

#include <stdio.h>
#include <stdlib.h>
int counter=0,minimum=0,sp=0,n=0,m=0,counter2=0,counter3=0,a[1000001];

int main()

{

int sp=0,i=0;
scanf("%d",&n);
counter2=n-2;
scanf("%d",&m);
for(i=0;i<n;i++)
{
    scanf("%d",&a[i]);
}
shortestpath(0);
counter2=counter2%1000000007;
counter=counter%1000000007;
printf("%d %d\n",counter2,counter);
return 0;

}

void shortestpath(int b)
{

int i=0;
for(i=b+1;i<n;i++)
{
    if(a[i]-a[b]<=m)
    {
        counter3=0;
        sp++;
        minimum=sp;
        shortestpath(i);
    }
}
counter3++;
if(counter3==1)
{
    minimum=minimum-1;
    if(minimum<counter2)
    {
        counter=0;
        counter2=minimum;
        counter++;
    }
    else if(minimum==counter2)
    {
        counter++;
    }
}
sp--;

}

2

Hi.

I think you are a beginner and you don’t know what complexity is.
Your algorithm works in : O(n!), and for n > 11 it’s too slow.
You should have TLE, but you got RE, because recursion stack overflew.
If you don’t know what is recursion stack read this.
Be kind and use pastebin.com next time, or just learn how to format code on codechef forum :slight_smile:

3

Okay, thank you.