Efficient Construction on Mars

We can think of countries as minimum-spanning trees (MST), cities as nodes, and roads as edges in the graph. Then we can rephrase the problem as building $C$ disconnected MST using $N$ nodes and $E$ in a way so that the maximum cost among minimum spanning trees is the minimum possible.

Iterative Solution:

At first, we will pre-compute and store the cost of MST for every possible subset of cities if these cities are connected otherwise the cost will be stored as $INF$. Let’s define $mstCost[sset]$ as the cost of the minimum spanning tree of the subset $sset$of cities.

Finally, we will use dynamic programming with bitmask to distribute the cities among countries. Let’s suppose, $dp[c][mask]$ denotes the minimized maximum cost to distribute a subset $mask$ of cities among first $C$ countries. Now, for the $C’th$ country, we will enumerate all sub-masks $submask$ of mask $mask$. Then, we will calculate the minimum possible maximum cost for the first $C$ countries as follows:

$$dp[c][mask] = min(dp[c][mask], max(mstCost[submask], dp[c-1][mask-submask])$$

Time Complexity:

Overall time complexity is $C* 3^N + N^2 * 2^N$.

We will require $3^N$ to iterate through all masks with their sub-masks. And we will also require $N^2 * 2^N$ to pre-compute the cost of MST for all possible subsets of cities.

Memory Complexity:

Overall memory complexity is $O(C*2^N)$.