PROBLEM LINK:
Author: Vraj
Tester: Vraj
Editorialist: Vraj
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming on Trees, Cycle Finding
PROBLEM:
Given a graph G with exactly one cycle of length at most 6 with vertices having non-negative integral weights, find the weight of the minimum weighted vertex cover in the graph.
QUICK EXPLANATION:
Find the cycle in G, the given graph. Run the vertex cover DP on the trees left out after removing the edges in the cycle. Now, iterate over all the combinations of states on the vertices of the cycle which lead to a vertex cover on the cycle.
EXPLANATION:
For the sake of completeness, let us revisit the DP approach to find the min. weighted vertex cover in a tree briefly. Given a rooted tree, you can find the min. weighted vertex cover by doing a DP maintaining two states on every vertex corresponding to whether the vertex is included in VC or not. DP[u][0] represents the min. weight of VC in the subtree rooted at u, if u is not to be selected as part of the VC. Similarly, DP[u][1] represents the min. weight of VC in the subtree rooted at u, if u is to be selected as part of the VC.
Now, let us suppose we have computed these values for all the children of the node u. When u is not to be selected, we need to include all the children of u so that all the edges between u and its children are covered. Therefore,
DP[u][0] = \sum\limits_{v \in \text{children}(u)} DP[v][1]
When u has to be a part of the vertex cover, it’s children may or may not be a part of them. So, for each of the children, we can simply select the minimum of the two DP states. Therefore,
DP[u][0] = \sum\limits_{v \in \text{children}(u)} \min(DP[v][0],DP[v][1])
Now, let us come back to the problem at hand, of finding the min. weight VC for a graph which has a single cycle. The cycle is the only obstruction in our way. Observe that if we find the cycle edges and remove them, we are left with independent trees rooted at the vertices which were part of the cycle. We can easily compute the answer to min. weight vertex cover, for the cases when the cycle vertices are and are not a part of the overall solution.
Now, we only need to consolidate all the computed values to get a valid solution. We will simply try out all combination of states for the cycle vertices which lead to a covering of the edges of the cycle that we previously removed. This leads to the following computation for the answer where S[v] denotes the state value (0 or 1) for a cycle vertex v, in the combination under consideration,
ans = \min\limits_{\text{all valid cycle states}} \sum\limits_{v \in \text{cycle}} DP[v][S[v]]
For the analysis, let us assume that c is the lenght of the cycle. Now, finding the cycle and computing the DP values for all the trees takes \mathcal{O}(N) time. Since you have to go over all the combinations of 2 states for all the vertices in a cycle and check (in \mathcal{O}(c) time) whether the particular combination corresponds to a vertex cover, consolidating the states to get the final solution requires \mathcal{O}(2^c c) time. Therefore, the overall time complexity for the solution is \mathcal{O}\left(2^{c} c + N \right).
SOLUTIONS:
Setter's Solution
import sys
import atexit
import io
sys.setrecursionlimit(10**6)
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER
@atexit.register
def write():
sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
def find_cycle_end(A_list,visited, curr = 0):
for v in A_list[curr]:
ans = -1
if visited[v]==-1:
visited[v]=curr
ans = find_cycle_end(A_list, visited, v)
elif visited[v]!=-1 and v!=visited[curr]:
visited[v] = curr
ans = curr
if ans!=-1:
return ans
return -1
def vc_tree(A_list, curr ,w, dp ,a1, a2, visited):
visited[curr] = True
dp0 = 0
dp1 = w[curr]
for v in A_list[curr]:
if not visited[v] and v!=a1 and v!=a2:
vc_tree(A_list, v,w, dp,a1,a2,visited)
dp0+=dp[v][1]
dp1+=min(dp[v][0], dp[v][1])
dp[curr][0] = dp0
dp[curr][1] = dp1
def is_cycle_vc(c):
for i in range(len(c)):
if c[i] == '0' and c[i-1] =='0':
return False
return True
N = int(input())
W = [int(i) for i in input().split()]
A_list = [[] for i in range(N)]
for i in range(N):
u,v = [int(i)-1 for i in input().split()]
A_list[u].append(v)
A_list[v].append(u)
vl = [-1]*N
vl[0] = -2
c_end = find_cycle_end(A_list, vl)
cycle = []
curr = c_end
while vl[curr] != c_end:
cycle.append(curr)
curr = vl[curr]
cycle.append(curr)
large_num = 10**11
DP = [[large_num,large_num] for i in range(N)]
vl = [False]*N
for i in range(len(cycle)):
vc_tree(A_list,cycle[i], W,DP, cycle[i-1], cycle[(i+1)%len(cycle)], vl)
ans = large_num
for i in range(2**len(cycle)):
bs = bin(i)[2:]
bs = '0'*(len(cycle) - len(bs)) + bs
if is_cycle_vc(bs):
ans = min(ans, sum(DP[i][int(j)] for i,j in zip(cycle, bs)))
print(ans)