ALTREE - Editorial

PROBLEM LINK:

Practice

Contest

Author: Sameer Gulati

Tester: Anurag Anand

DIFFICULTY:

Easy - Medium

PREREQUISITES:

Graph, Bitmask Dp

PROBLEM:

Given a graph with n nodes and m edges where each edge has a color(black or white) and a cost associated with it. Find the minimum spanning tree of the graph such that every path in the tree is made up of alternating colored edges.

EXPLANATION:

First observation is that every such kind of spanning tree will be a chain. To prove it, suppose we have a tree that is not a chain and every path in it is made up of alternating edges. Then at least 1 node has a degree of 3. Out of these 3 edges, at least 2 will have the same color. The path using these 2 edges will not follow the conditions. This causes a contradiction. Hence, such kind of tree is always a chain.

Now we want to find the chain with minimum cost that has alternating edges. This can be solved with bitmask dp : dp[mask(2^n)][Node(n)][col_of_last_edge(2)] where mask is the bitmask of nodes we’ve added to the chain, Node is the last node we added to the chain and col_of_last_edge is the color of edge use to connect Node. To transition from 1 state to another state we visit the adjacency list of last node and use those edges which have color != col_of_last_edge.

Time Complexity: O(2^N * (M + N))

AUTHOR’S SOLUTION:

Author’s solution can be found here.

//