10226 - Hardwood Species

Riyad · Post by **Riyad** » Fri Oct 31, 2003 8:09 am

what is the prob with my code of 10226 . it gets me TLE . pliz help me

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct Tree {
	char name[32];
	int freq;
	

};

struct Tree object[10000];

int index;

int check(char p[]){
	int i ;
	for(i=0;i<index;i++){
		if(strcmp(object[i].name,p)==0)
			return i;
		else
			continue;
	
	}
	return -1;



}

int compare(const void * a , const void * b){

	return strcmp(((const struct Tree *)a)->name,((const struct Tree *)b)->name);
}



int main(){

	
	int c ,i,minput;
	long int total;
	double result,x,y;
	char input[35];
        scanf("%d",&minput);
        getchar();
        while(minput>0){
		
	
		total=0;
		index=0;

		while(gets(input)){
			if(strcmp(input," ")==0)
				continue;
			c=check(input);
			if(c==-1){
				strcpy(object[index].name,input);
				object[index++].freq=1;

			}

			else
				object[c].freq++;
			total++;
		}
		
		
		qsort(object,index,sizeof(struct Tree),compare); 
		
		
		
		x=total;
		
		for(i=0;i<index;i++){
			y=object[i].freq;
			result=(double)(y/x)*100.0;
			
			
			printf(object[i].name);
			printf(" %.4lf\n",result);
		
		}
        printf("\n");
        minput--;


        }
		

	return 0;
}

Bye
Riyad

Riyad · Post by **Riyad** » Fri Oct 31, 2003 8:23 am

i went through all the topics about 10226 in the board . but no one seems to ans the reason behind getting TLE properly . how can we over come it . plizzzzzzzzzzzzzzz help me in this
Riyad

Whinii F. · Post by **Whinii F.** » Fri Oct 31, 2003 9:54 am

In your code, searching a tree costs O(n) and inserting costs O(1).

But, you can do binary searching to reach O(logn) in searching and doing inserting with O(n).

It is likely the latter will be faster, since you'll have only 10,000 insertings and 1,000,000 searchings.

Hope this helps!

szymcio2001 · Post by **szymcio2001** » Sun Nov 02, 2003 9:29 pm

ram wrote:I also used STL for solving this problem. But getting a TLE. Is anything wrong with the input or our algo?

I also got TLE when using <string>. After changing strings to char* I got Acc in 6 sec. And I had my own hash table.

Riyad · Post by **Riyad** » Mon Nov 03, 2003 3:59 pm

hey i tried to use the binary search tree to solve the prob as u said me to do . but it is fetching me wa . what did i do wrong , icant find it out . so can u plizzzzzzzzzzzzzz help me in this .
here is my code for 10226 . pliz help me in this .

[c]#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>

#define MAXWORD 50

long int Total;

struct tnode {
char *word;
int count ;
struct tnode *left;
struct tnode *right;

};

struct tnode * talloc(void);
char * strdup(char *);
struct tnode * addtree(struct tnode*,char *);
void treeprint(struct tnode*);
void FreeTree(struct tnode *);

int main(){
struct tnode * root;

char word[MAXWORD];

long int mcount ;

scanf("%ld",&mcount);
getchar();
while(mcount>0L){
root=NULL;
Total=0L;
while(gets(word)){
Total++;
root=addtree(root,word);

}
treeprint(root);
printf("\n");
FreeTree(root);

mcount --;
}

return 0;
}

struct tnode* addtree(struct tnode* p , char * w){
int cond;
if(p==NULL){

p=talloc();
p->word=strdup(w);
p->count=1;
p->left=p->right=NULL;

}
else if((cond=strcmp(w,p->word))==0)
p->count++;
else if(cond<0)
p->left=addtree(p->left,w);
else
p->right=addtree(p->right,w);

return p;

}

void treeprint(struct tnode *p){

if(p!=NULL){
treeprint(p->left);
printf(p->word);
printf(" %.4lf\n",(double)((double)(p->count)/(double)(Total))*100.00);
treeprint(p->right);

}

}

struct tnode *talloc(void){
return (struct tnode *) malloc(sizeof(struct tnode));
}

char * strdup(char *s){
char *p;
p=(char *) malloc(strlen(s)+1);

if(p!=NULL)
strcpy(p,s);
return p;

}

void FreeTree(struct tnode *t)
{
if(t==NULL)return;
if(t->left!=NULL)FreeTree(t->left);
if(t->right!=NULL)FreeTree(t->right);

free(t);
}[/c]

regards
riyad

rlatif119 · Post by **rlatif119** » Tue Apr 20, 2004 5:26 pm

My code causes TLE. I cannot find out the reason. I used Quick sort algorithm to sort the tree names and then start scan though the list and keep counting. It doesn't require any searching algorithm. But it causes mysterious TLE. Can somebody find out the problem?

My code is given below
[c]
#include<stdio.h>
#include<string.h>
void Qsort(long p, long r);
long Partition(long p, long r);

struct list{
char tree[32];
};
struct list forest[1000000];
/*FILE *fp;*/

