Page 1 of 1

188 - Perfect Hash

Posted: Mon Jul 22, 2002 5:38 pm
by Joe Smith
I don't understand why I'm getting WA here. The problem desc. says exactly what to do and it works on all the input i've tried. Can anyone see the problem? (I know my split function is fine, and i added the long long just as an extra precaution.)

[cpp]
while (gets(buf)) {
printf("%s\n", buf);
vector<string> vs = split(buf, " ");
c.clear();
for (int i=0; i<vs.size(); i++) {
int code = 0;
for (int j=0; j<vs.length(); j++)
code = code*32 + (vs[j]-'a'+1);
c.push_back(code);
}
int n=c.size();
long long C=2;
for (;;) {
long long biggest=-1;
for (int i=0; i<n; i++) for (int j=0; j<n; j++)
if (i!=j && ((C/c)%n == (C/c[j])%n))
biggest >?= min((C/c+1)*c,(C/c[j]+1)*c[j]);
if (biggest==-1) break;
C=biggest;
}
printf("%lld\n\n", C);
}
}
[/cpp]

Thanks...

Problem188

Posted: Sat Aug 10, 2002 7:04 pm
by fcarlos
Folks!!

I would like of a tests sample of input/output for test my program. I test it
with following samples and i got the correct answer

this is a test of some words to try out
a bee see dee
the of and to a in that is i it with for as

this is a test of some words to try out
17247663

a bee see dee
4427

the of and to a in that is i it with for as
667241.

But, I got WA of Judge. :(

Thanks advance.

Posted: Fri Aug 30, 2002 6:05 am
by obayashi
then waht if the words duplicates?

see example below

Code: Select all

aaa bbb bbb ccc ccc

hmmm

Posted: Sat Aug 31, 2002 8:33 pm
by zbogi
The second part seems alright to me(it is almost the same as mine- I got ACC). However, I don`t know if you read the words ok. Are you sure you read the last word?

Re: 188 perfect hash - huh?

Posted: Wed Oct 30, 2002 3:36 am
by uzioriluzan
you must use long long. but the initial value for C must be the minimum of the vector, not 2.
Joe Smith wrote:I don't understand why I'm getting WA here. The problem desc. says exactly what to do and it works on all the input i've tried. Can anyone see the problem? (I know my split function is fine, and i added the long long just as an extra precaution.)

[cpp]
while (gets(buf)) {
printf("%s\n", buf);
vector<string> vs = split(buf, " ");
c.clear();
for (int i=0; i<vs.size(); i++) {
int code = 0;
for (int j=0; j<vs.length(); j++)
code = code*32 + (vs[j]-'a'+1);
c.push_back(code);
}
int n=c.size();
long long C=2;
for (;;) {
long long biggest=-1;
for (int i=0; i<n; i++) for (int j=0; j<n; j++)
if (i!=j && ((C/c)%n == (C/c[j])%n))
biggest >?= min((C/c+1)*c,(C/c[j]+1)*c[j]);
if (biggest==-1) break;
C=biggest;
}
printf("%lld\n\n", C);
}
}
[/cpp]

Thanks...

Posted: Sun May 07, 2006 12:51 am
by Quantris
wrong, the problem assures 32-bit integer (unsigned, of course) is sufficient.

Posted: Tue May 09, 2006 4:26 pm
by alexg
Quantris wrote:wrong, the problem assures 32-bit integer (unsigned, of course) is sufficient.
Works fine with signed 32-bit integers. There are a maximum of 5 letters in each word. 5 bits for each letter = a maximum of 25 bits required.

Posted: Tue May 09, 2006 10:43 pm
by Quantris
I'm pretty sure you can make the required C exceed signed 32-bit.

EDIT:

zzzzz zzzzy fafa zdfdz dfazz zzxf s

gives 2532818294, which fits in unsigned but not in signed.

Re: 188 - Perfect Hash

Posted: Mon Jan 05, 2015 7:47 am
by zaomaohao
I understand what you are saying but I think there should be more comments regarding the threat that was initially started so that the pool of thoughts is attracted. Regards.

Why the answer always exist?

Posted: Mon Nov 05, 2018 9:52 pm
by ryx
Does anyone know, for every possible input, how to guarantee there is always an answer exist?
I have no ideas.
Thanks