Connection Status:
Competition Arena > Clicounting

Clicounting

SRM 696 · 2016-07-09 · by subscriber

SRM 696 · 2016-07-09 · by subscriber · Dynamic Programming
Class Name: Clicounting
Return Type: int
Method Name: count
Arg Types: (vector<string>)
Problem Statement

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

Constraints

  • g will contain n elements.
  • n will be between 1 and 38, 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 10, inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{"011","101","110"}
Returns: 3

This is a complete graph on 3 vertices. The size of the maximum clique is 3.

1)
{"01?","101","?10"}
Returns: 5

Hero is not sure about a single edge. If the edge is in the graph, we get the situation from Example 0. 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.

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

3)
{"0??","?0?","??0"}
Returns: 16
4)
{"0???","?0??","??0?","???0"}
Returns: 151

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

Coding Area

Language: C++17 · define a public class Clicounting with a public method int count(vector<string> g) · 127 test cases · 2 s / 256 MB per case

Submitting as anonymous