FourLamps | Topcoder Archive

Problem Statement

Fox Ciel has n lamps. The lamps are arranged in a row from the left to the right, and they are numbered 0 through n-1 in that order. You are given a String init with n characters that describes the initial state of the lamps: init[i] is '1' if lamp i is initially turned on, or '0' if it is initially turned off.

You are also given an int k. Below we describe an operation. Ciel can use that operation at most k times. Compute and return the number of different final states she can obtain. (Two states of lamps are different if there is a lamp that is on in one state but off in the other. The initial state is always one of the possible final states.)

The operation looks as follows:

Ciel chooses four consecutive lamps such that either exactly one of them is on, or exactly one of them is off. (If there is no such group of lamps, Ciel cannot perform any more operations.)
Ciel divides all lamps into a left part and a right part so that the division point is in the middle of the four lamps chosen in the previous step. In other words, if the four chosen lamps are x, x+1, x+2, x+3, the left part is {0, 1, ..., x+1} and the right part is {x+2, ..., n-2, n-1}.
Ciel chooses either the left part or the right part.
Ciel toggles all lamps in the chosen part. (Toggling a lamp means switching it to the opposite state.)

Definition

Class:: FourLamps
Method:: count
Parameters:: String, int
Returns:: long
Method signature:: long count(String init, int k)
(be sure your method is public)

Constraints

init will contain between 4 and 50 characters, inclusive.
Each character in init will be '0' or '1'.
k will be between 1 and 1,000,000,000, inclusive.

Examples

```
"0001"
```
```
2
```
```
Returns: 4
```
As there are only four lamps, there is only one group of four consecutive lamps. If these four lamps satisfy the constraint, the left part will be lamps {0,1} and the right part will be lamps {2,3}. If Ciel performs zero operations, the only possible final state is the initial state "0001". If Ciel performs one operation, she can either toggle the left part or the right part. Toggling the left part produces the state "1101", toggling the right part produces the state "0010". Note that both states produced by the first operation still have the property that enables us to do the next operation: exactly one of the four lamps is off in "1101", and exactly one of them is on in "0010". What states can we reach by performing two operations? Toggling the left part and then the left part again will bring us back to "0001". Toggling the right part twice has the same effect. Toggling the left part and then the right part produces the final state "1110". Toggling the right half and then the left half leads to that state as well. In total there are four possible final states: "0001", "1101", "0010", "1110".
```
"0001"
```
```
1000000000
```
```
Returns: 4
```
In the previous scenario increasing k to 10^9 does not change the answer. The following operations won't produce any new states of the lamps.
```
"1010"
```
```
100
```
```
Returns: 1
```
This time Ciel cannot make any operation because there are no four consecutive lamps with the required property. Thus, the only possible final state is the initial state.
```
"000111"
```
```
3
```
```
Returns: 12
```
These are the states we can get: "000111" "110111" "001000" "111011" "000100" "111000" "001111" "110000" "001011" "110100" "000011" "111100"
```
"00000010000"
```
```
5
```
```
Returns: 58
```

"10101100101010001011000100101000100001101"

Returns: 100256132848

Watch for overflow.

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.