[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

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

 Download Related Notes/Documents