TopCoder problem "PaintingBoards" used in SRM 390 (Division I Level Two)



Problem Statement

    There are several boards arranged side by side in a straight line. Boards go in order and you can't change the order of boards. The length of the i-th board in the line is boardLength[i] inches. There are also several painters. The i-th painter can paint a one inch length of board in 1/painterSpeed[i] seconds. You can assign jobs to some of painters (not necessarily to all of them). Each painter can be assigned at most a single block of one or more consecutive boards. All the painters start at the same time and work simultaneously. Return the minimal number of seconds needed to paint all the boards.
 

Definition

    
Class:PaintingBoards
Method:minimalTime
Parameters:int[], int[]
Returns:double
Method signature:double minimalTime(int[] boardLength, int[] painterSpeed)
(be sure your method is public)
    
 

Notes

-Painters do not have to be assigned to boards in any particular order. For example, painter 2 can be assigned to boards 1 to 3, while painter 1 is assigned to boards 4 to 5, etc.
-The returned value must be accurate to within a relative or absolute value of 1E-9.
 

Constraints

-boardLength will contain between 1 and 50 elements, inclusive.
-Each element of boardLength will be between 1 and 10000, inclusive.
-painterSpeed will contain between 1 and 15 elements, inclusive.
-Each element of painterSpeed will be between 1 and 10000, inclusive.
 

Examples

0)
    
{5,3,2}
{2,3,5}
Returns: 1.0
Assign painter 3 (1-indexed) to the board of length 5, painter 2 to the board of length 3, and painter 1 to the board of length 2. Each painter will finish in exactly one second.
1)
    
{1,2,1,4,2,1,1}
{1,2,3}
Returns: 2.0
Assign painter 2 (1-indexed) to the first three boards {1, 2, 1}, painter 3 to the next two boards {4, 2}, and painter 1 to the last two boards {1, 1}. Each painter will finish in exactly 2 seconds.
2)
    
{40, 46, 82, 89, 33, 46, 3, 50, 95, 
81, 69, 40, 94, 93, 90, 98, 17, 34, 
45, 18, 93, 28, 43, 38, 35}
{49, 51, 35, 27, 48, 36, 54, 10}
Returns: 4.686274509803922
3)
    
{3,3,20}
{9,1}
Returns: 2.888888888888889
It's better to assign everything to the fast painter and not assign anything to the slow painter.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11124&pm=8516

Writer:

srbga

Testers:

PabloGilberto , Olexiy , Andrew_Lazarev , ivan_metelsky

Problem categories:

Dynamic Programming