DistinguishableSetDiv2 | Topcoder Archive

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 String[] answer with N elements, each consisting of M characters. For each i and j, answer[i][j] is the answer person i chose for question j.

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.

Definition

Class:: DistinguishableSetDiv2
Method:: count
Parameters:: String[]
Returns:: int
Method signature:: int count(String[] answer)
(be sure your method is public)

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').

Examples

```
{"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
```

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)2024, Topcoder, Inc. All rights reserved.