Connection Status:
Competition Arena > PaintingBoards

PaintingBoards

SRM 390 · 2008-02-02 · by srbga

SRM 390 · 2008-02-02 · by srbga · Dynamic Programming
Class Name: PaintingBoards
Return Type: double
Method Name: minimalTime
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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)
{90, 5, 3, 17, 2, 27, 84, 73, 67, 2, 33, 71, 31, 40, 99, 35, 81, 48, 57, 68, 46, 51, 92, 35, 24, 9, 87, 43, 41, 67, 85, 23, 40, 32, 22, 85, 6, 60, 75, 94, 32, 97, 54, 23, 1, 54, 58, 6, 95, 23}
{4, 4, 13, 10, 5, 17, 7, 9, 4, 12, 13, 4, 6, 12, 1}
Returns: 20.647058823529413
3)
{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
4)
{4280, 6931, 4927, 8275, 4946, 8723, 693, 6638, 8418, 2068, 514, 5773, 9517, 6841, 3480, 6809, 454, 4464, 6481, 7451, 7609, 1573, 3463, 1136, 1168, 5335, 4143, 5260, 6581, 8535, 8802, 5067, 8021, 9644, 5434, 514, 4461, 612, 7909, 5811, 9108, 4293, 6633, 559, 6149, 7890, 5717, 2598, 5815, 4505}
{918, 6710, 1327, 7549, 997, 403, 8898, 7262, 4808, 3930, 166, 194, 709, 9172,1958}
Returns: 4.897072459928467
13)
{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.

Submissions are judged against all 218 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PaintingBoards with a public method double minimalTime(vector<int> boardLength, vector<int> painterSpeed) · 218 test cases · 2 s / 256 MB per case

Submitting as anonymous