Clicountingd2 | Topcoder Archive

Problem Statement

Hero has a simple undirected graph. I.e., the graph has no self-loops and each pair of vertices is connected by at most one edge. Hero would like to solve a standard problem: he wants to find the size of the largest clique in his graph. (A clique is a subset C of vertices such that each pair of vertices in C is connected by an edge. The size of a clique is the number of vertices in C.) However, Hero is facing an issue: for some (at most 20) pairs of vertices he does not remember whether they are connected by an edge or not. You are given the information Hero remembers: a String[] g with n elements, where n is the number of vertices in the graph. The vertices are numbered 0 through n-1. For each valid i and j, g[i][j] is one of '0', '1', and '?'. Here, '0' means that vertices i and j are not connected, '1' means that they are connected, and '?' means that Hero does not remember whether they are connected. Let there be k unordered pairs of vertices for which Hero does not remember whether they are connected or not. Then, there are exactly 2^k different graphs consistent with what Hero remembers. For each of those graphs find the size of the largest clique, and return the sum of those 2^k numbers.

Definition

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

Constraints

g will contain n elements.
n will be between 1 and 20, inclusive.
Each element in g will contain exactly n characters.
Each character in g will be either '0', '1' or '?'.
For each valid i and j, g[i][j] will be equal to g[j][i].
For each valid i, g[i][i] will be '0'.
Number of unknown edges (number of '?' characters divided by 2) will be between 0 and 20, inclusive.

Examples

```
{"01","10"}
```
```
Returns: 2
```
```
{"0?","?0"}
```
```
Returns: 3
```
Here the maximum clique size is either 2 (if the unknown edge is present) or 1 (if the edge is absent).
```
{"011","101","110"}
```
```
Returns: 3
```
This is a complete graph on 3 vertices. The size of the maximum clique is 3.
```
{"0?1","?01","110"}
```
```
Returns: 5
```
Hero is not sure about a single edge. If the edge is in the graph, we get the situation from Example 2. If the edge is not there, we get a graph in which the size of the maximum clique is 2. The answer is therefore 3+2 = 5.

{"0???","?0??","??0?","???0"}

Returns: 151

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.