10226 - Hardwood Species

[htl]

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[31];
struct treedata tree[10000];
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]

i wonder what is the use of the variable "count"????

[ambition]

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[500];

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]) == 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]

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[1000],b[10000][30],c[10000][30],temp[1000],f[10000][30];
long long int i,j,k,l,n,p,m,cnt,y,count,x;
float d[10000],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]

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[1000],b[10000][30],c[10000][30],temp[1000],f[10000][30];
long long int i,j,k,l,n,p,m,cnt,y,count,x;
float d[10000],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]

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[10000][30]). 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[...][30]. You should use b[...][31].

Try it and get AC.

Buy.

[yahoo]

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]

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]

Thank you very much for your kind information. I have to think about your advice deeply and recode the problem. Thanks again.

[ram]

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]

I appears to me that the posted code does not
reset the table to "empty" between input cases.

[ram]

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]

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]

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]

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[64][64];
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[0]/64][0])[input]++;
else (names[input[0]/64][input[1]/64])[input]++;

count++;
}

for(int i=0; i<64; i++)
{
for(int j=0; j<64; j++)
{
group = names[i][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]