If you want to make money online : Register now

# [Solved]: Number of special paths between two nodes

, ,
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.

original problem statement

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