Time Limit Exceeded TLE

general
, , , ,
1

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

2

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

3

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;
}
4

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)

2 Likes
5

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