BrightLamps | Topcoder Archive

Problem Statement

N lamps are arranged in a line. The lamps are numbered 0 through N-1 from left to right.

You are given a String init describing the initial state of the lamps. If the i-th (0-based) character of init is '1', the lamp i is initially turned on. If the i-th character of init is '0', the lamp i is initially turned off. You are also given a int[] a. When the lamp i is turned on, the brightness of the lamp is a[i]. When the lamp i is turned off, the brightness of the lamp is zero.

Toastman wants to maximize the total brightness of these lamps. He is allowed to toggle the states of some lamps according to the following rules: In each step, he can choose K consecutive lamps and toggle all their states. Return the largest possible total brightness Toastman can produce by making zero or more consecutive steps.

Definition

Class:: BrightLamps
Method:: maxBrightness
Parameters:: String, int[], int
Returns:: int
Method signature:: int maxBrightness(String init, int[] a, int K)
(be sure your method is public)

Constraints

init will contain between 1 and 2500 characters, inclusive.
Each character in init will be either '0' or '1'.
The number of elements in a will be the same as the number of characters in init.
Each element of a will be between 1 and 1000, inclusive.
K will be between 1 and the number of characters in init, inclusive.

Examples

```
"011"
```
```
{3, 2, 4}
```
```
2
```
```
Returns: 7
```
The optimal solution is to toggle the states of the first two lamps. The total brightness will then be 3+0+4 = 7.

"0010100101"

{1, 1, 1, 3, 4, 3, 4, 5, 1, 5}

Returns: 28

Here you can turn on all lamps.

"1111111111"

{5, 5, 3, 3, 4, 3, 5, 1, 1, 3}

Returns: 33

You are allowed not to perform any operations.

```
"0010000001"
```
```
{8, 3, 10, 8, 3, 7, 4, 6, 3, 10}
```
```
4
```
```
Returns: 55
```
In each optimal solution of this test case some lamps have to be toggled multiple times.

"00001001010101100001100000010000011001000000001011"

{99, 29, 22, 50, 17, 49, 50, 54, 43, 29, 30, 33, 38, 53, 71, 48, 82, 25, 62, 93, 90, 64, 43, 95, 68,
35, 79, 11, 13, 47, 51, 44, 35, 55, 4, 34, 7, 10, 25, 38, 29, 58, 36, 34, 77, 90, 37, 58, 20, 20}

Returns: 2068

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.