843 - Crypt Kicker

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

Moderator: Board moderators

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:

843 - Crypt Kicker

Post by dh3014 » Sun Jun 16, 2002 6:47 am

In the problem description it said:
"If there is more than one solution, any will do. "
but the icon of the problem shows that it doesn't use special judge...
may any adms tell me what's going on?

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN » Sun Jun 16, 2002 6:58 am

Does it means that the judge data is well chosen so that there's only one solution?

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:

Post by dh3014 » Sun Jun 16, 2002 7:35 am

yes, probably the test data was chosen...
but after I got several WA and test my program several times...
I think I should check it out if there's any mistake judge made.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jun 16, 2002 2:29 pm

I am quite sure that the test data is not chosen, because I found some test inputs on the Waterloo Homepage and my program gives different, but correct outputs for some of the test cases. I will write a special judge program for this problem.

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:

Post by dh3014 » Sun Jun 16, 2002 3:09 pm

quite thanks

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jun 16, 2002 3:33 pm

I have now written the special judge program and send it to the admins. If after rejudge you get Wrong answer, you can send me your program, so that I can look, if my judge program or your program is wrong.

rfcotta
New poster
Posts: 7
Joined: Mon Aug 12, 2002 12:13 am

843 - Crypt Kicker

Post by rfcotta » Mon Aug 12, 2002 12:14 am

What are the gotchas on problem #843? I am almost sure my program works, but I get WA.

Any idea of something I may be missing?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Aug 12, 2002 12:36 am

Each letter must be decoded uniquely, that means that if the coded word is ab, the decoded word can't be cc.

rfcotta
New poster
Posts: 7
Joined: Mon Aug 12, 2002 12:13 am

Post by rfcotta » Mon Aug 12, 2002 12:43 am

Adrian Kuegel wrote:Each letter must be decoded uniquely, that means that if the coded word is ab, the decoded word can't be cc.
And that's what I do! If input gives me "ac" and the dictionary "xy", "xy will appear on output only if a new "ac" appears. That's right, isn't it? a sample follows.

input

2
ac
ad
xy xz cv

output

ac ad **

rfcotta
New poster
Posts: 7
Joined: Mon Aug 12, 2002 12:13 am

Post by rfcotta » Mon Aug 12, 2002 12:46 am

Adrian Kuegel wrote:Each letter must be decoded uniquely, that means that if the coded word is ab, the decoded word can't be cc.
This sample is better:

input

2
ac
ad
xy kz cv

output

ac ad **

----
"a" appears as "x" and "k". Is it ok?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Aug 12, 2002 12:51 am

I see your mistake. In this case you must output ** ** ** (replace every letter of the alphabet by an asterisk). And your second example is not ok, I tried to explain it.

hlchan
New poster
Posts: 7
Joined: Sat May 25, 2002 8:15 am

Judge program

Post by hlchan » Sat Sep 21, 2002 6:36 pm

I submit a program that output nothing, and got accepted with runtime = 0.00s.

: )
Adrian Kuegel wrote:I have now written the special judge program and send it to the admins. If after rejudge you get Wrong answer, you can send me your program, so that I can look, if my judge program or your program is wrong.

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Thu Jun 19, 2003 4:30 am

I'm having trouble coming up with a fast enough algorithm.

I tried a branch-and-bound method which iterates through each word in the input line and tried every word of the same length in the dictionary. If the current decoding is consistent it recurses to the next word in the input, otherwise it bounds the search.

Is there another methodology which is faster?

PJYelton
New poster
Posts: 20
Joined: Fri May 30, 2003 6:56 pm

843 Crypt Kicker

Post by PJYelton » Thu Jul 17, 2003 6:56 pm

I am stumped on how to do this problem within the 10 second limit. The method I have is a recursive function that checks each word against all the words in the dictionary that are the same length and backs up everytime it hits a snag. It works beautifully but unfortunately it times WAY out at only 100 words and considering that the dictionary could be up to 1000 words there is obviously a different way to do this. Any hints or help?

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Thu Jul 17, 2003 7:22 pm

Hi !

An advice given in "Programming Challenges" is to use equivalence classes, using the length of words has you do, but also using repeated letters.
Nevertheless, I haven't tried it.

Post Reply

Return to “Volume 8 (800-899)”