VHSRecording | Topcoder Archive

Problem Statement

As much as he would like to, Robert cannot afford to spend all day watching TV. He often has to fly out of town and he likes to record his favorite shows on VHS tape for later viewing.

He sometimes has so many shows to record that they don't all fit on one tape. Luckily, his VCR supports recording in LP (long play) mode, in which a recording is made at a lower quality, but uses half as much tape as in SP (standard play) mode. This allows Robert to fit more shows on his tape, but still not necessarily all. Obviously, when he's not home, he cannot change the tape between shows, so he has to decide in advance which shows he will tape.

For this he has devised a point system in which he judges how much each show is worth to him. For each show, he awards some number of points if that show is among the shows chosen to be recorded. The reduction in quality when recording in LP mode is more significant with some shows and less with others. Because of this, a show will contribute one amount of points if it is recorded in SP mode, and a different amount if it is recorded in LP mode. For the show to contribute points, it needs to be taped in its entirety (recording only part of a show doesn't give points).

You will be given an int tapeCapacity and three int[]s of the same length, showLength, pointsSP and pointsLP. tapeCapacity is the number of minutes that can be recorded on the tape in SP mode. Elements at the same index in the three int[]s describe one show Robert would like to record - its length (in minutes), the amount of points Robert awards if it is recorded in SP mode, and points he awards if it is recorded in LP mode. Return the maximum number of points Robert can achieve by choosing which shows to record and in which modes to record them.

Definition

Class:: VHSRecording
Method:: mostPoints
Parameters:: int, int[], int[], int[]
Returns:: int
Method signature:: int mostPoints(int tapeCapacity, int[] showLength, int[] pointsSP, int[] pointsLP)
(be sure your method is public)

Notes

Shows do not overlap. When the tape is long enough, Robert can record all shows.

Constraints

tapeCapacity will be between 1 and 600, inclusive.
showLength, pointsLP and pointsSP will each contain between 1 and 50 elements, inclusive.
showLength, pointsLP and pointsSP will contain the same number of elements.
Each element of showLength will be between 1 and 600, inclusive.
Each element of pointsSP and pointsLP will be between 1 and 100, inclusive.
pointsSP[i] will be greater than or equal to pointsLP[i], for all i.

Examples

```
50
```
```
{10, 15, 20}
```
```
{5, 2, 6}
```
```
{4, 1, 5}
```
```
Returns: 13
```
The three shows are 45 minutes long altogether, so we can fit all of them in SP quality.
```
30
```
```
{20, 20}
```
```
{5, 6}
```
```
{2, 4}
```
```
Returns: 9
```
The tape is just long enough to fit one show in SP mode and the other in LP. The better option is to tape the first show in SP and the second in LP.
```
60
```
```
{50, 40}
```
```
{10, 3}
```
```
{4, 2}
```
```
Returns: 10
```
We can record both shows in LP mode, but it is worth more to record just the first show in SP.

{20, 21, 22}

{6, 7, 3}

{1, 2, 1}

Returns: 13

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.