10226 - Hardwood Species

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

10226 TLE

Post by Riyad »

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

Code: Select all

#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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

Post by Riyad »

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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. »

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!
JongMan @ Yonsei

szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

Re: Same is the case with me

Post by szymcio2001 »

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.

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

Post by Riyad »

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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

rlatif119
New poster
Posts: 16
Joined: Mon Mar 01, 2004 4:00 pm
Location: Dhaka

10226......TLE

Post by rlatif119 »

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? :o
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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

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
New poster
Posts: 16
Joined: Mon Mar 01, 2004 4:00 pm
Location: Dhaka

Post by rlatif119 »

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
New poster
Posts: 8
Joined: Sun May 16, 2004 12:48 am
Contact:

ios_base not fully supported

Post by DavidDeharbe »

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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

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

DavidDeharbe
New poster
Posts: 8
Joined: Sun May 16, 2004 12:48 am
Contact:

Post by DavidDeharbe »

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
New poster
Posts: 8
Joined: Sun May 16, 2004 12:48 am
Contact:

Post by DavidDeharbe »

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
New poster
Posts: 8
Joined: Sun May 16, 2004 12:48 am
Contact:

Post by DavidDeharbe »

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
New poster
Posts: 8
Joined: Sun May 16, 2004 12:48 am
Contact:

Post by DavidDeharbe »

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
New poster
Posts: 3
Joined: Thu Jun 17, 2004 8:03 pm
Location: Berlin, Germany
Contact:

Post by PunyTroll »

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

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

Thx for replies, Hagen.

Post Reply

Return to “Volume 102 (10200-10299)”