Time Limit Exceeded TLE

I made 2 programs for the problem ORDERS ( http://www.codechef.com/problems/ORDERS/ )

Both gave TLE!!!

can you give me some suggestion to improve any of these to make it work…if not just tell me what to do next…

PROGRAM 1: http://www.filedropper.com/orders2

#include<stdio.h>

int main(void)
{  
	int n,i;
	int data[200001];
	int num,j,k;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d",&num);
		for(j=0;j<num;j++)
		{
			scanf("%d",&data[j]);
			for(k=data[j];k>0;k--)
				++data[j-k];
			data[j]=j+1-data[j];


		}
		for(j=0;j<num;j++)
		{
			printf("%d ",data[j]);
		}     
		printf("\n");  
	}      

	return 0;
}

PROGRAM 2: http://www.filedropper.com/order3

#include<stdio.h>
#include<stdlib.h>
typedef struct soldier {
		int place;
		int step;
		int index;
		struct soldier *next;
		}sol;
	int rank[200000];
void write_rank(struct soldier * start,int rank);
struct soldier * read(int inde,struct soldier * last);
int main()
{
	struct soldier *start,*last;
	int cas,no,i;

	scanf("%d",&cas);
	while(cas--)
	{
			   scanf("%d",&no);
			   start=(sol*)malloc(sizeof(sol));
			   start->place=0;start->step=0;start->index=0;
			   last=start;
			   scanf("%d",&i);
			   for(i=1;i<no;i++)
				  last=read(i,last);
			   last->next=NULL;
			   write_rank(start,1);
			   for(i=0;i<no;i++)
				  printf("%d ",rank[i]);         
			   printf("\n");
	}

}
struct soldier * read(int inde,struct soldier * last)
{      
	   last->next=(sol*)malloc(sizeof(sol));
	   last=last->next;
	   last->place=last->index=inde;
	   scanf("%d",&(last->step));
	   
	   return(last);
}     
void write_rank(struct soldier * start,int ran)
{
	   if(start->next)
	   {      
	   struct soldier *temp2;
	   struct soldier *temp;                    
	   struct soldier *max;
	   struct soldier *max_father;
	   struct soldier *mover;
	   struct soldier *mover_father;
	   mover_father=start;
	   mover=start->next;
	   max=start;
	   while(mover)
	   {
		  if((mover->place)==(mover->step))   
				{max=mover;max_father=mover_father;}
		  mover_father=mover;
		  mover=mover->next;          
	   }
	   rank[max->index]=ran;
	   temp=max;
	   temp2=max->next;
	   while(temp2)
	   {
				   (temp2->place)--;
				   temp2=temp2->next;
	   }
					
	   if(start==max)
	   {             
					 start=start->next;
					 free(temp);
					 write_rank(start,ran+1);
	   }
	   else
	   {
					max_father->next=max->next;
					free(temp);
					write_rank(start,ran+1);      
	   }
	   }
	   else
	   {


		  rank[start->index]=ran; 
		  free(start);
		  
	   }
}

Also give me some general suggestion to make your program efficient…I am new to this site
Also tell me how to check your time taken by your program

the links don’t work for me (unable to download files)

The problem can be solved by implementing Binary tree.
But since the constraints are large,efficient implementation is required. O (n * logn) or O (n * logn * logn) will pass the judge.

Try to optimise write_rank function ,refer this thread http://apps.topcoder.com/forums/?module=Thread&threadID=515146&start=0&mc=12#575986 .,it will give you an idea-how to optimise it.

How to check your time taken by your program?

It can be done using clock function in time.h library :

#include <time.h>
#include <stdio.h>
int main()
{
		
		clock_t start = clock();
		//Take input here
		/*
 
				Code you want timed here 
				The program logic,Main Code ,etc.
		
		
		*/
		//Print final output /Results here
		clock_t ends = clock();
		printf("Run Time: %.5f\n", ((double)(ends - start)) / CLOCKS_PER_SEC);
 
		return 0;
}
3 Likes

first loop : 0<n<=50
second loop : num < 2 * 10^5
third loop: data[j] < 2 * 10^5

complexity = O(10^11) ~ 100 sec > time limit for this problem(13 sec)

3 Likes

I’m not sure if CodeChef server can make 10^9 “operations” in second :wink: but you are correct :wink:

//