MaximumPenalty | Topcoder Archive

Problem Statement

We have N jobs to complete. The jobs are numbered from 0 to N-1. Job i requires L[i] seconds of work. At any moment we can only work on one of the jobs.

As is usually the case, each job should be completed as soon as possible: the longer it takes, the worse the penalty will be. If job i is completed after t seconds, the penalty is calculated as follows:

penalty(i, t) = P[4i+0] * t⁰ + P[4i+1] * t¹ + P[4i+2] * t² + P[4i+3] * t³

All coefficients in P are nonnegative, and therefore the penalty is nondecreasing in time.

The penalty of the whole schedule is the maximum (not the sum!) over all jobs. Your goal is to minimize this penalty.

Clearly it doesn't pay off to jump back and forth between jobs: there is always an optimal schedule in which whenever you start working on a problem, you work on it until you complete it. Such a schedule can then be described by a list of job numbers in the order in which you should perform them. Find any such optimal schedule and return a int[] with the corresponding job order. Any optimal solution will be accepted.

Definition

Class:: MaximumPenalty
Method:: schedule
Parameters:: int[], int[]
Returns:: int[]
Method signature:: int[] schedule(int[] L, int[] P)
(be sure your method is public)

Notes

For the constraints specified below the largest possible penalty fits into a signed 64-bit integer.

Constraints

N will be between 1 and 1000, inclusive.
L will contain N elements.
Each element of L will be between 1 and 100, inclusive.
P will contain 4*N elements.
Each element of P will be between 0 and 8000, inclusive.

Examples

```
{7, 4, 1}
```
```
{0, 0, 0, 1,
 0, 0, 2, 0,
 0, 3, 0, 0}
```
```
Returns: {0, 2, 1 }
```
We have a long job with penalty function t^3, a medium job with penalty function 2t^2, and a short job with penalty 3t. If we do them in the order {0, 2, 1}, we will finish job 0 at 7 seconds, job 2 at 8 seconds, and then job 1 at 12 seconds. The individual penalties will be 7^3 = 343, 2*8^2 = 128, and 3*12 = 36. Thus, the overall penalty will be 343. This is optimal. There is one other optimal solution that would also be accepted.

{7, 4, 2, 5}

{47, 0, 0, 0,
 47, 0, 0, 0,
 47, 0, 0, 0,
 47, 0, 0, 0}

Returns: {3, 2, 1, 0 }

All jobs have the same constant penalty. The order in which we do them does not matter.

```
{7, 4, 2, 5}
```
```
{0, 47, 0, 0,
 0, 47, 0, 0,
 0, 47, 0, 0,
 0, 47, 0, 0}
```
```
Returns: {3, 2, 1, 0 }
```
All jobs have the same linear time penalty. Regardless of the order in which we perform them the penalty for the last job finished will always be 47*18, so again the order does not matter.

{7, 4, 2, 5}

{0, 7, 8,  15,
 1, 6, 9,  14,
 2, 5, 10, 13,
 3, 4, 11, 12}

Returns: {0, 1, 2, 3 }

Any order in which job 3 is performed last is optimal.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.