CCC '05 S3 - Quantum Operations - Olympiads Online Judge

CCC '05 S3 - Quantum Operations

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Python 2 2.5s

Python 3 2.5s

Memory limit: 256M

Python 2 64M

Python 3 64M

Problem type

Canadian Computing Competition: 2005 Stage 1, Senior #3

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 concept 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 (using the symbol $\otimes$ ~\otimes~). This is different than the normal product of matrices that you may have learned about.

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

$\displaystyle A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix},\ B = \begin{bmatrix} b_{11} & b_{12} & \cdots & b_{1q} \\ b_{21} & b_{22} & \cdots & b_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ b_{p1} & b_{p2} & \cdots & b_{pq} \end{bmatrix}.$

Notice that the size of matrix $A$ ~A~ is $m \times n$ ~m \times n~ ( $m$ ~m~ rows and $n$ ~n~ columns), and the size of $B$ ~B~ is $p \times q$ ~p \times q~.

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

$\displaystyle A \otimes B = \begin{bmatrix} a_{11}[B] & a_{12}[B] & \cdots & a_{1n}[B] \\ a_{21}[B] & a_{22}[B] & \cdots & a_{2n}[B] \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1}[B] & a_{m2}[B] & \cdots & a_{mn}[B] \end{bmatrix},$

where $a_{ij}[B]$ ~a_{ij}[B]~ simply indicates that each element in $B$ ~B~ is being multiplied by $a_{ij}$ ~a_{ij}~.

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

For more than two matrices, we will define $A \otimes B \otimes C = (A \otimes B) \otimes C$ , although it 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 Specification

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

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

Output Specification

The output (to the screen) will be 6 integers in the following order:

the maximum element in the tensor product
the minimum element 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$ ~1024~ rows and no more than $1024$ ~1024~ columns.

Sample Input 1

Sample Output 1

Tensor Product for Sample Input 1

Sample Input 2

Sample Output 2

Tensor Product for Sample Input 2

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

Comments

26

milan3sa commented on June 18, 2020, 10:09 p.m.

When the first two paragraphs are a bunch of random words you don't understand!

9

Kirito commented on Sept. 14, 2016, 3:43 a.m. ← edited →

What are the bounds on $N$ ~N~?

1

noYou commented on July 6, 2020, 10:23 p.m. ← edited →

$N \le 16$ ~N \le 16~

0

noYou commented on July 6, 2020, 8:00 p.m.

Probably doesn't matter too much to the actual problem, considering best solutions are able to do 10 cases in 0.02s

3

aCookieBreak commented on Sept. 15, 2016, 1:44 a.m. ← edited →

"You may assume that the tensor product matrix will have no more than $1024$ ~1024~ rows and no more than $1024$ ~1024~ columns."

8

mmun commented on Sept. 16, 2016, 4:28 p.m. ← edited →

That doesn't necessarily put a bound on $N$ ~N~ if matrices can be $1 \times 1$ ~1 \times 1~.

0

noYou commented on July 13, 2020, 8:35 p.m. ← edited →

It should place a bound on the intended solution's size. having 10 $2 \times 2$ ~2 \times 2~ matrices come together to form it would be only marginally less efficient than a single $1024 \times 1024$ ~1024 \times 1024~ matrix.