TopCoder problem "Lister" used in SRM 196 (Division I Level Three)



Problem Statement

    A listing of names can be arranged in rows and columns to make it compact. We want our listing to be arranged alphabetically in column major order (e.g. the first column should have all the earliest words in the list). Words should be left justified within their column. Each column has a fixed width, which may differ from the width of other columns. Each row should have a name in each column, except the last row, which may have no names in its final column(s).

Our list will be printed out row by row, with spaces inserted to position the names within each row properly. Each row must contain exactly pageWidth characters (including spaces). In order to avoid run-together, we require that only spaces can appear in the print position just prior to the start of a column. This applies even to the last row (where the final columns may contain no names).

Create a class Lister that contains a method doList that is given pageWidth and a String[] names and that returns the optimal listing as a String[] giving the rows to be printed (in order from top to bottom). Each element in the return should contain exactly pageWidth characters. Use the space character ' ' in your listing to position the names within each row (and to pad each row to pageWidth characters).

A listing is "optimal" if it has as few rows as possible. Among listings with the minimal number of rows, choose the one whose rightmost non-space character is as far to the left as possible. If multiple listings are still equally "optimal" choose the one with the fewest columns.

 

Definition

    
Class:Lister
Method:doList
Parameters:int, String[]
Returns:String[]
Method signature:String[] doList(int pageWidth, String[] names)
(be sure your method is public)
    
 

Constraints

-pageWidth will be between 10 and 80 inclusive.
-names will contain between 1 and 50 elements inclusive.
-Each element of names will contain between 1 and pageWidth characters inclusive.
-Each element of names will contain only lowercase letters 'a'-'z'.
 

Examples

0)
    
10
{"bob","abernathy","x"}

Returns: { "abernathy ",  "bob       ",  "x         " }
Any column containing "abernathy" cannot be adjacent to another column since even a one-character name would be too much to avoid run-together and fit on the page (spaces shown as '.'):
      abernathy.
      bob.......
      x.........
1)
    
11
{"bob","abernathy","x"}
Returns: { "abernathy x",  "bob        " }
There is just enough page width to get abernathy and x on the same row and keep them from running together, producing the following listing (spaces shown as '.'):
      abernathy.x
      bob........
2)
    
10
{"bob","a","x"}
Returns: { "a bob x   " }
3)
    
10
{"x","teddy","andy"}
Returns: { "andy  x   ",  "teddy     " }
Note that there are 2 spaces between "andy" and "x" in the listing. It would be illegal to have only 1 space, since then the 'y' in "teddy" would occupy the print position just prior to the second column of names (spaces shown as '.'):
      andy..x...
      teddy.....
4)
    
33
{"g","babec","bafffebe","bffaf",
 "decdgfgcbc","bacfeddea","g","deecgabcg","c"}
Returns: 
{ "babec     bffaf decdgfgcbc g     ",
 "bacfeddea c     deecgabcg  g     ",
 "bafffebe                         " }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2825

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5071&pm=2825

Writer:

dgoodman

Testers:

zoidal , lbackstrom , brett1479

Problem categories:

Dynamic Programming, String Manipulation