DistinguishableSetDiv2
2016 TCC India Online Round · 2016-03-24 · by IH19980412
Problem Statement
There are N people. Each of them was given the same survey that consisted of M questions. The people were numbered 0 through N-1, and the questions were numbered 0 through M-1. Each person answered each question by choosing one of the provided options. For each question, the options were labeled using distinct uppercase letters ('A'-'Z').
You are given the responses to the survey: a
A set of questions is called a distinguishable set if we can use it to distinguish between any two of our N people. Formally, a distinguishable set of questions has the property that no two people have the same sequence of responses to those questions.
The set of questions used in the survey has exactly 2^M subsets. Count how many of those subsets are distinguishable sets, and return that count.
Constraints
- N will be between 2 and 50, inclusive.
- M will be between 1 and 10, inclusive.
- answer will contain exactly N elements, inclusive.
- Each element in answer will contain exactly M characters, inclusive.
- Each character in answer will be a uppercase letter ('A'-'Z').
{"AA","AB","CC"}
Returns: 2
There are 4 subsets of questions: {}, {0}, {1}, and {0,1}. Let's look at each of them separately. For the empty subset {} each person gave the same sequence of answers (an empty sequence). For the subset {0} the answers given by the three people were "A", "A", and "C". Note that two of the people gave the same response. For the subset {1} the answers given by the three people were "A", "B", and "C". Note that all three responses are distinct. For the subset {0,1} the answers given by the three people were "AA", "AB", and "CC". Again, note that all three responses are distinct. Thus, there are 2 distinguishable sets: {1} and {0,1}.
{"XYZ","XYZ","XYZ"}
Returns: 0
Each person gave exactly the same sequence of answers. Thus, no subset of questions is a distinguishable set. The correct return value in such a case is 0.
{"AAAA","BACA","CDCE"}
Returns: 11
Among the 16 possible subsets of these questions there are 11 distinguishable sets. The five subsets of questions that are not distinguishable sets are {}, {1}, {2}, {3}, and {1,3}.
{"HGHHGUHUHI","BQHJWOSZMM","NDKSKCNXND","QOEOEIWIDS","IIQIWUNNZM"}
Returns: 1017
{"XYZ","XAB","YAC"}
Returns: 5
Submissions are judged against all 63 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DistinguishableSetDiv2 with a public method int count(vector<string> answer) · 63 test cases · 2 s / 256 MB per case