PROBLEM STATEMENT
In this problem, you will be given descriptions of several integer sequences, and you will be
required to return elements at certain positions of the union of all the given sequences. The
union of several sequences is a sequence containing all the elements of those sequences, sorted in
non-decreasing order. For each integer x, the number of occurrences of x in the union is equal to
the total number of occurrences of x in all the given sequences. For example, if we are given
sequences (3, 2, 2, 3), (1) and (5, 7, 1), their union is the sequence (1, 1, 2, 2, 3, 3, 5, 7).
Each of the given sequences will be an arithmetic sequence, a geometric sequence or an explicit
sequence.
An arithmetic sequence is described by three positive integers A, B and C. The sequence contains
exactly C elements: A, A+B, A+B+B, ..., A+B*(C-1). Formally, the sequence is { A+B*x | x an
integer between 0 and C-1, inclusive}.
A geometric sequence is described by three positive integers A, B and C. The sequence contains
exactly C elements: A, A*B, A*B*B, ..., A*B^(C-1). Formally, the sequence is { A*B^x | x an
integer between 0 and C-1, inclusive}.
An explicit sequence is just a non-empty sequence of arbitrary positive integers.
Each sequence will be represented as a string, where the first character is 'A', 'G' or 'E',
denoting arithmetic, geometric or explicit sequences, respectively. The second character will
always be a space. After that is a list of positive integers, where each integer is written with
no leading zeroes, consecutive integers are separated by a single space, and there are no leading
or trailing spaces. In the case of arithmetic and geometric sequences, this list will always
contain exactly three integers, A, B and C, in that order, as described above for each type of
sequence. For explicit sequences, the list will contain one or more integers, explicitly
representing the members of the sequence.
You will be given a vector seqs, where each element represents a sequence as described in
the previous paragraph, and a vector positions, which contains a list of 1-based positions.
Return a vector containing the same number of elements as positions, such that its i-th
element is the element at position positions[i] of the union of all the sequences in seqs. If the
union contains less than positions[i] elements or if the element at position positions[i] of the
union is strictly greater than 1000000000 (10^9), the i-th element of the return must be -1
instead. See examples for further clarification.
DEFINITION
Class:SequenceMerger
Method:getVal
Parameters:vector , vector
Returns:vector
Method signature:vector getVal(vector seqs, vector positions)
NOTES
-The elements of the given sequences don't necessarily fit within 32-bit or 64-bit integer types.
CONSTRAINTS
-positions will contain between 1 and 50 elements, inclusive.
-Each element of positions will be between 1 and 1000000000 (10^9), inclusive.
-seqs will contain between 1 and 50 elements, inclusive.
-Each element of seqs will contain between 3 and 50 characters, inclusive.
-Each element of seqs will be formatted as described in the problem statement.
EXAMPLES
0)
{"E 1 1000000000 1000000001"}
{1,2,3,4}
Returns: {1, 1000000000, -1, -1 }
The sequence here has only 3 elements. The first two elements are returned normally. The element
at position 3 is strictly greater than 1000000000, so you must return -1 in that place. There is
no element at position 4, so you must also return -1 there.
1)
{"A 1 1 10", "G 1 2 4"}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
Returns: {1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9, 10, -1 }
The arithmetic sequence is 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. The geometric sequence is 1, 2, 4, 8.
Therefore, the resulting sequence is 1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9, 10.
2)
{"A 1000000000 1000000000 1000000000","G 100000000000000000 1000000000000 100000000000000", "E
1000000000000000 10000000 10 1111"}
{1,2,3,4,5,6,7,8,9,10}
Returns: {10, 1111, 10000000, 1000000000, -1, -1, -1, -1, -1, -1 }
Watch out for big numbers.
3)
{"G 1 1 999999999", "E 2"}
{1,999999999,1000000000}
Returns: {1, 1, 2 }
A lot of 1s and a 2.
4)
{"A 100 341 1524", "G 1 3 45235", "E 653 87 12341 8785 123 543"}
{100000,1,10,10000,100,1000}
Returns: {-1, 1, 441, -1, 28403, 334621 }
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)2010, TopCoder, Inc. All rights reserved.