Connection Status:
Competition Arena > GCDLCMEasy

GCDLCMEasy

SRM 633 · 2014-08-25 · by cgy4ever

SRM 633 · 2014-08-25 · by cgy4ever · Graph Theory
Class Name: GCDLCMEasy
Return Type: String
Method Name: possible
Arg Types: (int, vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

Your task is to find n positive integers. We will label them x[0] through x[n-1].


We will give you some information about these integers. Namely, for some pairs of integers we will tell you both their greatest common divisor (GCD) and their least common multiple (LCM).


You are given the int n and four int[]s: A, B, G, and L. These int[]s will all have the same number of elements. Their meaning is as follows: For each valid i, the integers x[ A[i] ] and x[ B[i] ] must have the greatest common divisor G[i] and the least common multiple L[i].


Return "Solution exists" (quotes for clarity) if there is at least one way to choose x[0] through x[n-1] so that all requirements are satisfied. Otherwise, return "Solution does not exist".

Notes

  • The greatest common divisor (GCD) of two positive integers x and y is the largest positive integer z such that z divides x and at the same time z divides y.
  • The least common multiple (LCM) of two positive integers x and y is the smallest positive integer z such that x divides z and at the same time y divides z.
  • For example, the GCD of 10 and 15 is 5, and the LCM of 10 and 15 is 30.

Constraints

  • n will be between 1 and 500, inclusive.
  • A will contain between 1 and 500 elements, inclusive.
  • A and B will contain the same number of elements.
  • A and G will contain the same number of elements.
  • A and L will contain the same number of elements.
  • Each element in A will be between 0 and n-1, inclusive.
  • Each element in B will be between 0 and n-1, inclusive.
  • For each i, A[i] and B[i] will be different.
  • Each element in G will be between 1 and 10,000, inclusive.
  • Each element in L will be between 1 and 10,000, inclusive.
Examples
0)
4
{0,1,2,3}
{1,2,3,0}
{6,6,6,6}
{12,12,12,12}
Returns: "Solution exists"

We have 4 unknown integers: x[0], x[1], x[2], and x[3]. The given A, B, G, and L encode the following information: The GCD of x[0] and x[1] must be 6 and their LCM must be 12. The GCD of x[1] and x[2] must be 6 and their LCM must be 12. The GCD of x[2] and x[3] must be 6 and their LCM must be 12. The GCD of x[3] and x[0] must be 6 and their LCM must be 12. There are two valid solutions. In one of them, x[0] = x[2] = 6 and x[1] = x[3] = 12.

1)
5
{0,1,2,3,4}
{1,2,3,4,0}
{6,6,6,6,6}
{12,12,12,12,12}
Returns: "Solution does not exist"
2)
2
{0,0}
{1,1}
{123,123}
{456,789}
Returns: "Solution does not exist"

The LCM of x[0] and x[1] cannot be 456 and 789 at the same time.

3)
2
{0}
{1}
{1234}
{5678}
Returns: "Solution does not exist"

The LCM of x[0] and x[1] must always be a multiple of their GCD.

4)
6
{0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4}
{1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5}
{2, 2, 3, 3, 1, 2, 5, 1, 5, 1, 7, 7, 3, 5, 7}
{30, 42, 30, 42, 210, 70, 30, 210, 70, 210, 42, 70, 105, 105, 105}
Returns: "Solution exists"

There is one solution: {6, 10, 14, 15, 21, 35}.

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

Coding Area

Language: C++17 · define a public class GCDLCMEasy with a public method string possible(int n, vector<int> A, vector<int> B, vector<int> G, vector<int> L) · 151 test cases · 2 s / 256 MB per case

Submitting as anonymous