TopCoder problem "WhiteSpaceEditing" used in SRM 499 (Division I Level Two)



Problem Statement

    You want to type a document containing only spaces and new lines. Let SP and NL denote a space character and a new line character, respectively. You are given a int[] lines describing the desired document. The elements of lines represent the number of SP characters in each line, in order. Each line must end with a NL character. In other words, the document should look like this: lines[0] SP characters, followed by a NL, followed by lines[1] SP characters, followed by a NL, ..., lines[N-1] SP characters, followed by a NL (where N is the number of elements in lines).



The editor has a cursor, which can be positioned between two adjacent characters or at the beginning or end of the document. You can move this cursor freely.



The editor has three special keys:
  • SPACE: inserts a SP at the position of the cursor.
  • DELETE: deletes a SP character immediately to the right of the cursor. This key cannot be used if the character to the right of the cursor is a NL.
  • RETURN: inserts a NL followed by some number of SP characters. This key can only be used when the character immediately to the right of the cursor is a NL. The number of SP characters that get inserted is equal to the number of SP characters in the line where the cursor is. For example, if the document is "SP NL SP SP NL SP SP SP NL", and the cursor is immediately to the left of the second NL, it will become "SP NL SP SP NL SP SP NL SP SP SP NL" after pressing RETURN.
The document initially contains nothing but a single NL character. Return the minimum number of times you must press SPACE, DELETE or RETURN to complete the document.
 

Definition

    
Class:WhiteSpaceEditing
Method:getMinimum
Parameters:int[]
Returns:int
Method signature:int getMinimum(int[] lines)
(be sure your method is public)
    
 

Constraints

-lines will contain between 1 and 50 elements, inclusive.
-Each element of lines will be between 0 and 1,000,000, inclusive.
 

Examples

0)
    
{ 3, 2, 3 }
Returns: 6
You can edit the document as follows:
  • NL
  • SP NL
  • SP SP NL
  • SP SP SP NL
  • SP SP SP NL SP SP SP NL
  • SP SP SP NL SP SP SP NL SP SP SP NL
  • SP SP SP NL SP SP NL SP SP SP NL
1)
    
{ 0 }
Returns: 0
You have to do nothing.
2)
    
{ 1, 2, 4 }

Returns: 6
3)
    
{ 250, 105, 155, 205, 350 }

Returns: 499

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14428&pm=11328

Writer:

lyrically

Testers:

PabloGilberto , ivan_metelsky , nika

Problem categories:

Dynamic Programming, Greedy