Connection Status:
Competition Arena > FromToDivisibleDiv2

FromToDivisibleDiv2

SRM 699 (Cisco) · 2016-08-27 · by Errichto

SRM 699 (Cisco) · 2016-08-27 · by Errichto · Brute Force
Class Name: FromToDivisibleDiv2
Return Type: int
Method Name: shortest
Arg Types: (int, int, int, vector<int>, vector<int>)
Problem Statement

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.

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
0)
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.

1)
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.

2)
60
30
8
{16,15,12}
{2,20,5}
Returns: -1
3)
77
10
62
{2,5,7,4,17,26}
{25,7,11,13,31,34}
Returns: 4
4)
100
90
40
{20,30,100,99,100}
{10,30,100,100,99}
Returns: 2

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

Submissions are judged against all 32 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FromToDivisibleDiv2 with a public method int shortest(int N, int S, int T, vector<int> a, vector<int> b) · 32 test cases · 2 s / 256 MB per case

Submitting as anonymous