PROBLEM LINK
Panel Members
Problem Setter: Sunny Aggarwal
Problem Tester: Pushkar Mishra
Editorialist: Prateek Gupta
Contest Admin: Praveen Dhinwa and Pushkar Mishra
Russian Translator: Sergey Kulik
Mandarin Translator: Hu Zecong
Vietnamese Translator: VNOI Team
Language Verifier: Rahul Arora
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Dynamic Programming, Graph.
PROBLEM:
Given a complete graph of N nodes, find the number of ways to remove subset of edges such that after removal, there exist K connected components.
EXPLANATION
A complete graph of N nodes has NC2 edges meaning each node is connected to all other nodes in the graph.
Solution to Subtask 1
Approach
Since N is pretty small here, we can go bit of brute here. We can consider subset of NC2 edges and make a graph using those. The resultant graph can then be checked to have exactly K connected components.
Pseudo Code:
Lets see how to use Bit Manipulation technique to form the subset of the given complete graph.
for ( int i = 0; i < 1<<edges; i++ ) {
subset_graph = {}
for ( int j = 0; j < edges; j++ ) {
if ( i & (1<<j) ) {
subset_graph = subset_graph U edges[j]
}
}
ans += (number of components in subset_graph == K)
}
Now, we need to find how to check if the graph formed by subset of edges has K connected components.
int components = 0;
void dfs(int curr)
{
vis[curr] = true;
for ( int i = 0; i < g[curr].size(); i++ ) {
int to = g[curr][i];
if ( vis[to] ) continue;
dfs(to);
}
}
for ( i = 0; i < N; i++ ) {
if ( !vis[i] ) {
components++;
dfs(i);
}
}
Let M denote NC2 i.e the number of edges in a complete graph of N nodes. Then, overall complexity for this subtask is around \mathcal{O}(MN * 2 ^ {M}) which is infact pretty slow for large values of M.
Solution to subtask 2, 3 & 4
The solution to this subtask will indeed require breaking down the problem into smaller sub-problems and then combine their results to find out the result of the bigger problem. Let us see the recurrence involved in breaking down the problem into smaller sub parts.
Approach
Let C(i,j) denote the number the of ways to choose j vertices from i vertices. Then, the following equations hold true.
C(i,0) = 1
C(i,i) = 1
C(i,j) = C(i-1,j-1) + C(i-1,j)
This can be precomputed in \mathcal{O}(N^{2}) space and time complexity.
Let F(i,j) denote the number of ways to choose a subset of edges from total iC2 edges such that the resultant graph of i vertices has exactly j connected components. At any particular state (i,j), we have added i - 1 nodes into the graph, and now, we will go on to add the ith vertex in our graph. So, as i - 1 vertices are being added till now, there can be atmost i - 1 components. Henceforth, ith vertex can be added in any of the component size. If we assume the size of that component as k, then following equation holds true.
F(i,j) = \sum_{k=1}^{i-1} F(i-k,j-1) * F(k,1) * C(i-1,k-1) for all j >= 2
To place the ith vertex in the graph where i - 1 have already been added, we needed to choose any k - 1 vertices from i - 1 vertices.
F(i,1) = 2(i*(i-1))/2 - \sum_{j=2}^{j=i} F(i,j)
For details on the implementation, please look at the setter’s and tester’s solution mentioned in the section below. Do not forget to take modulo M while doing calculations.
COMPLEXITY
Overall complexity for each test case should be \mathcal{O}(KN^{2}) to pass all the subtasks stated in the problem.