PROBLEM LINK:
Practice
Author: Jatin Yadav
Tester: tncks0121
DIFFICULTY:
Medium
PREREQUISITES:
Graph theory, Bitmask DP
PROBLEM:
Given an undirected weighted graph and k special nodes, delete some edges of minimum total weight from it, such that after the deletion of these edges, no two special nodes have a path between them.
Explanation:
Let the connected components on the deletion be S_1, S_2, \ldots S_k, where i \in S_i \forall 1 \leq i \leq k. Note that there will be exactly k components in the optimal answer, as a component not containing a special vertex can be merged into a component containing a special vertex giving a better solution. Also, it is not optimal to remove edges which have both endpoints in the same connected component.
So, the problem is equivalent to finding such a partition such that the sum of weights of edges having endpoints in different sets of the partition is minimized. This is the same as maximizing the sum of weights of edges having endpoints in the same set.
Let f(S) denote the sum of weights of edges with both endpoints in the set S. Precompute f(S) for all sets using brute force in O(n^2 2^n) .
We have to maximimize \displaystyle \sum_{i=1}^{k} f(S_i).
For a subset Q of non-special vertices, define g(j, Q) as the maximum possible value of \displaystyle \sum_{i=1}^{j} f( \{i\} \cup R_i), where Q = R_1 \cup R_2 \ldots \cup R_j , and all R_i are disjoint.
Clearly, we are interested in finding g(k, V \setminus \{1, 2, \ldots k\}).
We use the following recurrence to compute g:
-
g(1, Q) = f(\{1\} \cup Q)
-
\forall j > 1, \text{ } g(j, Q) = \displaystyle \max_{P \subseteq Q } \left ( \text{ } f(\{j\} \cup P) \text{ } + \text{ } g (j - 1, Q \setminus P) \text{ } \right) .
To get the above recurrence we have just iterated on R_j = P.
Clearly, we are iterating over subsets of subsets of the non special vertices for each 1 \leq j \leq k. So, the complexity is O(n^2 2^n + k 3^{n - k}), which is maximized at k = 3. The TL is enough for this to pass, as there are no costly operations and the memory usage is also small (2^n).
Also, on a more detailed analysis, we see that the constant factor would be very small here (for example, the author’s code runs in 0.31 seconds):
-
We only have to compute k-2 layers of the dp from 2 to k - 1. For layer k we only need to compute g(k, V \setminus \{1, 2, \ldots k\}). So, we actually have (k-2) 3^{n-k} \leq 3^{17} \approx 1e8
-
When precomputing f over all sets, we iterate over edges and add its weight to all subsets containing both endpoints of this edge. So, there would be a constant factor of about \frac{1}{8} with the n^2 2^n part.
AUTHOR’S and TESTER’S codes:
The author’s code can be found here
The tester’s code can be found here