## 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

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### 10226 - Hardwood Species

It's unbelievable that I got TLE in this problem. I think I handle the multiinput data well and use qsort to reduce the running time.Could someone find out the bugs?
[c]
#include<stdio.h>
#include<string.h>
struct treedata
{
long n;
char *name;
};
int comp(const void *,const void *);
void main(void)
{
int x,count,n,y,max;
long total;
double t;
char s;
struct treedata tree;
max=0;
for(x=0;x<10000;x++)
tree[x].name=NULL;
scanf("%d\n",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
n=total=0;
while(gets(s)!=NULL)
{
if(!strlen(s))
break;
total++;
for(y=0;y<n;y++)
if(strcmp(s,tree[y].name)==0)
{
tree[y].n++;
break;
}
if(y==n)
{
if(!tree[n].name)
tree[n].name=(char *)malloc(sizeof(char)*31);
strcpy(tree[n].name,s);
tree[n].n=1;
n++;
}
}
qsort(tree,n,sizeof(struct treedata),comp);
for(y=0;y<n;y++)
{
t=tree[y].n;
printf("%s %.4lf\n",tree[y].name,t/(double)total*100);
}
if(n>max)
max=n;
}
for(x=0;x<max;x++)
free(tree[x].name);
}
int comp(const void *a,const void *b)
{
return strcmp(((const struct treedata *)a)->name,((const struct treedata *)b)->name);
}
[/c]
Melon Melon
New poster
Posts: 17
Joined: Fri May 31, 2002 6:30 pm
Contact:
i wonder what is the use of the variable "count"???? ambition
New poster
Posts: 2
Joined: Fri Aug 16, 2002 3:47 am

### 10226 use stl but get TLE

10226 use stl but get TLE

who can help? maybe 30s i can accept the problem but now is 10s only... [cpp]
#include <iostream>
#include <string>
#include <map>
#include <iomanip>

using namespace std;

typedef map< string, int > treeType;

treeType treeList;

int main(){
string elem;
double count;
int caseNum, l;
char buf;

cin >> caseNum;
cin.getline(buf, sizeof(buf));

for( l = 0; l < caseNum; l++ ){
count = 0;

while( cin.getline(buf, sizeof(buf)) ){

if( int(buf) == 0 )
break;

elem = buf;
count++;
treeList[elem]++;
}

treeType::iterator l = treeList.begin();
while( l != treeList.end() ){
cout.setf(ios::fixed);
cout.precision(4);
cout << (*l).first << " " << double((*l).second)/count*100.0 << endl;
l++;
}
}

return 0;
}
[/cpp]
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

### 10226 Hardwood species: can anybody help me

I can't understand why i got runtime error all the time . I think this is a multiple input problem and my array size ok. will anybody kindly see my code and tell me where i am wrong.thanks in advance.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
main()
{
char a,b,c,temp,f;
long long int i,j,k,l,n,p,m,cnt,y,count,x;
float d,z;
gets(a);
n=atoi(a);
gets(a);
for(x=0;x<n;x++)
{
j=p=0;
while(1)
{
if(gets(b[j])==NULL) {p=1;break;}
if(!strcmp(b[j],"")) break;
j++;
}
if(p) break;
count++;
for(i=0;i<j;i++)
for(k=i+1;k<j;k++)
{
if((strcmp(b[i],b[k]))>0)
{
strcpy(temp,b[i]);
strcpy(b[i],b[k]);
strcpy(b[k],temp);
}
}
m=cnt=y=0;k=0;
for(i=0;i<j;i++)
{
for(k=i;k<j;k++)
{
if(strcmp(b[i],b[k])==0) cnt++;
else break;
}
d[m++]=((float)cnt/j)*100.0000;
strcpy(f[y++],b[i]);
i=k-1;
cnt=0;
}

for(i=0;i<m;i++)
{
printf("%s %.4f\n",f[i],d[i]);
}
if(count!=(n-1)) printf("\n");
}
return 0;
}
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

### 10226 Hardwood species: can anybody help me

I can't understand why i got runtime error all the time . I think this is a multiple input problem and my array size ok. will anybody kindly see my code and tell me where i am wrong.thanks in advance.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
main()
{
char a,b,c,temp,f;
long long int i,j,k,l,n,p,m,cnt,y,count,x;
float d,z;
gets(a);
n=atoi(a);
gets(a);
for(x=0;x<n;x++)
{
j=p=0;
while(1)
{
if(gets(b[j])==NULL) {p=1;break;}
if(!strcmp(b[j],"")) break;
j++;
}
if(p) break;
count++;
for(i=0;i<j;i++)
for(k=i+1;k<j;k++)
{
if((strcmp(b[i],b[k]))>0)
{
strcpy(temp,b[i]);
strcpy(b[i],b[k]);
strcpy(b[k],temp);
}
}
m=cnt=y=0;k=0;
for(i=0;i<j;i++)
{
for(k=i;k<j;k++)
{
if(strcmp(b[i],b[k])==0) cnt++;
else break;
}
d[m++]=((float)cnt/j)*100.0000;
strcpy(f[y++],b[i]);
i=k-1;
cnt=0;
}

for(i=0;i<m;i++)
{
printf("%s %.4f\n",f[i],d[i]);
}
if(count!=(n-1)) printf("\n");
}
return 0;
}
Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
I guess you misunderstood the problem. You think that there can be only 10000 lines in input, but according to the problem statement there can be up to 1000000 lines for one test. Therefore you can't keep all the input in one array (you used b). You should use a structure like sorted list that is updated for each new line of input. Well... perhaps there are better algorithms, but I did it this way. And another little bug in your program - name of a tree can be up to 30 characters - it's not enough to use arrays like b[...]. You should use b[...]. Try it and get AC.

