1

Given :

Matrix consist of $n$ rows and m columns

For each row the xor of all elements in that row (suppose if there are 5 rows in a matrix then 5 numbers will be given representing the xor of each row)

For each column the xor of all element in that column

Task:

If it is possible to form a matrix then print the elements of that matrix

I found this in the editorial

If $a_1\oplus a_2 \oplus\cdots\oplus a_n\neq b_1 \oplus b2 \oplus\cdots\oplus b_m$ , then there is no suitable matrix. The operation means xor.

Otherwise, we can always construct a suitable matrix by the following method: the first element of the first line will be equal to `$a_1 \oplus b_2 \oplus b_3 \oplus\cdots\oplus b_m$. The second element of the first line is $b_2$, the third element is $b_3$, the last one is $b_m$.

The first element of the second line will be $a_2$, the first element of the third line is $a_3$, the first element of the last line is an. The rest of the elements will be zero.

It is not difficult to verify that the matrix obtained satisfies all the restrictions.

I tried reading https://codeforces.com/contest/1016/problem/D , but I didn't understand how the elements of matrix are calculated. Please can someone explain it with example.

Xander Henderson
  • 29,772
akashking
  • 83

1 Answers1

1

The point is that xor is a commutative and associative operation, so the xor of the xors of the rows must be the same as the xor of the xors of the columns.

For example if the matrix is

$$\pmatrix{1 & 2 & 3\cr 4 & 5 & 6\cr}$$

we have $$1 \oplus 2 \oplus 3 \oplus 4 \oplus 5 \oplus 6 = (1 \oplus 2 \oplus 3) \oplus (4 \oplus 5 \oplus 6) = (1 \oplus 4) \oplus (2 \oplus 5) \oplus (3 \oplus 6)$$

EDIT: Let's say you want a $2 \times 3$ matrix $A$ where the xor's of the rows are $a = [4, 1]$ and the xor's of the columns are $b = [2, 3, 4]$. This does satisfy the condition. We take the first element of the first row to be $a_1 \oplus b_2 \oplus b_3 = 4 \oplus 3 \oplus 4 = 3$, the others $b_2 =3$ and $b_3 = 4$, the first element of the second row to be $a_2 = 1$, and all other elements $0$. Thus the matrix is $$ \pmatrix{3 & 3 & 4\cr 1 & 0 & 0\cr} $$

Robert Israel
  • 448,999
  • Please can you explain how the elements of matrix are calculated? – akashking Mar 27 '19 at 14:04
  • The logic of this line a1⊕b2⊕b3⊕⋯⊕bm – akashking Mar 27 '19 at 14:06
  • The solution is far from unique. This particular choice does work: the xor of the first row is $$(a_1 \oplus b_2 \oplus b_3 \ldots \oplus b_m) \oplus b_2 \oplus b_3 \ldots \oplus b_m = a_1$$ The xor of the first column is $$(a_1 \oplus b_2 \oplus b_3 \ldots \oplus b_m) \oplus a_2 \ldots \oplus a_n = b_1$$ (this is where the condition comes in). The other rows and columns are easy. – Robert Israel Mar 27 '19 at 14:29
  • can you tell me how did you get xor of first column that is 1⊕4 or b[0] as 2 because 1=0001 and 4=0100 there xor should be 0101 – akashking Mar 27 '19 at 16:13
  • The xor of the first column of my first example is indeed $3$, not $2$. Where did I claim it was $2$? It's the second example where the xor of the first column is $2$, and that's $3 \oplus 1$. – Robert Israel Mar 27 '19 at 16:33