JOIN
Get Time

   Problem Statement  

 Problem Statement for MultiplicationTable

Problem Statement

    Fox Ciel is creating a new binary operation.



The operation will be denoted * and it will be defined on the finite set S = {0, 1, 2, ..., n-1}. I.e., for each ordered pair of elements of S the operation will return some element of S. The operation can be described by its "multiplication table": a square table where in row i and column j we have the result returned by the operation i*j. Ciel has already filled in row 0 of this table: for each j we know that 0 * j = firstRow[j].



Ciel's operation doesn't have to be symmetric: it is possible that for some i and j the operations i*j and j*i return two different values. However, Ciel does want her operation to be associative: for all a,b,c in S, (a*b)*c must be equal to a*(b*c). (Note that this includes cases when some or all of a,b,c are equal to each other.)



You are given the int[] firstRow with n elements. If there is a way to fill in the rest of the multiplication table so that the resulting operation is associative, find one such way and return a int[] with n*n elements: all elements of the entire multiplication table, listed in row major order. If there are multiple solutions you may return any of them. If there are no solutions, return {-1}. (I.e., if there are no solutions, return a int[] of length 1 containing the element -1.)
 

Definition

    
Class:MultiplicationTable
Method:getMultiplicationTable
Parameters:int[]
Returns:int[]
Method signature:int[] getMultiplicationTable(int[] firstRow)
(be sure your method is public)
    
 

Constraints

-firstRow will contain between 2 and 50 elements, inclusive.
-Each element in firstRow will be between 0 and |firstRow|-1, inclusive.
 

Examples

0)
    
{1,2,0}
Returns: {1, 2, 0, 2, 0, 1, 0, 1, 2 }
The example return value corresponds to the following multiplication table:
* | 0  1  2
--+-----------
0 | 1  2  0
1 | 2  0  1
2 | 0  1  2  
In other words, this operation * can be defined using the following formula: i*j = (i+j+1) mod 3. We can easily verify that for any a,b,c both (a*b)*c and a*(b*c) evaluates to the same value: namely, to the value (a+b+c+2) mod 3.
1)
    
{1,1,1}
Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1 }
This time we can use: i*j = 1.
2)
    
{0,0,1}
Returns: {-1 }
Row 0 already tells us that 0*0 = 0, 0*1 = 0, and 0*2 = 1. Let's take a=0, b=0, and c=2. On one hand we already know that (a*b)*c = (0*0)*2 = 0*2 = 1. On the other hand we also know that a*(b*c) = 0*(0*2) = 0*1 = 0. Hence, regardless of how we fill in the rest of the table, the resulting operation will never be associative.
3)
    
{0,1}
Returns: {0, 1, 1, 1 }
4)
    
{2,3,0,1}
Returns: {2, 3, 0, 1, 3, 0, 1, 2, 0, 1, 2, 3, 1, 2, 3, 0 }
5)
    
{3,4,5,0,2,1}
Returns: {-1 }
6)
    
{0,1,2}
Returns: {0, 1, 2, 0, 1, 2, 0, 1, 2 }

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.

This problem was used for:
       Single Round Match 662 Round 1 - Division I, Level Three