ORDERS- Why my code is getting TLE Error

general
, ,
1

I solved the problem- ORDERS on codechef at https://www.codechef.com/problems/ORDERS/

I tried a lot but always getting TLE Error for my code. I saw another successfully submitted code which was made by using almost the same approach as used by me.

Can someone please, tell me, why my code gives TLE error and the other code does not.

My Code:

#include <stdio.h>
int main(void)
{
int h,i,j,k,t,n,tmp,tmp1;

scanf("%d",&t);
for(i=0;i<t;i++)
{
    scanf("%d",&n);
    int b[n+1],c[n+1];
    for(j=1;j<=n;j++)
    {   
        scanf("%d",&tmp);
        b[j]=c[j]=j;
        for(h=1,k=j;h<=tmp;k--,h++)
        {
           tmp1 = b[k-1];
            b[k-1]=b[k];
            b[k]=tmp1;
        }
    }
    for(j=1;j<=n;j++)
        c[b[j]]=j;
    for(k=1;k<=n;k++)
        printf("%d ",c[k]);
printf("\n");
 }
return 0; 
}

The other code, which was in successful submissions:

#include <stdio.h>

int main(void)
{
 int i, j, k, l, tc, ns;
 scanf("%d\n", &tc);
 for (i = 0; i < tc; i++)
 {
	scanf("%d\n", &ns);
	int nos[ns];
	for (j = 0; j < ns; j++)
	{
		scanf("%d", &nos[j]);
	}
	int ar[ns];
	for (k = 0; k < ns; k++)
	{
		ar[k] = k + 1;
	}
	for (l = 1; l < ns; l++)
	{
		int tmp = ar[l];
		int m;
		for (m = l; m > l - nos[l]; m--)
		{
			ar[m] = ar[m - 1]; 
		}
		ar[l - nos[l]] = tmp;
	}
	int kal[ns + 1];
	int p;
	for (p = 0; p < ns; p++)
	{
	    kal[ar[p]] = p + 1;
	}
	int n;
	for (n = 1; n < ns + 1; n++)
	{
		printf("%d ", kal[n]);
	}
	printf("\n");
}
return 0;
}

Thanks. :slight_smile:

2

It’s all about complexity in both the codes… As i can see that your complexity in worst case goes upto O(T * N * temp) That is very slow to be acceptable in a given time limit…

Next solution is optimized solution where inner most loop have a beautiful modification as you can, my advice is to optimized your whole solution according to AC solution…

And sorry i will not give the full solution, otherwise this question would be worthless for you…

3

Hey @tussank, the swaps you are performing-

tmp1 = b[k-1];
b[k-1]=b[k];
b[k]=tmp1;

affect the performance of your code enough to give TLE. Think about it, just b[k]=b[k-1] is sufficient, as long as you put j into the last gap created after tmp shifts. I have made this slight modification and it gives AC, see here.
By the way, this procedure is called insertion sort, go ahead and look it up if you don’t know about it already. Hope this helps :slight_smile:

1 Like
4

Thank You Very Much, I got it.

5

Thank You Very Much, I got it.