Page 1 of 1
289 - A Very Nasty Text Formatter
Posted: Mon May 10, 2004 8:07 pm
by Adrian Kuegel
Can someone explain me this problem?
You should do as few hyphenations as possible. However, if it is impossible to justify a line of the text, output it left-justified.
Does it mean, that I should minimize the number of lines that can't be printed with length n, and then minimize the number of hyphenations?
If yes, why the output for last sample test case is not:
Code: Select all
This
is a-
n ex-
ample
of a
para-
graph
whic-
h is
pret-
typr-
inte-
d on
a r-
ow w-
ith a
leng-
th of
five.
The only way how I can reproduce the sample output is by using greedy, but I got WA when I submitted a program with it. Did someone solve this problem with DP, or is greedy the algorithm that is wanted here?
Posted: Mon May 10, 2004 8:56 pm
by Adrian Kuegel
Well, it seems greedy is the wanted solution, at least I got Accepted now.
Here is a test case where my first greedy program failed, perhaps it will help someone else, too:
4 Te s t.
Output is:
Te s
t.
Posted: Tue Jun 01, 2004 8:01 pm
by ..
Thanks for your post.
Once you tell the word "greedy", I suddednly understand what it is asking.
Before that, I have no way to solve it as I even don't know what it requires....
Posted: Thu Jun 03, 2004 10:38 am
by little joey
Yes, thanks.
The sentence "You should do as few hyphenations as possible." is wrong, because the only way to achieve that is DP. But than there would be a better solution for the second example:
Code: Select all
This is an<CR>
example of<CR>
a paragraph<CR>
which is<CR>
prettyprinted<CR>
on a row with a<CR>
length of<CR>
fifteen.<CR>
which has zero hyphens.
I guess the sentence should read "You should only hyphenate when you are forced to", or something like that, altough it doesn't clear matters that much.
Greed is indeed the method, and the problem can be solved by using a buffer of only n+1 characters.
Not so much a 'nasty' text formatter, but rather a 'nasty' problem description.
Posted: Thu Jun 03, 2004 11:36 am
by Adrian Kuegel
I just looked at the ps file. It probably shows the original problem description, and there is only one sample test case, and this test case is also possible to reach with DP (minimize number of hyphenations).
I fear that the one who generated the judge input/output made a mistake.