Given a 2d array of N * M, find the max XOR of all elements of a sub-matrix. Problem Link.
N <= 10000 and M <= 20. Time limit: 1s. Memory limit: 256
I tried to go through all possible subarray [l...r] on M and calculated its xor. Then for each [l...r] I traversed all rows and then calculated the max xor of this [l...r]*Ni rectangle using trie.
When trie is implemented using struct I'm getting TLE. But, array implementation of trie is giving Accepted verdict. I don't understand what's the difference in time complexity. Isn't it the same?
TLE Solution
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define BOOST \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
int it = 0;
const int N = 2;
struct node{
node* arr[N];
int vis[N];
};
node* getNode()
{
node* n = new node;
for(int i = 0; i < N; i++)
{
n->arr[i] = NULL;
n->vis[i] = it;
}
return n;
}
void insert(node *root, int n)
{
node *tmpRoot = root;
for(int i = 28; i >= 0; i--)
{
int index = ((n >> i) & 1);
tmpRoot->vis[index] = it;
if(tmpRoot->arr[index] == NULL)
{
tmpRoot->arr[index] = getNode();
}
tmpRoot = tmpRoot->arr[index];
}
}
int search(node *root, int n)
{
node *tmpRoot = root;
int ans = 0;
for(int i = 28; i >= 0; i--)
{
int index = ((n >> i) & 1);
if(tmpRoot->arr[index^1] && tmpRoot->vis[index^1] == it)
{
ans += (1 << i);
tmpRoot = tmpRoot->arr[index^1];
}else
{
tmpRoot = tmpRoot->arr[index];
}
}
return ans;
}
void solve()
{
int n, m;
cin >> n >> m;
int v[n + 5][m + 5];
for (int i = 0; i <= n; i++)
{
v[i][0] = 0;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> v[i][j];
v[i][j] ^= v[i][j - 1];
}
}
node *root = getNode();
int mxor = 0;
for (int l = 1; l <= m; l++)
{
for (int r = l; r <= m; r++)
{
int rowXor = 0;
insert(root, 0);
for (int i = 1; i <= n; i++)
{
rowXor = (rowXor ^ v[i][r] ^ v[i][l - 1]);
int k = search(root, rowXor);
mxor = max(mxor, rowXor);
mxor = max(mxor, k);
insert(root, rowXor);
}
it++;
}
}
cout << mxor << endl;
}
int main()
{
solve();
}
AC Solution
#include <bits/stdc++.h>
using namespace std;
int trie[10001*28][2],node;
void insert(int n)
{
int root = 1;
for(int i = 27; i >= 0; i--)
{
int idx = (1 & (n >> i));
if(!trie[root][idx])
{
trie[root][idx] = node++;
}
root = trie[root][idx];
}
}
int search(int n)
{
int root = 1;
int res = 0;
for(int i = 27; i >= 0; i--)
{
int idx = (1 & (n >> i));
if(trie[root][idx^1])
{
res += (1 << i);
root = trie[root][idx^1];
}else
{
root = trie[root][idx];
}
}
return res;
}
void solve()
{
int n, m;
cin >> n >> m;
int v[n + 5][m + 5];
for (int i = 0; i <= n; i++)
{
v[i][0] = 0;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> v[i][j];
v[i][j] ^= v[i][j - 1];
}
}
int mxor = 0;
for (int l = 1; l <= m; l++)
{
for (int r = l; r <= m; r++)
{
memset(trie,0,sizeof trie);
node = 2;
int rowXor = 0;
insert(0);
for (int i = 1; i <= n; i++)
{
rowXor = (rowXor ^ v[i][r] ^ v[i][l - 1]);
int k = search(rowXor);
mxor = max(mxor, rowXor);
mxor = max(mxor, k);
insert(rowXor);
}
}
}
cout << mxor << endl;
}
int main()
{
solve();
}
Also, I see that somebody has solved it without trie. How to solve it without trie?
Without TRIE solution
#include<bits/stdc++.h>>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m, a[10005][22], arr[22], tg, res;
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> a[i][j];
for(int x = 1; x <= 18; x++)
{
for(int j = 1; j <= m; j++)
arr[j] = 0;
for(int i = x; i <= n; i++)
{
tg = 0;
for(int j = 1; j <= m; j++)
{
arr[j] = arr[j] ^ a[i][j];
tg = max(tg, max(arr[j], arr[j] ^ tg));
}
res = max(res, tg);
}
}
cout << res;
return 0;
}
