**Problem Detail:**

Consider a directed graph. Each node in this graph has an integer label. We want to count the number of special paths between `source`

and `sink`

. Let's define a variable named `value`

. Every path starts with `value = label[source]`

. When we move from node A to B value changes like this: `value = lcm( label[B], value )`

where `lcm`

is lowest common multiplier. A speical path has two condition:

1- During the move from `source`

to `sink`

value should always change. It means when moving from node A to B, if `value`

before and after the move remains unchanged, that path is not special.

2- `value`

should become some predetermined integer `k`

at the end of the path.

How many ways we can go from `source`

to `sink`

while not contradicting above conditions.

I think we can remove every node that `lcm(label[node], k) != k`

because this node could not be on any special path. Also condition one removes every loop from the graph.

Now the only algorithm I know about counting all the paths between two nodes is to use Dynamic Programming but I can't reduce this problem to that.

Also I can compute the result using backtrack but as there could be exponentially large number of such paths, it's not efficient enough.

###### Asked By : sudomakeinstall2

#### Answered By : JoaoM

To start, notice that a room is only useful if v[i] divides k, where v[i] is the value of the room i. One other important thing to see is that, is the worst case there are at most 7 different primes (2*3*5*7*11*13) in the prime factorization of k and at most 19 primes total (2^19). This gives us a good hint that we can use a bitmask to represent the value of each node in such a way that lcm(v[i], v[j]) = v[i] | v[j] (bitwise or).

After having the graph pre-processed (with only the useful nodes and with the bitmask pre-computed for every node and for k), we can do DP on the graph that can be seen as a DAG because we will never go through the same node twice. Our state will then be (cur_node, cur_bitmask).

There's only one final detail for this to fit in memory. One should notice that for the second dimension of the DP is very sparse so we can use a map for each node to keep the DP results.

Hope my explanation was clear enough, if not, feel free to clarify your doubts :)

Sample implementation: http://pastebin.com/KLfyyvhv

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49746

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback