SwitchingGame | Topcoder Archive

Problem Statement

You're playing a game with lamps. There are M lamps in a row. The lamps are numbered 0 through M-1. Initially, all lamps are turned off.

The game consists of N levels. The levels are numbered 0 through N-1. Each level is described by a string of M characters. For each i, character i of that string gives the required state of lamp i. Each of these characters will be either '+', '-', or '?'. Here, '+' means that the lamp must be on, '-' means that the lamp must be off, and '?' means that the lamp may be in either state.

The game is played in turns. Each turn takes one second. In each turn, you may do one of three things:

You may choose any subset of lamps that are all turned off, and turn all of them on.
You may choose any subset of lamps that are all turned on, and turn all of them off.
You may press the big red button that says "Check!".

Whenever you press the button, the current states of all lamps are checked against the requirements of the current level. If all lamps satisfy the requirements, you solved the current level. You win the game by solving all N levels. You must solve the levels in the given order, starting with level 0. Note that the lamps do not reset between levels: you continue playing the next level from the state you had when you solved the previous level.

Return the smallest number of seconds it takes to win the game if you play optimally.

Definition

Class:: SwitchingGame
Method:: timeToWin
Parameters:: String[]
Returns:: int
Method signature:: int timeToWin(String[] states)
(be sure your method is public)

Constraints

states will contain exactly N elements.
N will be between 1 and 50, inclusive.
Each element of states will contain exactly M characters.
M will be between 1 and 50, inclusive.
Each character of states will be '+', '-' or '?'.

Examples

```
{"++--",
 "--++"}
```
```
Returns: 5
```
The following sequence of actions wins the game in five seconds: Turn lamps 0 and 1 on. Press the button to win level 0. Turn lamps 0 and 1 off. Turn lamps 2 and 3 on. Press the button to win level 1 and thus win the game.
```
{"+-++",
 "+-++"}
```
```
Returns: 3
```
Each time you press the button you can only win a single level. Even though levels 0 and 1 are identical, you have to press the button twice in a row to win both of them.
```
{"++",
 "+?",
 "?+",
 "++"}
```
```
Returns: 5
```
Here we can simply turn both lamps on, and then use that configuration to win all four levels.
```
{"+", 
 "?",
 "?",
 "?",
 "-"}
```
```
Returns: 7
```
At some point between winning level 0 and winning level 4 we have to turn the lamp off.

{"+??+++",
 "++??+-",
 "?++??+",
 "?-+-??",
 "??+?++",
 "++-?+?",
 "?++?-+",
 "?--+++",
 "-??-?+"}

Returns: 20

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.