## 709 - Formatting Text

Moderator: Board moderators

j0ker
New poster
Posts: 1
Joined: Fri Sep 27, 2002 9:04 pm

### 709 - Formatting Text

Is there a faster way to solve this problem? My algorithm was taken from a book and it takes O(n^3) to run. I got accepted in 3.470secs but I

kostik
New poster
Posts: 2
Joined: Fri May 14, 2004 8:48 am

### 709 Formatting Text

Which algorithm for this problem? pleaze HELP !

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
I think this problem is fairly straight forward. A hint would be, for each word, see how good you can do if the message started with just that word.

Also remember to satisfy the condition:
If there are several ways to format a paragraph with the same badness, use the following algorithm to choose which one to output: Let A and B be two solutions. Find the first gap which has not the same length in A and B. Do not output the solution in which this gap is bigger.

fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

### Re: 709 - Formatting Text

Got WA....
Do anyone have tricky I/O for this problem?

Landertxu
New poster
Posts: 4
Joined: Tue Feb 14, 2006 9:39 pm

### Re: 709 - Formatting Text

I don't understand wich should be the output for:

5
La la la

It could be:

La la
la

or:

La
la la

I don't undestand if the newline is considered a "gap" or not, and if it's, if is taken as a 1-gap or as a oo-gap. Could you help me?

Also, some tricky output wouldn't hurt

fushar
New poster
Posts: 26
Joined: Fri Apr 03, 2009 12:09 pm
Location: Indonesia
Contact:

### Re: 709 - Formatting Text

My AC code produces:

Code: Select all

``````La la
la
``````