Buy.
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
Sorry for you incovenience. As i am a new programmer i can't understand what do you mean by structur with sorted list that is updated for new line of input. Would you kindly please tell me this thing with example. If you are kind enough would you explain all the other ways. Thanks in advance.
Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
Well, I'll try to explain the way I did it.

I used sorted list of structures { char *s; int count;}, that was sorted by s.

First let the list be empty.

Then for each line S of input you should:

1. Find out if S is in the list. As our list is sorted we can do it using binary search.
2. If S is in the list we increase count of the item.
3. If S is not in the list we insert new item so that the list remain sorted and set its count to be 1.

After reading in all the lines we have sorted list of trees and the number of appearances of each one.

Now it's easy to do the rest.

I tried to explain carefully, but my English is not well so ask me whatever you don't understand.

Good luck.
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
Thank you very much for your kind information. I have to think about your advice deeply and recode the problem. Thanks again. ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:

### Same is the case with me

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

Can anybody help....
gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
I appears to me that the posted code does not
reset the table to "empty" between input cases.
ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:

### But it doesnt have anything to do with TLE

hi gvcormac:

But that doesnt have anything to do with TLE. if he is not "emptying" the map table then I think it should give a WA but not a TLE. I have actually modified the posted code into this:
[cpp]
#pragma warning(disable : 4786)
#include <iostream>
#include <string>
#include <map>
#include <iomanip>
#include <fstream>

using namespace std;
typedef map< string, int > treeType;
treeType treeList;

int main(){
string elem;
double count;
int caseNum, l;

cin >> caseNum;
getline(cin,elem);
getline(cin,elem);

for( l = 0; l < caseNum; l++ ){
count = 0;
treeList.clear();

while( getline(cin,elem) ){

if(elem=="")
break;

count++;
treeList[elem]++;
}

treeType::iterator l = treeList.begin();
while( l != treeList.end() ){
cout.setf(ios::fixed);
cout.precision(4);
cout << (*l).first << " " <<(double((*l).second)/count)*100.0 << endl;
l++;
}
}

return 0;
}
[/cpp]

But it still gives a TLE. There must be someother way to do this.
stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### 10226 compile error from <algorithm> sort

Anyone knows what the compile error means when you try to compile this following program of mine for 10226? It has to do with calling the function sort from <algorithm>. I get the same error when calling sort on another program, this time giving a comparator function as 3rd argument. Any hint on getting rid of the compile error would be much appreciated.
THANKS.

[cpp]#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <map>
#include <iomanip>

int main()
{
string input;
map<string, int> names;
map<string, int>::iterator itor, b, e;
int count=0;
while(true)
{
getline(cin, input);
if(cin.eof())
break;
if(names.find(input) == names.end())
names[input] = 1;
else names[input]++;
count++;
b = names.begin();
e = names.end();
sort(b,e);
cout.setf(ios::fixed);
cout << setprecision(4);
itor=names.begin();
while(itor != names.end())
{
cout << (*itor).first << " " << (*itor).second << "\n";
}
}
return 0;
}[/cpp]
Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
You can't sort the elements of a map. And you don't need it, since they are already sorted by key value (in this case by the strings).
stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### 10226 TLE

I can't believe I am having so many problems with this simple problem. I submitted at least 10 times and still get TLE. I have tried having 256 separate maps (one for each treename starting with a different ascii value character), or 256x256 (depending on ascii value of first 2 characters), and finally with 64x64 maps.

Could anyone please kindly tell me how you solved the problem w/o TLE? THANKS so much.

[cpp]
#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <map>
#include <iomanip>

int main()
{
int numcases;
cin >> numcases;
string temp, input;
getline(cin, temp);
getline(cin, temp);
cout.setf(ios::fixed);
cout << setprecision(4);
for(int i=0; i<numcases; i++)
{
int count=0;
map<string, int> names;
map<string, int> group;
map<string, int>::iterator itor;
while(true)
{
if(cin.peek() == '\n')
{
getline(cin, temp);
break;
}
if(cin.eof())
break;
getline(cin, input);

if(input.length() == 1)
(names[input/64])[input]++;
else (names[input/64][input/64])[input]++;

count++;
}

for(int i=0; i<64; i++)
{
for(int j=0; j<64; j++)
{
group = names[j];
itor = group.begin();
while(itor != group.end())
{
cout << (*itor).first << " ";
cout << (*itor).second * 100.0 / (double)count << "\n";
itor++;
}
}
}
cout << "\n";
}
return 0;
}[/cpp]