Page 1 of 1

963 - Spelling Corrector

Posted: Sun Jan 20, 2008 11:23 am
by ImLazy
Who can give some hints about the algorithm?

Posted: Sun Jan 20, 2008 9:00 pm
by 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).

Posted: Mon Jan 21, 2008 3:51 am
by andmej
Excuse me for the newbiesness, I know DP means Dynamic programming, but what is LCS? :oops:
I'm I sorry if it this a stupid question, I just want to learn.

Posted: Mon Jan 21, 2008 10:02 am
by ImLazy
andmej wrote:what is LCS? :oops:
Longest Common Substring (or Subsequence).

Posted: Mon Jan 21, 2008 10:09 am
by ImLazy
Jan wrote: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?

Posted: Mon Jan 21, 2008 7:15 pm
by Jan
ImLazy wrote:You mean, for each given word, calculate its penalty with each word in the dictionary?
Yes.

Posted: Tue Jan 22, 2008 5:26 pm
by ImLazy
Jan wrote: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.

Posted: Wed Jan 30, 2008 4:01 pm
by 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 :(

Re: 963 - Spelling Corrector

Posted: Thu May 01, 2014 1:04 am
by brianfry713
I created a dataset and emailed the admins.

Re: 963 - Spelling Corrector

Posted: Tue Jul 29, 2014 8:42 pm
by 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.

Re: 963 - Spelling Corrector

Posted: Mon Aug 04, 2014 10:37 pm
by 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

Re: 963 - Spelling Corrector

Posted: Sat Nov 08, 2014 9:57 am
by 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