CHEFAXR - Editorial

@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:Maximum sum rectangle in a 2D matrix | DP-27 - GeeksforGeeks

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 CHEFAXR Problem - CodeChef

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

For all who are asking why O(N^4 * 10) is been accepted! So answer is that there is a chance of weak test cases in 1< = T <= 10. May be all test cases would not able to cover N=70. otherwise in execution speed it impossible to get AC in (10^8 * 2) instruction according to the question!

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:

Thanks. That helped.

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

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