SRM 699, D1, 500-Pointer (FromToDivisible)

James S. Plank

Sat Oct 8 12:36:33 EDT 2016

The alternate graph

This sure feels like an unweighted shortest path (BFS) problem. However, like many Topcoder graph problems, you can't use the graph that they specify, but instead, you have to create an alternate graph.

Obviously, the graph that they specify is too big. If a[i] equals 2, and b[i] equals 3, and N equals 1,000,000,000, then there are roughly (500,000,000 * 333,333,333) edges. That's too big.

However, let's work on building a different graph that solves the problem, but is much smaller. Here's thought number one: If your path uses an edge (w,x) defined by (a[i],b[i]), then it will never take a subsequent edge (y,z) which is also defined by (a[i],b[i]). Why? Because the edge (w,z) will exist, and your path could have taken it instead of (w,x).

That observation helps us, because we can try to define our path as a sequence of (a[i],b[i]) values, rather than as a sequence of edges.

So, let's build a new graph. In this new graph, the nodes are i values (as in (a[i],b[i])). We'll have an edge from S to a node i if the (a[i],b[i]) includes node S as one of its a[i] nodes. And, we'll have an edge from a node i to T the (a[i],b[i]) includes node T as one of its b[i] nodes. Finally, we'll have an edge from node i to node j if there exists a city that is one of the b[i] nodes, and also one of the a[j] nodes.

The shortest path from S to T on this new graph defines a shortest path on the original graph. The path on the original graph will be one edge shorter than the path our our new graph (we'll see this on the example below).

We can find this shortest path using BFS, which is O(|V|+|E|). Our new graph has a maximum of 1000 nodes, so the maximum number of edges is 1,000,000. That's big, but well within topcoder limits.

Converting the problem's graph to our alternate graph

First, how do we create the edges from S? Those will be to nodes i such that S is a multiple of a[i]. Similarly, the nodes to T will be the nodes i such that T is a multiple of b[i].

What about edges from node i to node j? We need to find a city C such that C is a multiple of b[i], and also a multiple of a[j]. In other words, we need to find the least common multiple (LCM) of b[i] and a[j]. If that value is less than or equal to N, then the edge exists. If it is greater to N, then the edge doesn't exist.

Is there a fast algorithm for LCM of x and y? Yes, and it is based on finding the greatest common denominator (GCD) of x and y? Suppose the GCD of x and y is z. Define s and t such that x = sz and y = tz. Then, the LCM of x and y is zst.

There is a fast algorithm (log time) for GCD. It is attributed to Euclid, and it goes as follows:

This gives you a way of creating the graph.

Example 3

Example 3 is big enough to be interesting. That gives us the following graph:

You can see the shortest path in red - since it is composed of five edges, the answer is four.

Now that you know all of the pieces of the puzzle, go ahead and solve the problem!