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

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

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

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.

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/

My code n^3logn solution also gives TLE when i used Trie base based(with use of pointer).(I think it is impossible to pass a n^4 solution). I got frusteded but then i use Trie based solution with use of array only without use of pointer. And then magic happen and my solution pass like miracle but the time complexity is still n^3logn. But my time is far worse than a n^4 solution coded by my friend. Why this happen?? My both solution are here and here.

Problem link in practice not working

Practice link for this problem is not working.Please resolve this.

Please explain how CR=CB⊕CG⊕CY⊕CP works.

Please explain how CR=CB⊕CG⊕CY⊕CP works.

link to pratice https://www.codechef.com/problems/CHEFAXR

How to solve this question in O(N^2)??