843 - Crypt Kicker

[dh3014]

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]

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

[dh3014]

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]

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]

quite thanks

[Adrian Kuegel]

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]

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]

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

[rfcotta]

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]

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]

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]

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

: )

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]

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]

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]

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.