Connection Status:
Competition Arena > SwitchesAndLamps

SwitchesAndLamps

TCO12 Round 2A · 2012-03-27 · by rng_58

TCO12 Round 2A · 2012-03-27 · by rng_58 · Math, Simple Search, Iteration
Class Name: SwitchesAndLamps
Return Type: int
Method Name: theMin
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

There are N switches and N lamps in Cucumberman's house. Each switch is connected to a single lamp. Different switches are connected to different lamps. Switches are numbered 0 through N-1. Lamps are also numbered 0 through N-1, but not necessarily in the same order as their corresponding switches. Switches and lamps have two states: ON and OFF. When a switch is in the ON state, the lamp connected to the switch is ON. When a switch is in the OFF state, the lamp connected to the switch is OFF.

Cucumberman decided to perform some experiments in order to figure out the connection between switches and lamps. In each experiment he first sets the states of all switches as he wants to, and then he writes down the states of all lamps.

He has already performed some experiments. You are given the results in two String[]s switches and lamps. If the j-th character of the i-th element of switches is 'Y', the j-th switch was ON in the i-th experiment. If the j-th character of the i-th element of switches is 'N', the j-th switch was OFF in the i-th experiment. lamps gives the information of lamps in the same format.

If the results of experiments are inconsistent, return -1. (I.e., return -1 if no way of assigning switches to lamps matches all the experiments.) Otherwise, return the minimal number of additional experiments required to figure out the connection between switches and lamps. In other words, return the smallest nonnegative integer X with the following property: It is possible to design X additional experiments in such a way that after Cucumberman executes them and tells you the results you will surely be able to match each switch to its corresponding lamp.

Constraints

  • switches will contain between 1 and 50 elements, inclusive.
  • Each element of switches will contain between 1 and 50 characters, inclusive.
  • Each element of switches will contain the same number of characters.
  • lamps will contain the same number of elements as switches.
  • Each element of lamps will contain the same number of characters, and it will be equal to the number of characters of elements in switches.
  • Each character in switches and lamps will be 'Y' or 'N'.
  • For each i, the number of 'Y' in switches[i] and the number of 'Y' in lamps[i] will be equal.
Examples
0)
{"NYNN", "NNYN"}
{"NNNY", "NNYN"}
Returns: 1

He can figure out that switch 1 is connected to lamp 3 and switch 2 is connected to lamp 2. He needs one more experiment to figure out which of the switches 0 and 3 is connected to lamp 0.

1)
{"YYN", "YNY", "YYN"}
{"YNY", "NYY", "YNY"}
Returns: 0

He can figure out that switch 0 is connected to lamp 2, switch 1 is connected to lamp 0, and switch 2 is connected to lamp 1. No additional experiments are necessary.

2)
{"NYYYNYNNYYYNYNNNNY", "NYYYNYNNYYYNYNNNNY"}
{"YYYNNNYNNYNYNYNYNY", "YYYNNNYNNYNYYNNYNY"}
Returns: -1

The same experiment cannot give different results when executed twice.

3)
{"YYNNN", "NNYYN"}
{"NYNNY", "NNNYY"}
Returns: -1
4)
{"YNNYNNYNYY", "NYNNYNYNYN", "YNYNYYYYYN", "NNYYNYNYNN"}
{"NYYNYNNYNY", "NYYYNNYNNN", "YYYYNYNNYY", "YNNNNYNYYN"}
Returns: 2

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

Coding Area

Language: C++17 · define a public class SwitchesAndLamps with a public method int theMin(vector<string> switches, vector<string> lamps) · 166 test cases · 2 s / 256 MB per case

Submitting as anonymous