Problem Link:
Difficulty:
Medium
Pre-requisites:
Dynamic Programming, Tree
Problem:
Given N families, each of whom declares exactly one enemy among the remaining families, find how many ways are there to invite a set of families to your party, given that you will not invite both a family as well as its enemy.
Explanation:
Consider the (multi)graph where nodes correspond to families and edges correspond to enmity. Then in this graph, every component consists of exactly one cycle. This is because, if the component has n nodes, then there are exactly n edges corresponding to the enemies of each node. Further, a connected component having n nodes and n edges consists of exactly one cycle. In this argument, note that I am considering a multigraph, and there can be cases of A having enemy B, whose enemy is A itself, thus forming a “cycle” of size 2.
Further, the answer for each connected component is independent. So, if we can solve the problem for a single component, we just take the product of our answers over all components to get our final answer.
If the graph were a tree, it would be a simple problem - where we consider two DPs:
INVITE[n] saying how many ways are there, considering the subtree rooted at n, and wherein we invite node n.
nINVITE[n] saying how many ways are there, considering the subtree rooted at n, and wherein we do Not invite node n.
In the above, INVITE[n] = product (nINVITE[c] : c is a child of n)
and, nINVITE[n] = product(nINVITE[c] + INVITE[c] : c is a child of n)
For this modified problem, which is almost a tree (one extra edge :(), we consider the cycle, and have rooted trees coming out of the cycle for each node of the cycle. We then calculate values of INVITE and nINVITE for all the nodes. Finally, if the cycle consists of the nodes C1 – C2 – C3 – … – Ck – C1, we break the cycle (Ck-C1 edge) and consider it as a path taking two separate cases for having chosen C1, or not.
That is, given INVITE and nINVITE values for Ci, we run two O(K) loops as follows:
int ans1, ans2
int inv, ninv;
//case 1: invite C1
inv = INVITE[C[1]], ninv = 0
for (i = 2; i <= K; i++)
if(i == K)
inv, ninv = 0, nINVITE[C[i]] * (inv + ninv)
else
inv, ninv = INVITE[C[i]] * ninv, nINVITE[C[i]] * (inv + ninv)
ans1 = inv + ninv
//case 2: don't invite C1
inv = 0, ninv = nINVITE[C[1]]
for (i = 2; i <= K; i++)
inv, ninv = INVITE[C[i]] * ninv, nINVITE[C[i]] * (inv + ninv)
ans2 = inv + ninv
return ans1 + ans2
In the above, for case1, we are not allowed to invite C[K], whereas in case2, there is no such restriction. “inv, ninv” store what are the number of ways, when we consider C[1], C[2], …, C[i] for each i upto K. We finally return the sum of the answers to the two cases.
Thus, the overall algorithm is as follows:
Step 1: Cycle Detection
Step 2: Rooting trees as cycle-nodes and finding values of INVITE and nINVITE
Step 3: Finding the solution for each cycle by breaking it into paths and considering two cases for the first node.
Overall order of complexity: O(N) for Step 1, O(N) for Step 2, O(N) for Step 3 => O(N) for the whole program.
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here
got it…