Chef and Submatrix
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef has a square matrix A. He would like to choose a consecutive sub-matrix of A such that value of bitwise XOR of all elements in it is maximal.
Each sub-matrix can be defined by four numbers (x1,y1,x2,y2), with the meaning that the submatrix contains an element A[i][j] iff x1 ≤ i ≤ x2 and y1 ≤ j ≤ y2.
You can read more about bitwise XOR operation here.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the size of the matrix A.
The following N lines contain N space-separated integers, denoting values of elements in given matrix. The j-th element in the i-th line denotes the value of A[i][j].
For each test case, output a single line containing the maximal bitwise XOR a submatrix of A
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 70
- 1 ≤ Ai,j ≤ 109
- Subtask 1 (40 points): 1 ≤ N ≤ 20
- Subtask 2 (60 points): 1 ≤ N ≤ 70
Input: 1 3 1 4 3 1 8 6 1 2 3 Output: 15
Chef can pick the following submatrix in order to make the XOR of elements equal to 15:
1 4 3 1 8 6 1 2 3
This submatrix can be defined by x1 = 1, y1 = 1, x2 = 3, y2 = 2.
|Tags||bit, easy, furko, ltime25, matrix, xor|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.