10226 - Hardwood Species

Moderator: Board moderators

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
I do something like this here.
But I still got TLE... What happens??
If I just read data, its 1.3s.
But if I put them in the map, it's TLE already.

[cpp]map <string,int> sky;

int size=0;
while (gets(h)&&strlen(h))

{
size++;
sky[(string)h]++;
} [/cpp]
Impossible is Nothing.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
I've heard find() works faster then [], also make sure to call clear() between testcases.
Try to post your code here - Larry might tell you if he did something in different way.

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
My code is here. As you can see, I don't need to clear as the map is destroyed after each case.

[cpp]
#include <string>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>

using namespace std;

int main()
{
int p;
cin>>p;
char h[3000];
gets(h);
gets(h);

for (int y=0;y<p;y++)
{
if (y)
cout<<endl;
map <string,int> sky;

int size=0,type=0;
cs l[10001];
cout<<sizeof(l)<<endl;
while (gets(h)&&strlen(h))
{
size++;
sky[h]++;

}

double i=size/100.0;
string s=" ";

for (map <string,int>::iterator l=sky.begin();l!=sky.end();l++)
{
if ((*l).first!=s)
cout<<(*l).first<<' '<<setprecision(4)<<setiosflags(ios::fixed)<<(*l).second/i<<endl;
s=(*l).first;
}
}
return 0;
}
[/cpp]
Impossible is Nothing.

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
I changed to use hash_map
I get WA in 5s...
What happens?

[cpp]#include <string>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <hash_map.h>

using namespace std;

struct cs
{
string p;
char h[31];
};

bool sillyhp(cs p,cs h)
{
return p.p<h.p;
}

struct eqstr
{
bool operator()(char* s1,char* s2)
{
return strcmp(s1,s2)==0;
}
};

int main()
{
int p;
cin>>p;
char h[3000];
gets(h);
gets(h);
for (int y=0;y<p;y++)
{
if (y)
cout<<endl;
hash_map <char*,int,hash<char*>,eqstr> sky;

int size=0,type=0;
cs l[10001];

while (gets(h)&&strlen(h))

{
size++;
sky[h]++;

if (sky[h]==1)
{
strcpy(l[type].h,h);
l[type].p=h;
type++;

}
}

double i=size/100.0;
string s=" ";

sort(l,l+type,sillyhp);
for (int z=0;z<type;z++)
{
cout<<l[z].p<<' ';
cout<<setprecision(4)<<setiosflags(ios::fixed)<<sky[l[z].h]/i<<endl;
}

}
return 0;
} [/cpp]
Impossible is Nothing.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I don't know, I use printf instead of cout, but otherwise, everything looks the same..

I use .clear() instead of reallocating the memory.. don't know which is faster..

[] is different from .find in that if the key is not in the map, it'll create it, while in .find, it'll just return 0. In this case, since that's what we want to do anyhow, I used []..

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
Larry wrote:I don't know, I use printf instead of cout, but otherwise, everything looks the same..

I use .clear() instead of reallocating the memory.. don't know which is faster..

