PACMAN - Editorial

PROBLEM LINK:

Contest
Practice

Author: admin3
Editorialist: dhirajfx3

DIFFICULTY:

Easy

PREREQUISITES:

Graphs, dfs

PROBLEM:

There are N softwares and among them are some special, a special software don’t have any software dependent on them. To install a non-special software, first the software on which it depends (at most 1) must be installed. For each copy of special software its full dependency chain must be freshly installed. We are required to find the number distinct special software that can be installed.

QUICK EXPLANATION:

Apply dfs on the forest of trees formed by software dependency network and sum the result from each component.

EXPLANATION:

The network of software dependencies form forest of trees with dependency of a software i as its parent pi and some leaves are marked as special.

To find the total number of special software that can be installed, we need to sum the result of dfs each forest. In each dfs we evaluate the number of distinct special software that can be installed from this component. In each dfs if we are at node u we will traverse its child and sum the number of distinct software that we can install from each sub-tree of u, now the number of distinct software that can be installed is at most the number of copies of copies of u present since all those distinct software lie in sub-tree u and thus depend on u, so for each special software we need a separate copy of u.

See the pseudo code below how to evaluate the number of distinct software that can be installed from each component.

(variable names in the pseudo code are self explanatory)

dfs_software(int u)
	ans = 0
	visited[u] = True
    if is_special[u]:
		ans++
	for v in childs[u]:
		ans = ans + dfs_software(v)
	return min(copies[u],ans)

The image below simulates the dfs shown above in which blue nodes are special software.

Dfs simulation

Now to get the result of whole network, we need to call dfs from root of each component of the forest and then take the sum.

Pseudo code below illustrates this:

solve()
	ans=0
	for each u software without dependency
		ans+= dfs_software(u)
	return u

Time complexity:

If V is the set vertices and E the set of edges then
O(|V|+|E|) .

Editorialist solution:

Solution link