Connection Status:
Competition Arena > SquareCityWalking

SquareCityWalking

SRM 788 · 2020-07-22 · by square1001

SRM 788 · 2020-07-22 · by square1001 · Brute Force, Dynamic Programming, Math, Recursion
Class Name: SquareCityWalking
Return Type: int
Method Name: largestGCD
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

TopCity is a square-shaped city. When we divide the city into N rows and N columns, you can see that the city is divided into N2 districts. We will number both the rows and the columns starting from 0, and we will say that district (i, j) is the square in row i and column j.
In TopCity, districts have various cultures. For each district, a positive integer is assigned to represent its culture. The culture of district (i, j) is represented by the integer A[i*N+j].


You are initially at district (0, 0). You will go to district (N-1, N-1) by repeatedly moving between cells which share an edge, using a shortest route.


The similarity of cultures of different districts can be measured by computing the greatest common divisor (GCD, see Notes for definition) of their individual culture values.
The similarity of cultures on your route is the similarity of all districts that lie on the route, including districts (0, 0) and (N-1, N-1).
Find and return the largest possible similarity of cultures on a valid route from (0, 0) to (N-1, N-1).

Notes

  • GCD (Greatest Common Divisors) means the largest positive integer which divides all given values. For example, the GCD of {91, 169, 130} is 13, because 13 divides all three given integers, but there is no larger value which divides all three given integers.

Constraints

  • N will be between 1 and 25.
  • The length of A will be exactly N*N.
  • A[i] will be between 1 and 100.
Examples
0)
3
{ 96, 42, 45,
  32, 36, 27,
  40, 54, 84 }
Returns: 6

In this example, there are six possible routes that you may pass. The culture value of districts you pass for each possibility, will be following: 96 --> 42 --> 45 --> 27 --> 84 (The GCD will be 3) 96 --> 42 --> 36 --> 27 --> 84 (The GCD will be 3) 96 --> 42 --> 36 --> 54 --> 84 (The GCD will be 6) 96 --> 32 --> 36 --> 27 --> 84 (The GCD will be 1) 96 --> 32 --> 36 --> 54 --> 84 (The GCD will be 2) 96 --> 32 --> 40 --> 54 --> 84 (The GCD will be 2) Hence, the maximum possible GCD will be 6, and that's why you need to return 6 for this example.

1)
3
{ 4, 9, 2,
  3, 5, 7,
  8, 1, 6 }
Returns: 1

In this example, there are six possible routes, but for all of them, the GCD of culture value of districts you pass will be 1. So, the maximum possible GCD of culture value of districts you pass is 1.

2)
4
{ 54, 81, 27, 36,
  48, 64, 96, 72,
  84, 60, 45, 99,
  80, 90, 40, 63 }
Returns: 9

In this example, it is optimal to move as (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) --> (1, 3) --> (2, 3) --> (3, 3), and the GCD of their culture values will be 9.

3)
1
{ 47 }
Returns: 47

Please note that there is a case which N is equal to 1. The GCD of "just 47" is, of course, 47.

4)
5
{ 100,  80,  64,  48,  36,
   75,  10,  10,  10,  48,
   50,  10,  10,  10,  64,
   25,  10,  10,  10,  80,
    5,  25,  50,  75, 100 }
Returns: 10

In this example, one of the optimal route is (0, 0) --> (0, 1) --> (1, 1) --> (1, 2) --> (2, 2) --> (2, 3) --> (3, 3) --> (3, 4) --> (4, 4), and the GCD of their culture values will be 10.

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

Coding Area

Language: C++17 · define a public class SquareCityWalking with a public method int largestGCD(int N, vector<int> A) · 54 test cases · 2 s / 256 MB per case

Submitting as anonymous