 Practice

Contest

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], 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]
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, C, …, 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

6 Likes

can you explain what the component means in this context ???

1 Like

The graph may not connected hence it may consist of several connected components.

1 Like

“have rooted trees coming out of the cycle for each node of the cycle”

why each cycle node have a rooted tree?

similar problem: http://www.spoj.com/problems/AMR10J/

Could someone provide a simpler answer for someone not well versed in graph theory? I don’t understand the algorithm for solving this at all. A graph where the nodes are families and the edges are enemies makes sense, but I don’t know why walking that graph helps. If I walk from a family to that family’s enemy, how does that help me count the number of situations where those two families aren’t at the party?

The part about the graph having a single path makes sense I guess. If you start at the first family and then walk the directional paths, avoiding already visited nodes, then you’ll run out of nodes at some point, but you won’t necessarily have touched all nodes. Then you repeat the process for the second family, etc. But, again, I don’t know how that helps count the number of unique results.

@tuananh93 thank you… got it…