Connection Status:
Competition Arena > MultiplicationTable

MultiplicationTable

SRM 662 · 2015-06-30 · by cgy4ever

SRM 662 · 2015-06-30 · by cgy4ever · Advanced Math
Class Name: MultiplicationTable
Return Type: int[]
Method Name: getMultiplicationTable
Arg Types: (vector<int>)
Problem Statement

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.)

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 }

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

Coding Area

Language: C++17 · define a public class MultiplicationTable with a public method vector<int> getMultiplicationTable(vector<int> firstRow) · 35 test cases · 2 s / 256 MB per case

Submitting as anonymous