## 188 - Perfect Hash

Moderator: Board moderators

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

### 188 - Perfect Hash

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...

fcarlos
New poster
Posts: 5
Joined: Sat Jul 27, 2002 4:16 am

### Problem188

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. obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm
then waht if the words duplicates?

see example below

Code: Select all

``````aaa bbb bbb ccc ccc
``````
Time makes a fool of memory
And yet my memories still shine

zbogi
New poster
Posts: 15
Joined: Thu Aug 29, 2002 11:00 pm
Location: Bulgaria

### hmmm

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?
Tsvetan Bogdanov.
from Brain Explorer - Sofia University - FMI 2
e-mail: zbogi@yahoo.com

uzioriluzan
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am

### Re: 188 perfect hash - huh?

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...

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
wrong, the problem assures 32-bit integer (unsigned, of course) is sufficient.

alexg
New poster
Posts: 5
Joined: Wed Sep 01, 2004 11:24 am
Location: London, UK
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.

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
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.

zaomaohao
New poster
Posts: 1
Joined: Mon Jan 05, 2015 7:45 am

### Re: 188 - Perfect Hash

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.
Are you worried about pmp book dumps exam ccna training preparation? We offer up-to-dated MCTS Certification practice questions and www.brandeis.edu dumps with Sterling College exam pass guarantee of mcts training.

ryx
New poster
Posts: 4
Joined: Fri Jul 10, 2015 2:52 am

### Why the answer always exist?

Does anyone know, for every possible input, how to guarantee there is always an answer exist?
I have no ideas.
Thanks