Clicounting
SRM 696 · 2016-07-09 · by subscriber
SRM 696 · 2016-07-09 · by subscriber · Dynamic Programming
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.
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