main()
{
long i,n,len,count,N,c,j;
char str[32],ch;
/*fp = fopen("10226.txt","r");*/

fscanf(stdin,"%ld",&N);

while(N>0)
{
i=0;
count = 0;
while(1)
{
fgets(forest.tree,32,stdin);
if(strcmp(forest.tree,"\n")==0 && i==0)
continue;
else if(strcmp(forest.tree,"\n")==0)
break;
else
{
forest.tree[strlen(forest.tree)-1]='\0';
count = 0;
}
++i;
}

n=i;
Qsort(0,n-1);
count = 1;
strcpy(str,forest[0].tree);
for(i=1;i<=n;++i)
{
if(strcmp(str,forest.tree)==0)
{
++count;
continue;
}
else
{
printf("%s %0.4f\n",str,(count*100.0)/n);
strcpy(str,forest.tree);
count = 1;
}
}
printf("\n");
--N;
}
}

void Qsort(long p, long r)
{
long q;
if(p<r)
{
q = Partition(p,r);
Qsort(p,q);
Qsort(q+1,r);
}
}
long Partition(long p, long r)
{
struct list x,temp;
long i,j;

strcpy(x.tree,forest[p].tree);

i = p-1;
j = r+1;
while(i<=j)
{
do {
--j;
}while(strcmp(forest[j].tree,x.tree)>0);
do {
++i;
}while(strcmp(forest.tree,x.tree)<0);

if(i<j)
{
temp = forest;
forest=forest[j];
forest[j]=temp;
}

else
return j;
}

}

[/c]

Larry · Post by **Larry** » Tue Apr 20, 2004 6:17 pm

Code: Select all

while(1) 
   { 
   fgets(forest[i].tree,32,stdin); 
   if(strcmp(forest[i].tree,"\n")==0 && i==0) 
      continue; 
   else if(strcmp(forest[i].tree,"\n")==0) 
      break; 
   else 
      { 
      forest[i].tree[strlen(forest[i].tree)-1]='\0'; 
      count = 0; 
      } 
   ++i; 
   }

Might want to reconsider this..

rlatif119 · Post by **rlatif119** » Wed Apr 21, 2004 12:03 pm

Well Larry.......you adviced me to check the input portion....well, but it works fine with my sample input file and generates correct output. If you see carefully, you can realize it can handle more than one blang line between two dataset. Well.......thanks for your reply......i am trying to take input character by character.
Hope for the best

DavidDeharbe · Post by **DavidDeharbe** » Sun May 16, 2004 12:55 am

I use the following code so that float are output as specified in problem 10226, e.g. 3.1416 for pi.

[cpp]
cout.flags(ios_base::fixed | ios_base::showpoint);
cout.precision(4);
[/cpp]

I have included iostream and iomanip, and am using namespace std. This compiles fine with g++ (GCC) 3.2.2 (Mandrake Linux 9.1 3.2.2-3mdk).

Any idea what is going on? And how can I fix that using C++ library routines?

Thanks,

David.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Mon May 17, 2004 1:53 am

I've already answered to similar questions several times. Just search the board. It's much faster than waiting for someone to reply.

DavidDeharbe · Post by **DavidDeharbe** » Mon May 17, 2004 3:47 pm

For each tree name, you scan the whole list of species. So assuming that you have S species, and are reading N names, of length L, then your complexity is roughly N*M*L. Now, if S = 10,000, N = 1,000,000, and L=30, there is no wonder that you get time limit exceeded.

Note that even if you maintain the list of species ordered, then your complexity will be roughly log S * N * L; which is still too much, I think for the judge test cases.

I have only managed to get an accepted when I made my solution linear in the size of the input, that is N * L.

Best luck,

David.
--

DavidDeharbe · Post by **DavidDeharbe** » Mon May 17, 2004 3:50 pm

For each tree name, you scan the whole list of species. So assuming that you have S species, and are reading N names, of length L, then your complexity is roughly N*M*L. Now, if S = 10,000, N = 1,000,000, and L=30, there is no wonder that you get time limit exceeded.

Note that even if you maintain the list of species ordered, then your complexity will be roughly log S * N * L; which is still too much, I think for the judge test cases.

I have only managed to get an accepted when I made my solution linear in the size of the input, that is N * L.

Best luck,

David.

DavidDeharbe · Post by **DavidDeharbe** » Mon May 17, 2004 3:53 pm

The search in a map container is too expensive (linear). As you may have as much as 1,000,000 searches in a map of up to 10,000 you exceed the time limits. I am not sure that the compiler accepts hash_map, but it should significantly decrease the execution time.

Best luck,

David.

DavidDeharbe · Post by **DavidDeharbe** » Mon May 17, 2004 4:11 pm

Thanks for pointing this to me. I enlarged the scope of my search and finally find some pieces of answers. I wonder if there is a web page where the "features" of the current C++ compiler are exhaustively documented.

Cheers,

David.
--

PunyTroll · Post by **PunyTroll** » Thu Jun 17, 2004 8:12 pm

OK, I got that. But the question remains: Why? It's more obscure and, although valid, Stroustrup himself uses the short form. Additionally
[cpp]
std::cout << std::setw(3) << std::ios::right << 3 << std::endl;
[/cpp]
produces some very nasty things:

Code: Select all

which is not quite what I would expect. So Why is the short form not accepted?

Thx for replies, Hagen.

OJ Board

10226 - Hardwood Species

10226 TLE

Re: Same is the case with me

10226......TLE

ios_base not fully supported