FromToDivisibleDiv2 | Topcoder Archive

Problem Statement

Bearland consists of N cities, numbered 1 through N. Some pairs of cities are connected by one-way roads of unit length. The distance from city X to city Y is the smallest number of roads you need to traverse in order to get from X to Y.

The road network has a special structure. You are given a description of this structure: two int[]s a and b, each with M elements. For each pair of distinct cities (X,Y), there is a one-way road from X to Y if and only if there is at least one index i such that X is divisible by a[i] and Y is divisible by b[i].

For example, suppose that N = 7, M = 1, a[0] = 2, and b[0] = 3. In this case the country has 7 cities and it contains the following one-way roads: 2 -> 3, 2 -> 6, 4 -> 3, 4 -> 6, 6 -> 3, and 6 -> 6.

You are given the int N. You are also given two ints S and T: the source city where you start your journey and the target city you want to reach. Finally, you are given the int[]s a and b described above.

If there is no path from S to T, return -1. Otherwise, compute and return the distance from S to T.

Definition

Class:: FromToDivisibleDiv2
Method:: shortest
Parameters:: int, int, int, int[], int[]
Returns:: int
Method signature:: int shortest(int N, int S, int T, int[] a, int[] b)
(be sure your method is public)

Constraints

N will be between 2 and 10^5, inclusive.
S and T will each be between 1 and N, inclusive.
S and T will be different.
M will be between 1 and 500, inclusive.
a and b will each contain exactly M elements.
Each element in a and in b will be between 1 and N, inclusive.
The pairs (a[i],b[i]) are all distinct.

Examples

```
11
```
```
9
```
```
6
```
```
{3,10}
```
```
{5,2}
```
```
Returns: 2
```
The one-way roads are: (3,5), (3,10), (6,5), (6,10), (9,5), (9,10), (10,2), (10,4), (10,6), (10,8). The shortest path from city 9 to city 6 is 9 -> 10 -> 6. It uses two roads, so the length is 2.
```
12345
```
```
18
```
```
12
```
```
{1,42,50}
```
```
{1,17,3}
```
```
Returns: 1
```
Since a[0] = b[0] = 1, there is a one-way road from any city to any other city. In particular, there is a road from city 18 to city 12.
```
60
```
```
30
```
```
8
```
```
{16,15,12}
```
```
{2,20,5}
```
```
Returns: -1
```

{2,5,7,4,17,26}

{25,7,11,13,31,34}

Returns: 4

{20,30,100,99,100}

{10,30,100,100,99}

Returns: 2

The only optimal path is 90 -> 60 -> 40.

{3500,12000,42345,20000,35,19}

{15,1,700,20000,40000,17}

Returns: 3

```
2
```
```
1
```
```
2
```
```
{2}
```
```
{1}
```
```
Returns: -1
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.