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

[brianfry713]

I created a dataset and emailed the admins.

[brianfry713]

This has been changed to a multiple input problem.
If you get PE, make sure you copy all whitespace from the input to the output. It looks there are now extra whitespace characters between words or at the beginning or end of a line.

[brianfry713]

Input:

Code: Select all

49
abfuz
b
bttl
ceqhywnq
d
daqlkcbni
dpxf
ezcxk
fgsuahz
fsgi
gsqqhegi
kjvas
knrt
lbubud
ll
lolzbcbf
mgfbby
moy
mq
mtmfn
n
naofqayjk
ndb
nrp
oc
pu
pzn
q
qkh
qmtrhocg
rkkorjmbp
rmgoaza
rqbyse
rqtnsn
rxxfxw
s
smmr
szwsccr
t
ulggietw
uyfmxw
vlwt
vuczjzg
xryo
yaswa
ye
zi
zmxopmods
ztsq
51
i xszama rpqlrrxs petdli knkzjpjv bu pwkgldtcu wuib lmx wmavv
gshhowwkj xmy i yeyztk rak ahbsov vmyu hawvaxdp knwdzkubu c
d paynm jlfjha gf epqavskrt txkyuzz onsxyx hz q wuyowtg
mapgz etbfppv ptgydhvt tnoh jquvskbrj n peckmtgu lcogqhv q pgb
alo wyhjp nczgi zvwnbou w clt xtqnnnlwy kndjt fskdhltb pnlagpyc
lrwzo

AC output:

Code: Select all

zi s nrp d nrp b pu b ll mq
s moy zi ye b b moy yaswa ndb oc
d pzn ll b knrt t moy zi q t
pzn b d n qkh n pu q q b
ll ye zi b b t n knrt ndb nrp
xryo

[uDebug]

Copying and pasting the sample input seems to omit the newline between cases. Here's the correct version of the sample input

Code: Select all

5
ate
carrot
rabbit
the
white
6
the white rabit ate ate carott

20
a
abbey
adapted
ago
almost
but
clumsy
had
he
joined
living
manuel
monk
not
of
that
the
to
way
year
22
the clumsy momk manuel had joined the abey almost a
year ago but he had not adapted to that way
of leaving