188 - Perfect Hash

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

188 - Perfect Hash

Post by Joe Smith » Mon Jul 22, 2002 5:38 pm

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

Post by fcarlos » Sat Aug 10, 2002 7:04 pm

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.

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

Post by obayashi » Fri Aug 30, 2002 6:05 am

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

Post by zbogi » Sat Aug 31, 2002 8:33 pm

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?

Post by uzioriluzan » Wed Oct 30, 2002 3:36 am

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
Location: Edmonton AB Canada

Post by Quantris » Sun May 07, 2006 12:51 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

Post by alexg » Tue May 09, 2006 4:26 pm

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
Location: Edmonton AB Canada

Post by Quantris » Tue May 09, 2006 10:43 pm

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

Post by zaomaohao » Mon Jan 05, 2015 7:47 am

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?

Post by ryx » Mon Nov 05, 2018 9:52 pm

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

Post Reply

Return to “Volume 1 (100-199)”