Connection Status:
Competition Arena > AstronomicalRecords

AstronomicalRecords

SRM 594 · 2013-06-25 · by cgy4ever

SRM 594 · 2013-06-25 · by cgy4ever · Dynamic Programming
Class Name: AstronomicalRecords
Return Type: int
Method Name: minimalPlanets
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Fox Ciel found two astronomical records. They both describe the same solar system. Each planet in the system can be characterized by two parameters each being a positive number: planet's size and the distance at which it orbits the sun. All orbital distances are pairwise distinct, but sizes of some planets may be the same.


The first record is a int[] A with x elements. These elements give the relative sizes of some x planets in the solar system. Formally, the sizes of those planets have the ratio A[0] : A[1] : ... : A[x-1]. The planets described by A are ordered by their distance from the sun. (That is, earlier elements of A correspond to planets that are closer to the sun.)


The second record is a int[] B with y elements. These elements give the relative sizes of some y planets in the solar system. Formally, the sizes of those planets have the ratio B[0] : B[1] : ... : B[y-1]. The planets described by B are ordered by their distance from the sun.


Note that the planets considered by a record do not have to be consecutive. For example, if a solar system contains the planets P, Q, R, S, T, and U, it is possible that the first record compares P, R, and S, and the second record compares Q, R, T, and U.


We assume that both records are correct. Return the smallest possible total number of planets in the solar system.

Constraints

  • A will contain between 2 and 50 elements, inclusive.
  • B will contain between 2 and 50 elements, inclusive.
  • Each element in A will be between 1 and 1,000,000,000, inclusive.
  • Each element in B will be between 1 and 1,000,000,000, inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{1,2,1,2,1}
{2,1,2,1,2}
Returns: 6

There have to be at least 5 planets, because each record compares 5 of them. There cannot be exactly 5 planets, because the first one would have to be both smaller than and larger than the second one. (Their ratio would have to be both 1:2 and 2:1, which is impossible.) There can be exactly 6 planets with relative sizes 1,2,1,2,1,2.

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

There can be only 4 planets because 1:2:3:4 = 2:4:6:8.

2)
{2,3,2,3,2,3,2}
{600,700,600,700,600,700,600}
Returns: 10
3)
{1,2,3,4,5,6,7,8,9}
{6,7,8,9,10,11,12}
Returns: 12
4)
{100000000,200000000}
{200000000,100000000}
Returns: 3

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

Coding Area

Language: C++17 · define a public class AstronomicalRecords with a public method int minimalPlanets(vector<int> A, vector<int> B) · 205 test cases · 2 s / 256 MB per case

Submitting as anonymous