Numways problem in inter iit contest2 hacker rank

general
, ,
1

@anton_lunyov I would like to know how you solved this problem problem link

2

Firstly think of the input as a graph : G(V,E) where V = {1,2ā€¦n} leaving the elements in set C ,
and E = (i,j) where i * a = j OR i * b = j OR i = j * a OR i = j * b (graph is undirected) .

Now we have to find the number of independent sets in this graph , which for general graphs has no polynomial time solution. So lets concentrate on the brute force approach for this problem.Simple brute force would be nothing but trying all subsets of the vertex set.However we can do better by decomposing the graph into connected components and doing the same for all these components.Also, a simple check will reveal that there a no more than 40 vertices in a single component for the constraints in the problem.This suggests us that we can try a meet in the middle approach.That is , we can compute those valid subsets of size of 20 elements and try finding the valid combinations .Another check will reveal that there are no more than 10^4 valid vertex subsets in the worst case . This suggests us that we can simply loop over the valid subsets using first 20 elements and check if the subset using the last 20 elements can be combined. This will give us a worst case of (10^8) iterations , which works quite fast.

Pseudo Code :

  1. make the graph

  2. find the components

  3. for each component do :

  4. Let the number of elements in the component be size

  5. Now compute the list of all valid subsets L using the first size/2 elements.

  6. Iterate through all valid subsets using the last (size - size/2) elements and for each such subset consider the number of subsets in L which on combination gives a valid independent set , and increase the count.

  7. Multiply the count to the answer.

Code : Link

5 Likes
3

@javadecoder Can you be more clear about how to use the meet in the middle approach to find the number of independent sets in a connected graph of 40 vertices?

4

First enumerate all the subsets of first 20 elements and store the valid ones in a vector ā€˜gā€™. Now enumerate all the subsets of last 20 elements and for each valid subset , loop over the vector ā€˜gā€™ to check if the subset in consideration and the subset ā€˜g[i]ā€™ give a valid subset , if yes then increment the count . By valid subset I mean to say that the subset satisfies the definition of an independent set.