Computer Science Canada

[CCC 2005] Senior S3: Quantum Operations
Author:  zylum [ Sun Mar 06, 2005 6:55 pm ]
Post subject:  [CCC 2005] Senior S3: Quantum Operations
[CCC 2005] Senior S3: Quantum Operations

Quantum computing is currently a hot topic in research. If they can be built, quantum computers will have the ability to perform certain computing tasks much faster than any computer in existence today. Fortunately, you won't need a quantum computer to do this question.

A fundamental comcept in quantum computing is the idea of a quantum operation. A quantum operation can be essentially thought of as a matrix. Also, if you perform two quantum operations in parallel on separate quantum data, this can be thought of as a larger quantum operation. Thinking of these operations in terms of matrices again, the resulting matrix from performing two matrices in parallel is called the tensor product of the two matrices. This is different than the normal product of matrices that you may have learned about.

In a tensor product, your are given two matrices (which are essentially two-dimensional arrays). We will call them A and B, and we will represent the individual elements of these two matrices this way:

code:
     _                  _         _                  _
    | a11  a12  ...  a1n |       | b11  b12  ...  b1q |
A = | a21  a22  ...  a2n |   B = | b21  b22  ...  b2q |
    |  :    :   '-.   :  |       |  :    :   '-.   :  |
    |_am1  am2  ...  amn_|       |_bp1  bp2  ...  bpq_|


Notice that the size of matrix A is mxn (m rows and n columns), and the size of B is pxq.

The tensor product of these two matrices will be an mpxnq matrix (with mp rows and nq columns) that looks like:

code:
                        _                           _
                       | a11[B]  a12[B]  ...  a1n[B] |
A (tensor product) B = | a21[B]  a22[B]  ...  a2n[B] |
                       |  :       :      '-.   :     |
                       |_am1[B]  am2[B]  ...  amn[B]_| 


where aij(B) simply indicates that each element in B is being multiplied bay aij.

Finally notice that the tensor product is not commutative, which means that the changing the order of matrices may change the answer (A (tensor product) B not= B (tensor product) A).

For more than two matrices, we will define A()B()C = (A(tensor product)B)(tensor product)C, although if does not technically matter, since the tensor product is associative.

Your task is to compute and output the tensor product of two or more given matrices.

Input

The first line of input contains the number of matrices, N, a positive integer. Then, there are N blocks of lines describing the matrices in order.

In each block, the first line will contaion two positive integers, r, and c, separated by a space, indicating the number of rows and columns, respectively. Then, the next r lines will denote the rows, in order. Each line will contain c integers, separated by spaces. Input is contained in the file s3.in.

Output

The output (to the screen) will be 6 integers in the following order.
    the maximum element in the tensor product
    the minimum elemen in the tensor product
    the maximum row sum (i.e., sum of entries in each row)
    the minimum row sum
    the maximum column sum
    the minimum column sum


You may assume that the tensor product matrix will have no more than 1024 rows and no more than 1024 columns,

Sample Input 1

code:
2
2 2
1 1
1 -1
2 2
1 0
0 1


Output for Sample Input 1

code:
1
-1
2
0
2
0


Actual Tensor Product for Sample Input 1

code:
1 0 1 0
0 1 0 1
1 0 -1 0
0 1 0 -1


Sample Input 2

code:
3
2 2
1 0
0 3
2 2
1 1
1 -1
2 2
1 0
0 1


Actual Tensor Product for Sample Input 2

code:
1 0 1 0 0 0 0 0
0 1 0 1 0 0 0 0
1 0 -1 0 0 0 0 0
0 1 0 -1 0 0 0 0
0 0 0 0 3 0 3 0
0 0 0 0 0 3 0 3
0 0 0 0 3 0 -3 0
0 0 0 0 0 3 0 -3
Author:  AlphaWice [ Mon Mar 07, 2005 7:15 am ]
Post subject: 
soln 1: compute the tensor product

basically involves an array and 4 "for loops"


soln 2: a realization!

realize that, given matrices A and B, the maximum row sum of A*B can be found to also be the maximum of ( maxA*maxB, maxA*minB, minA*maxB, minA*minB ) and similarily for the others. This is because maxA and minA are the two sums with the largest magnitude, and we are just trying to find the largest magnitude that keeps everything positive.

The largest element can be found in a similar way.

The code can look something like this:

define 6 functions:
maxele(A): given an array A, computes the maximal element
minele(A): given array A, computes minimal element
maxrowsum(A): given A (an array) it computes the maximum row sum
maxcolsum(A)
minrowsum(A)
mincolsum(A) [similarily for all these]

Now get the matrices and store the 6 values for all of these matrices.

Now take any two matrices. We have 12 values. We can change this to 6 values using the idea above. Continue until we have 6 values; these values are the required.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy