SRM 699, D1, 500-Pointer (FromToDivisible)

James S. Plank

Mon Dec 3 15:05:06 EST 2018

If Topcoder's Servers are Down

Here is a summary of the problem: Examples:

# N S T a b Answer
0 11 9 6 {3,10} {5,2} 2
1 123456789 18 12 {1,42,50} {1,17,3} 1
2 60 30 8 {16,15,12} {2,20,5} -1
3 77 10 62 {2,5,7,4,17,26} {25,7,11,13,31,34} 4
4 100 90 40 {20,30,100,99,100} {10,30,100,100,99} 2
5 1000000000 7000 424212345 {35000000,120000000,424212345,200000000,3500,19} {15,1,7000,200000000,400000000,17} 3
6 2 1 2 {2} {1} -1
7 See main.cpp for values. 35
9 See main.cpp for values. 72
14 See main.cpp for values. 7
17 See main.cpp for values. 140
19 See main.cpp for values. -1
22 See main.cpp for values. 1


Grading

There are tests.sh and answers.txt files. The examples above are the only ones in tests.sh, and they are hard-coded in main.cpp, so I don't read anything from standard input, and there are just 13 test problems. So be it. I could write some harder ones, but I'm not in the mood.

Your code needs to run in under 2 seconds for each example.


Intuition -- What on earth are the graphs?

You can try to draw them, but they are a pain to draw. It's probably easier to just describe them. Try this for example 0: Given that definition, it's pretty easy to see that the shortest path from 9 to 6 goes from 9 to 10 to 6.

Hopefully that gives you some better intuition about what these graphs look like.


Strategy -- Build a Smaller Graph with Equivalent Properties

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 with equivalent properties.

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 of the original graph.

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 node 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 node 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!