963 - Spelling Corrector

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

Moderator: Board moderators

Post Reply
User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

963 - Spelling Corrector

Post by ImLazy » Sun Jan 20, 2008 11:23 am

Who can give some hints about the algorithm?
I stay home. Don't call me out.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Jan 20, 2008 9:00 pm

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).

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Mon Jan 21, 2008 3:51 am

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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Mon Jan 21, 2008 10:02 am

andmej wrote:what is LCS? :oops:
Longest Common Substring (or Subsequence).
Last edited by ImLazy on Tue Jan 22, 2008 5:27 pm, edited 1 time in total.
I stay home. Don't call me out.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Mon Jan 21, 2008 10:09 am

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?
I stay home. Don't call me out.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Jan 21, 2008 7:15 pm

ImLazy wrote:You mean, for each given word, calculate its penalty with each word in the dictionary?
Yes.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Tue Jan 22, 2008 5:26 pm

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.
I stay home. Don't call me out.

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Post by mpi » Wed Jan 30, 2008 4:01 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 963 - Spelling Corrector

Post by brianfry713 » Thu May 01, 2014 1:04 am

I created a dataset and emailed the admins.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 963 - Spelling Corrector

Post by brianfry713 » Tue Jul 29, 2014 8:42 pm

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.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 963 - Spelling Corrector

Post by brianfry713 » Mon Aug 04, 2014 10:37 pm

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
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 963 - Spelling Corrector

Post by uDebug » Sat Nov 08, 2014 9:57 am

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
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 9 (900-999)”