963 - Spelling Corrector

[ImLazy]

Who can give some hints about the algorithm?

[Jan]

You can apply dp. To be more specific you can use LCS (with minor changes).
But I still dont know whether the judge data is present or not (for this problem).

[andmej]

Excuse me for the newbiesness, I know DP means Dynamic programming, but what is LCS?
I'm I sorry if it this a stupid question, I just want to learn.

[ImLazy]

what is LCS?

Longest Common Substring (or Subsequence).

[ImLazy]

You can apply dp. To be more specific you can use LCS (with minor changes).

You mean, for each given word, calculate its penalty with each word in the dictionary?

[Jan]

You mean, for each given word, calculate its penalty with each word in the dictionary?

Yes.

[ImLazy]

But I still don't know whether the judge data is present or not (for this problem).

It seems like you said. I kept getting Runtime Error. But when I submitted a code with only an empty main function, it was Accepted. There is quite something wrong with the test data of this problem.

[mpi]

What a pity! This seemed a very interesting problem. I've been waiting long for a spelling correction problem in order to apply the Levenshtein Distance algorithm efficiently, but in this one anyone can get AC with an empty main function