Connection Status:
Competition Arena > LightbulbGame

LightbulbGame

TCO19 SRM 738 · 2018-09-29 · by misof

TCO19 SRM 738 · 2018-09-29 · by misof · Dynamic Programming, Math
Class Name: LightbulbGame
Return Type: int
Method Name: countWinningMoves
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Yvonne and Zed have a rectangular array of lightbulbs. Each lightbulb is either on or off. You are given the String[] board that describes their current states: '1' represents on, '0' off.

Yvonne and Zed use the array to play a game. They take alternating turns, Yvonne starts. In each turn the active player does the following:

  1. The player must choose a lightbulb L that is currently on. If the player cannot do that, they lose the game.
  2. The player must turn lightbulb L off.
  3. The player then may choose another lightbulb L'. This lightbulb must be either somewhere to the right of L (in the same row) or somewhere downwards from L (in the same column).
  4. If the player did choose L', they now must toggle it. (Turn it on if it was off, or vice versa.)

For the given board, count all winning moves for the player whose turn it is.

Constraints

  • board will contain between 1 and 50 elements, inclusive.
  • Each element of board will contain between 1 and 50 characters, inclusive.
  • All elements of board will have the same length.
  • Each character in board will be either '1' or '0'.
Examples
0)
{"000",
 "000",
 "000"}
Returns: 0

All lightbulbs are off. The player immediately loses the game.

1)
{"0000",
 "0100",
 "0000"}
Returns: 1

A single lightbulb is on. The only winning move is to turn it off and to refuse to toggle another lightbulb.

2)
{"00000",
 "01001",
 "00000"}
Returns: 1

Two lightbulbs are on. As they are in the same row, the current player can win by choosing the lightbulb at row 1, column 1 (using 0-based indices) as L and then the other lightbulb as the L' to toggle. It can be shown that there are no other winning moves from this situation.

3)
{"10",
 "01"}
Returns: 0

Two lightbulbs are currently on and two are off. We can work out all possible ways this game can play out to see that if the opponent plays optimally, the current player will lose regardless of the first move they make.

4)
{"1111",
 "1110"}
Returns: 3

Submissions are judged against all 87 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LightbulbGame with a public method int countWinningMoves(vector<string> board) · 87 test cases · 2 s / 256 MB per case

Submitting as anonymous