10226 - Hardwood Species

[cytmike]

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]

[minskcity]

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]

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]

[cytmike]

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]

[Larry]

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]

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?

[minskcity]

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]

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*

[minskcity]

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]

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]

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)

[cytmike]

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]

[samueljj]

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;
	}

[BiK]

How on earth are you using hash_map? This class is not part of the C++ standard.

[cytmike]

How on earth are you using hash_map? This class is not part of the C++ standard.

What on earth should I use then....