CHEFAXR - Editorial

PROBLEM LINK:

Practice
Contest

Author: Roman Furko
Testers: Pushkar Mishra and Sergey Kulik
Editorialist: Pawel Kacprzak
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng

DIFFICULTY:

Easy

PREREQUISITES:

bits, implementation

PROBLEM:

You are given a square matrix A of size N. For a submatrix B of A, we define its value as the bitwise XOR of all elements of B. Your task is to find the maximum value among all submatrices of A.

QUICK EXPLANATION:

Since N \leq 70, if we are able to compute a value for a given submatrix in constant time, we can iterate over all submatrices and return the maximum value. In order to compute the value for a given submatrix fast, we first compute values of all submatrices which have the upper-left corner at (1, 1). Then we can use these values to compute every other value using properties of XOR operation.

EXPLANATION:

Let C[i][j] be the value of the submatrix which has its upper left corner at (1, 1) and its bottom right corner in (i, j). We can compute the C table in O(N^4) or O(N^3), or even O(N^2), but since N is quite small, it does not matter which method you choose.

After that, we notice the major property of XOR, i.e. x \oplus x = 0. Using this property and precomputed table C, we can easily compute the value for any submatrix R in constant time. Let’s consider the below illustration and define 5 submatrices:

  1. R, the Red submatrix, we are
    interested in computing its value
  2. B, the Blue submatrix, we have its
    value computed and stored in C
    table
  3. G, the Green submatrix, we have
    its value computed and stored in C
    table
  4. Y, the Yellow submatrix, we have
    its value computed and stored in C
    table
  5. P, the Purple submatrix, we have
    its value computed and stored in C
    table

alt text

Let’s define, for the above matrices, C_X to be the value from C table for a submatrix X, for example C_R is the value of the matrix R. Then C_R = C_B \oplus C_G \oplus C_Y \oplus C_P

This is duo to the major property of XOR and the fact that both C_G and C_Y contain C_P as a submatrix.

Time complexity

For a single test case it is O(N^4) because we can compute the C table in O(N^4); and we compute the value for every submatrix in a constant time, and there are O(N^4) different submatrices.

AUTHOR’S AND TESTER’S SOLUTIONS:

Tester

4 Likes

Can someone provide some testcases please? because i think my solution is correct. but still giving me WA.
Thanks

http://www.codechef.com/viewsolution/7297522

Nice editorial :slight_smile:
Can you please explain the O(N^2) or O(N^3) method for precomputation?
Thanks

http://www.codechef.com/viewsolution/7297553

My solution was something like finding maximum sum submatrix in which instead of Kadane i use Trie based solution to find maximum xor subarray.
According to me complexity of this solution certainly looks better than O(n^4) to be exact O((n^3)*32).But still I got TLE for 2nd subtask.And was one major reason i didn’t use O(N^4) solution.
Can someone help me where am i going wrong??

@franky Notice that method which I described in the editorial takes about O(N^4 / 4) with a very small constant

@yashv For O(N^3) you can first compute table row[N][N]] where, row[i][j] = a[i][0] ^ a[i][1] ^ … ^ a[i][j] and col[j][i] = a[0][j] ^ a[1][j] ^ … ^ a[i][j]. These tables can be computed in O(N^2). In the C table we have O(N^2) entries and you can compute C[i][j] in constant time xoring C[i - 1][j] with row[i][j]

2 Likes

How can we neglect 10 test cases! O(N^4) is required for precomputaion for every test case. So, how does that solution passed in 1 second and trie tree implementation got tle(I accept that constant is small for that O(N^4) solution. Plz explain! :confused:

please add link to pratice problem…

1 Like

can someone please check my solution … can’t figure out what’s wrong …:frowning: http://www.codechef.com/viewsolution/7295735

I don’t know why kadane’s famous algorithm was given WA…
please someone tell what’s wrong in my code …
http://www.codechef.com/viewsolution/7297962

Thanks. That helped.

why is n^4 accepted ? 70 ^ 4= 24010000=2*10^7. for a single test case for 10 test case this amounts to 10^8. :confused:

pratise problem still not accessible :frowning:

@ayushtomar, because of the same reason i thought my code will give a TLE. But may be because only very few constant time operations are being performed in the 4 time nested loop,it was Accepted for all who got a 100.

@mithunmk93 i was also thinking the same . :confused: Will keep this in mind next time

Practice link of this problem is broken. Someone concerned please rectify it soon.

1 Like

Where is link for practice session?

Practice link ? -_-

you can find here in more detail:http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

Please refer to tester’s solution for N^2 preprocessing

//