Connection Status:
Competition Arena > LightSwitches

LightSwitches

SRM 306 · 2006-06-08 · by soul-net

SRM 306 · 2006-06-08 · by soul-net · Greedy, Math
Class Name: LightSwitches
Return Type: long
Method Name: countPossibleConfigurations
Arg Types: (vector<string>)
Problem Statement

Problem Statement

In a ballroom, there are some light bulbs and some switches that control those bulbs. However, the switches and the bulbs are not related in a logical way. Each switch is connected to a subset of the bulbs, and when a switch is flipped, all the bulbs connected to that switch change state (the ones that were off are turned on, and the ones that were on are turned off). Bulbs that are not connected to the flipped switch remain as they were.

The states of all the bulbs in the room can be described as a configuration of lights. If there are N bulbs, there are 2N possible configurations. Two configurations are distinct if a bulb in one configuration has a different state than that same bulb in the other configuration.

You will be given the connections between the switches and bulbs as a String[] switches. The jth character of the ith element of switches is 'Y' if the ith switch is connected to the jth bulb, and 'N' otherwise. All the bulbs are initially off. Return the number of distinct configurations of lights that can be achieved using this setup.

Constraints

  • switches will have between 1 and 50 elements, inclusive.
  • Each element of switches will have exactly N characters, where N is between 1 and 50, inclusive.
  • Each character of each element of switches will be 'Y' or 'N'.
Examples
0)
{"YYN",
 "NNY",
 "YYY",
 "NNN"}
Returns: 4

In this example, there are three bulbs and four switches. The first switch is connected to the first two lights, the second switch is connected to the third light, the third switch is connected to all three lights, and the fourth switch is connected to nothing. The possible configurations are (- for OFF and + for ON): - - - The initial configuration. + + - This can be achieved by flipping the first switch. - - + This can be achieved by flipping the second switch. + + + This can be achieved by flipping the first switch and then the second switch.

1)
{"NNNNYYYNYYNYYYYYNYY"}
Returns: 2

There are only two possible configurations here - the initial configuration where all the bulbs are off, and the configuration that results from flipping the switch once.

2)
{"YNNNN",
 "NYNNN",
 "NNYNN",
 "NNNYN",
 "NNNNY"}
Returns: 32
3)
{"NYNYNYN",
 "YNYNYNY",
 "YYNNNYN",
 "NNNYNYN",
 "YYYYYNN",
 "YNNNNYN"}
Returns: 32
4)
{"YYYY","YNYN","NYNY","NNNN","YNYN","NYNY"}
Returns: 4
6)
{"YNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNN"}
Returns: 1073741824

Each of the first 30 bulbs can be turned on and off individually while the remaining 20 bulbs are impossible to turn on. Any combination of states among the first 30 bulbs is possible, so the number of configurations is 230.

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

Coding Area

Language: C++17 · define a public class LightSwitches with a public method long long countPossibleConfigurations(vector<string> switches) · 117 test cases · 2 s / 256 MB per case

Submitting as anonymous