10226 - Hardwood Species

[minskcity]

Where t is the name of the map, and a is the name of the char array.

t[ string( a ) ] = whatever;

(Though, of course, it takes time..)

I used STL's map and got AC in about 5 secs..

Who did you read char arrays? gets()?

[cytmike]

Where t is the name of the map, and a is the name of the char array.

t[ string( a ) ] = whatever;

(Though, of course, it takes time..)

I used STL's map and got AC in about 5 secs..

Who did you read char arrays? gets()?

yea
i used sth like this:

char y[size];
cin>>y;
set<char *> t;
t[y]=...;

but when i call t.count(y) it is always 0

my code is shown above
the hash set throw away all data

[minskcity]

char y[size];
cin>>y;
set<char *> t;
t[y]=...;

1) STL "set" is not hashset, optional second parameter in the template is comparator.
2) STL "set" does not look to support []. STL "map" does.
3) cin >> y will only read until space.
4) set < char * > might create a set of pointers, not strings.

---- According to Larry, it's possible to get AC by using STL map ( not hashed ) by reading char* and converting them into strings when accessing the map.

I was asking Larry which function he was using to read char arrays fast enough...

[cytmike]

I used this:

[cpp]hash_multiset <char*> sky;
cin.getline(h,32);
while (strlen(h))
{
sky.insert(h);
cin.getline(h,32);
}[/cpp]

a set of pointers? why? what should i do then? convert c-styled char array to c++ string first?

[Larry]

I don't have the code in front of me, but I almost never use cin, (since I am still mostly a C programmer)

I do something like this:

Code: Select all

char a[MAX_L];
map<string, int> t;

while ( gets( a ) ) {
    t[ string( a ) ]++;
}


Of course, you have to clear and stuff, but that's how I handle it..

[minskcity]

I don't have the code in front of me, but I almost never use cin, (since I am still mostly a C programmer)

I do something like this:

Code: Select all

char a[MAX_L];
map<string, int> t;

while ( gets( a ) ) {
    t[ string( a ) ]++;
}


Of course, you have to clear and stuff, but that's how I handle it..

THANKS A LOT!!!!
The only change I made to my program was getline->gets...
That corresponded to 10+sec->1.77sec, AC, 7th in ranking... (looks like my hashing works)

PS: You might be a mostly a C programmer, but I bet you are using STL map whenever is possible.

[Larry]

I am indeed a C programmer.. but I was learning the STL at some point.. no point in reinventing the wheels, eh?

[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*