Connection Status:
Competition Arena > EllysLights

EllysLights

TCO12 Round 1A · 2012-03-27 · by espr1t

TCO12 Round 1A · 2012-03-27 · by espr1t · Graph Theory
Class Name: EllysLights
Return Type: int
Method Name: getMinimum
Arg Types: (string, vector<string>)
Problem Statement

Problem Statement

Elly's house has a number of light bulbs. Some of them are turned on, some of them are not. She wants to switch all of them off for the upcoming Earth Hour.

Unfortunately, her house has a strange system of light switches. Each switch changes the state of some of the bulbs (possibly none or all of them). This means that if she uses the switch, all bulbs that are connected to it go off if they were on, and go on if they were off. She also knows that each bulb is connected to at most two switches. Help Elly determine what is the minimal number of switches she must use in order to turn off all the lights.

You are given a String initial and a String[] switches. Each character in initial represents one light bulb: if the i-th light bulb (0-based index) is initially on, the i-th character of initial is 'Y', otherwise it is 'N'. Each element of switches represents one switch: if the i-th switch toggles the j-th light bulb, switches[i][j] is 'Y', otherwise it is 'N'.

Find and return the smallest nonnegative integer X such that there is a sequence of X switches such that if Elly toggles those switches in the given order, all light bulbs will be turned off at the end. If no such X exists, return -1.

Notes

  • It is possible that none or all of the bulbs are turned on initially.
  • Elly is allowed to toggle the same switch more than once.

Constraints

  • initial will contain between 1 and 50 characters, inclusive.
  • Each character of initial will be either 'Y' or 'N'.
  • switches will contain between 1 and 50 elements, inclusive.
  • Each element of switches will contain the same number of characters as initial.
  • Each character of each element of switches will be either 'Y' or 'N'.
  • For each index of initial there will be at most two elements of switches that will have 'Y' at that index.
Examples
0)
"YNYNNN"
{"YNNYNY", "NYYYNN", "YNYNYN", "NNNNYN", "NYNNNY"}
Returns: 2

There are multiple ways how to turn off all the lights. For example, she can first use switch 0, then switch 4, and finally switch 1. The shortest solutions only use two switches. For example, it is enough to flip the switch 2 followed by the switch 3.

1)
"YNYNYN"
{"NNNNNN", "YYYYYY", "NYNNNN", "NNNYNN", "NNNNNY"}
Returns: 4

Some of the switches might change the state of none or all of the bulbs. Some of the bulbs might be influenced by less than 2 switches.

2)
"YYN"
{"YNY", "NYN"}
Returns: -1

Sometimes there might be no way to switch off all the bulbs. In this case return -1.

3)
"NNYNYNYYYNNYYYYN"
{"NYNYNYNYNYNYNYNY",
 "YNYNYNYNYNYNYNYN",
 "NNNNNNNNNNNNNNNN",
 "YNNNNNNNNNNNNNNN",
 "NYNNNNNNNNNNNNNN",
 "NNYNNNNNNNNNNNNN",
 "NNNYNNNNNNNNNNNN",
 "NNNNYNNNNNNNNNNN",
 "NNNNNYNNNNNNNNNN",
 "NNNNNNYNNNNNNNNN",
 "NNNNNNNYNNNNNNNN",
 "NNNNNNNNYNNNNNNN",
 "NNNNNNNNNYNNNNNN",
 "NNNNNNNNNNYNNNNN",
 "NNNNNNNNNNNYNNNN",
 "NNNNNNNNNNNNYNNN",
 "NNNNNNNNNNNNNYNN",
 "NNNNNNNNNNNNNNYN",
 "NNNNNNNNNNNNNNNY"}
Returns: 6

There are 9 lit bulbs initially. We can turn them off one by one, but it will be faster to use one of the complex switches and then to toggle the ones that are still lit.

4)
"NYNYNYYYNNYYYNNYNNYYYYYNNYNYYYY"
{"NNNNNNNNNNNNNNNNNNYNNNNNNNNNNNN",
 "NNNNNNNNYNNNYNNNNYYNYNNNNYNNNNN",
 "NNNNNNNNNYNNNNNNNNNNNNYNNNNNNNN",
 "NNNNNYNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NYNNNNNNNNNNNNYNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNYYNNNNNNNNNNNNNNNY",
 "NNNNNNYNNNNNNNNNNNNYNNNNNYNNNNN",
 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "YNNNNNNNNNNNNNNNNNNYNNNNNNNNNNN",
 "NNNYNNNNNNNNNNNNNNNNNNNYYNNNNNN",
 "NYNNNNNNNNNNYNNNNNNNNNNNNNNNYNN",
 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNYNNNNNNNNNNNNNNNNNNNNNNNNY",
 "NNNNNNNNNNYNNNNNNNNNYYYNNNNNNNN",
 "NNNYNNNNNNNNNNNNNNNNNNNNNNNYNNN",
 "NNNNNNNNYNNNNNNNNNNNNNNNYNNNNNN",
 "YNNNYNNNNNNNNNNNNNNNNNNNNNNYNNN",
 "NNNNNNNNNNYNNNNNNNNNNNNNNNNNNNN",
 "NNNNYNNYNNNNNNNNNNNNNNNNNNNNNNN",
 "NNNNNNNYNNNYNNNYNNNNNNNNNNNNNYN"}
Returns: 7

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

Coding Area

Language: C++17 · define a public class EllysLights with a public method int getMinimum(string initial, vector<string> switches) · 117 test cases · 2 s / 256 MB per case

Submitting as anonymous