PROBLEM STATEMENT
Multi-dimensional arrays with dimensions (N1, N2, N3,..., Nm) require the
amount of storage proportional to N1*N2*N3*...*Nm. When only a very small
fraction of the elements have non-empty values, using true multi-dimensional
arrays is inefficient (or even not feasible when Ni and m are large). In such
cases implementations of sparse arrays are used. Sparse arrays provide
functionality of real multi-dimensional arrays, but store only non-empty
elements.
You are designing a program to test an implementation of sparse arrays. Given a
sequence of assignments to elements of a sparse array, your program needs to
figure out values in the cells of the simulated multi-dimensional array.
DEFINITION
Class name: SparseArray
Method name: process
Parameters: int[], String[], String
Return type: int
Method signature (be sure your method is public): int process (int[]
dimensions, String[] assignments, String query);
The number of elements in the dimensions argument equals the number of
dimensions in the sparse array; values of dimensions define limits for indexes
in each dimension of the sparse array. For example, if dimensions =
{1000,1000,1000,1000}, a sparse array with four dimensions is defined, with
valid indexes 0 through 999, inclusive, in each dimension.
Elements of assignments are formatted as follows (quotation marks are for
clarity only):
"N1,N2,N3,..,Nm=Value"
N1..Nm are coma-separated indexes or index ranges (see below). The number of Ni
will be equal to the number of dimensions in the array. Value is an int in the
range from 0 to 1000, inclusive.
String query is formatted as follows:
"N1,N2,N3,..,Nm"
N1..Nm are coma-separated indexes or index ranges (see below). The number of Ni
will be equal to the number of dimensions in the array.
Each Ni above is formatted as either:
- A non-negative integer representing a single index, or
- A non-negative integer preceded by a '<' sign, representing all indexes from
zero to this number, excluding the number itself, or
- A non-negative integer preceded by a '>' sign, representing all indexes from
this number to the highest index in this dimension, excluding the number
itself, or
- An asterisk '*' representing all valid indexes in the corresponding dimension.
For example, ">500,<600,300,*=200" assigns 200 to all array elements in the
segment of the array where the first index is greater than 500, the second
index is less than 600, and the third index equals 300; note how this
assignment disregards the value of the forth index. Assignment "*,*,*,*=0" sets
all elements of a four-dimensional array to zero.
String query will be limited to a single index range - all other Ni will be
integer values. For example, "1,*,2,3" is a valid query, because it contains a
single range "*". "1,<4,2,>3", on the other hand, is not a valid query: it
contains two ranges, "<4" and ">3".
Your method should return the value of the element specified by the query. When
the query does not contain a range, return the value at the specified location
in the sparse array; when the query contains a range, return the sum of all
elements in the segment of the array specified by the range. If any element
that is required to compute the result has not been assigned to, your method
should return -1.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- dimensions has 1 to 10 elements, inclusive.
- Elements of dimensions are in the range from 1 to 1000, inclusive.
- assignments contains 0 to 50 elements, inclusive.
- All elements of assignments and the query are formatted as described above.
- All assigned values will be in the range from 0 to 1000, inclusive.
- The number of indexes or ranges in the assignments and the query equals the
number of dimensions.
- The query argument contains at most one range.
- The query references at least one element.
- All integer values used in the assignments and the query are in the valid
range for that dimension. This applies to both single indexes and '<' and '>'
ranges.
NOTES
- An assignment for a particular location that occurs later in the String[]
assignments will overwrite a prior assignment to that location. See Example 6.
- Queries always reference at least one element. For example, if
dimensions={5}, queries "<0" or ">4" are illegal.
EXAMPLES
1. When dimensions={10}, assignments={"5=1"}, and query="5", your method should
return 1.
2. When dimensions={10}, assignments={"5=2"}, and query="6", your method should
return -1.
3. When dimensions={10}, assignments={"<5=3"}, and query="6", your method
should return -1.
4. When dimensions={10}, assignments={">5=4"}, and query="6", your method
should return 4.
5. When dimensions={10}, assignments={"*=5"}, and query="6", your method should
return 5.
6. When dimensions={10}, assignments={"5=1","5=2","5=3"}, and query="5", your
method should return 3.
7. When dimensions={3,10}, assignments={"1,*=1","2,*=2","0,*=3"}, and
query="*,4", your method should return 6.
8. When dimensions={3,10}, assignments={"1,*=1","2,<4=2","0,*=3"}, and
query="*,4", your method should return -1.
9. When dimensions={1000,1000,1000,1000,1000,1000,1000,1000,1000,1000},
assignments={"*,*,*,*,*,*,*,*,*,*=5","1,2,3,4,5,6,7,8,9,10=11"}, and
query="1,2,3,4,5,6,7,8,9,*", your method should return 5006.
10. When dimensions={1000,1000,1000,1000,1000,1000,1000,1000,1000,1000},
assignments={"*,*,*,*,*,*,*,*,*,*=5","1,2,3,4,5,6,7,8,9,10=11"}, and
query="10,9,8,7,*,5,4,3,2,1", your method should return 5000.