JOIN
Get Time

   Problem Statement  

 Problem Statement for SwitchesAndLamps

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.
 

Definition

    
Class:SwitchesAndLamps
Method:theMin
Parameters:String[], String[]
Returns:int
Method signature:int theMin(String[] switches, String[] lamps)
(be sure your method is public)
    
 

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

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2012 TCO Algorithm Round 2A - Division I, Level One