[] is different from .find in that if the key is not in the map, it'll create it, while in .find, it'll just return 0. In this case, since that's what we want to do anyhow, I used []..
Larry, can you send me your code to have a look at the differences?
Impossible is Nothing.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
Your last code results in WA because it always prints 0.0000. (at least for me)
cout is fast enough for this problem: I've just moved to second place with 0.8sec, still using cout for output...

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
minskcity wrote:Your last code results in WA because it always prints 0.0000. (at least for me)
cout is fast enough for this problem: I've just moved to second place with 0.8sec, still using cout for output...
So you use your own hash fucntion?
I don't know why there is some problem with STL hash_map with const char*
Impossible is Nothing.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
cytmike wrote: So you use your own hash fucntion?
I don't know why there is some problem with STL hash_map with const char*
I guess hash_map is actually using pointer to char, not array of chars as a key (It's definetely true for set, I checked it). You should try to use string.

BTW, hash I'm using is very easy to implement: I'm using a tree, each node has an array of 256 pointers to the next node(for each char) and a counter. Even the most naive implementation runs in under 2sec. My basic hash implementation was ~20 lines long and was coded in 10 minutes. Later I managed to optimize it to run in under 0.5sec, which moved me to 1st place. (but you have to work on input/output if you want to achieve that time)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
minskcity wrote:
cytmike wrote: So you use your own hash fucntion?
I don't know why there is some problem with STL hash_map with const char*
I guess hash_map is actually using pointer to char, not array of chars as a key (It's definetely true for set, I checked it). You should try to use string.

BTW, hash I'm using is very easy to implement: I'm using a tree, each node has an array of 256 pointers to the next node(for each char) and a counter. Even the most naive implementation runs in under 2sec. My basic hash implementation was ~20 lines long and was coded in 10 minutes. Later I managed to optimize it to run in under 0.5sec, which moved me to 1st place. (but you have to work on input/output if you want to achieve that time)
That's a trie.. =)

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
minskcity wrote:
cytmike wrote: So you use your own hash fucntion?
I don't know why there is some problem with STL hash_map with const char*
I guess hash_map is actually using pointer to char, not array of chars as a key (It's definetely true for set, I checked it). You should try to use string.

BTW, hash I'm using is very easy to implement: I'm using a tree, each node has an array of 256 pointers to the next node(for each char) and a counter. Even the most naive implementation runs in under 2sec. My basic hash implementation was ~20 lines long and was coded in 10 minutes. Later I managed to optimize it to run in under 0.5sec, which moved me to 1st place. (but you have to work on input/output if you want to achieve that time)
but hash_map doesn't support string (or i just can't use it like using string in map)
Impossible is Nothing.

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
I changed my code to this in order to do string hashing, but the judge gives me compile error while i can correctly compile using gcc, why?

[cpp]#include <string>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <locale.h>
#include <algorithm>
#include <hash_map.h>

using namespace std;

struct hashing
{
size_t operator()(const string& s) const
{
const collate<char>& c = use_facet<collate<char> >(locale::classic());
return c.hash(s.c_str(), s.c_str() + s.size());
}
};

int main()
{
int p;
cin>>p;
char h[31];
gets(h);
gets(h);
for (int y=0;y<p;y++)
{
if (y)
cout<<endl;
hash_map<string,int,hashing> sky;
int size=0,type=0;
string l[10001];
while (gets(h)&&strlen(h))
{
size++;
if (sky.count(h)==0)
{
l[type]=h;
type++;
}
sky[h]++;
}
double i=size/100.0;
string s=" ";
sort(l,l+type);
for (int z=0;z<type;z++)
{
cout<<l[z]<<' ';
cout<<setprecision(4)<<setiosflags(ios::fixed)<<sky[l[z]]/i<<endl;
}
}
return 0;
} [/cpp]
Impossible is Nothing.

samueljj
New poster
Posts: 18
Joined: Fri Jul 18, 2003 5:24 am

10226....WA help

can anybody say why i am getting WA. my code :

Code: Select all

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

struct hardwood
{
char name[31];
long double frequency;
}tree[10101];
long int n=0;
int bsearch(char *name);
void insert(char *name);

void main()
{
char name[31];
long int i,j;
float result;

//freopen("i:\\in.txt","r",stdin);
//freopen("i:\\out.txt","w",stdout);
for(i=0;;i++)
{
if(gets(name)==0)	break;
j=bsearch(name);
if(j==-1)	{insert(name);n++;}
else		tree[j].frequency++;
}
for(j=0;j<n;j++)
{
result=(tree[j].frequency/i)*100;
printf("%s %.4f\n",tree[j].name,result);
}
}

int bsearch(char *name)
{
long int beg=0,end=n-1,mid;

for(;beg<=end;)
{
mid=(beg+end)/2;
if(strcmp(tree[mid].name,name)==0)		return mid;
else if(strcmp(tree[mid].name,name)<0)	beg=mid+1;
else									end=mid-1;
}
return -1;
}

void insert(char *name)
{
long int j;

for(j=n-1;j>=0&&strcmp(tree[j].name,name)>0;j--)
{
strcpy(tree[j+1].name,tree[j].name);
tree[j+1].frequency=tree[j].frequency;
}
strcpy(tree[j+1].name,name);
tree[j+1].frequency=1;
}
novice programmer

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
How on earth are you using hash_map? This class is not part of the C++ standard.

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
BiK wrote:How on earth are you using hash_map? This class is not part of the C++ standard.

What on earth should I use then....
Impossible is Nothing.