2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Note: this is from a programming contest. $\endgroup$ – Yuval Filmus Nov 20 '15 at 19:57
2
+50
$\begingroup$

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

$\endgroup$
1
$\begingroup$

I don't have a solution, but here's something that's probably needed for a solution.

Recall that every natural number can be written uniquely as a product of prime powers: $n = p_1^{k_1} p_2^{k_2} \dots p_a^{k_a}$ for a number $n$ with at most $a$ prime factors $p_1, \dots, p_a$ all unique.

The lcm of two numbers can be easily computed in terms of products of prime powers: You simply take the maximum exponent for every prime. If $n = p_1^{k_1} \dots p_a^{k_a}$ and $n' = p_1^{m_1} \dots p_a^{m_a}$, then $\mathit{lcm}(n, n') = p_1^{\mathrm{max}(k_1, m_1)} \dots p_a^{\mathrm{max}(k_a, m_a)}$.

It follows that if we go from node $u$ with value $b$ to node $v$ with key $b' = \mathit{lcm}(b, l[v])$ and $b' \ne b$, then $b' \ge 2 b$. Thus any special path from the source to the sink has length at most $\log_2 k$ (which for the programming contest, where $k \le 10^6$, means at most $20$ edges followed).

$\endgroup$
  • 1
    $\begingroup$ This fact is irrelevant because if you have a graph somewhat like a neural network with 22 layers. Layer one includes the source node and layer 22 is the sink node. Each of the middle layers include ten nodes which is fully connected to adjacent layers. All the middle layers nodes have label 2 where source and sink have label 1. if k=2^20 there will be around 10^20 number of special paths. So this fact doesn't necessary make the problem easier. $\endgroup$ – sudomakeinstall2 Nov 23 '15 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.