In this HackerEarth Micro's House problem solution Our coder Micro, is building a new house. For that he bought a rectangular plot few days back. The plot is very big, so he decided that he will use some portion of the plot to make his house, and the rest he will use for playing cricket with his astrologer friend Mike. But Micro is very superstitious, he is not going to just randomly pick some portion to build his house. He want to maximize his good luck. For this he took help of Mike.
Mike divided the whole plot into grid of square blocks and assigned a Good Luck value to each. The size of the grid was N * M. For some unknown reasons Mike kept N ≥ M. Now he calculates the Good Luck value of a rectangular portion (rectangular sub matrix) as xor of Good Luck value of all square blocks in that rectangular portion. Help Micro in finding out the maximum Good Luck value he can achieve.
HackerEarth Micro's House problem solution.
#include<bits/stdc++.h>
#define ll long long
#define gc getchar_unlocked
#define pc putchar_unlocked
#define repl(i, a, b) for(i=a; i<b; i++)
#define repe(i, a, b) for(i=a; i<=b; i++)
#define per(i, a, b) for(i=a; i>=b; i--)
#define vi vector<int>
#define vl vector<long>
#define vll vector<long long>
#define pb(x) push_back(x)
#define lt(i) (i<<1)
#define rt(i) ((i<<1)+1)
#define mp(a, b) make_pair(a, b)
#define ln length()
#define sz size()
#define md(a, b) ((a+b)>>1)
#define pii pair<int, int>
#define pll pair<long, long>
#define pLL pair<long long, long long>
#define all(v) v.begin(),v.end()
#define pn pc('\n');
using namespace std;
void sll(ll &x)
{
register char c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
void wll(ll a)
{
if(a<0)
{
pc('-');
a=-a;
}
char snum[100];
int i=0;
do
{
snum[i++]=a%10+48;
a=a/10;
}
while(a!=0);
--i;
while(i>=0)
putchar_unlocked(snum[i--]);
putchar_unlocked('\n');
}
void wi(int a)
{
if(a<0)
{
pc('-');
a=-a;
}
char snum[100];
int i=0;
do
{
snum[i++]=a%10+48;
a=a/10;
}
while(a!=0);
--i;
while(i>=0)
putchar_unlocked(snum[i--]);
putchar_unlocked('\n');
}
void wl(long a)
{
if(a<0)
{
pc('-');
a=-a;
}
char snum[100];
int i=0;
do
{
snum[i++]=a%10+48;
a=a/10;
}
while(a!=0);
--i;
while(i>=0)
putchar_unlocked(snum[i--]);
putchar_unlocked('\n');
}
void sl(long &x)
{
register char c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
void si(int &x)
{
register char c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
ll power(ll a, ll b, ll mod)
{
ll ret = 1 ;
while(b)
{
if(b & 1 ) ret = ret*a % mod;
a = a*a % mod;
b >>= 1 ;
}
return ret;
}
ll gcd(ll a, ll b)
{
while(b) b ^= a ^= b ^= a %= b;
return a;
}
struct trie{
trie *child[2];
};
struct parent{
trie *t;
};
trie arr[2000000];
int cnt;
void insert(trie *t, ll val)
{
ll i, j;
per(i,31,0)
{
j=((1<<i)&val)?1:0;
if(!t->child[j])
{
arr[cnt].child[0]=arr[cnt].child[1]=NULL;
t->child[j]=&arr[cnt];
cnt++;
}
t=t->child[j];
}
}
ll query(trie *t, ll val)
{
ll i, j, ret=0;
per(i,31,0)
{
j=((1<<i)&val)?1:0;
if(t->child[!j])
{
j=!j;
ret^=(1<<i);
}
t=t->child[j];
}
return ret;
}
ll mat[30000][300];
int main()
{
ll t, i, j, k, l;
ll n,m;
sll(n);sll(m);
repe(i,1,n)
repe(j,1,m){
sll(mat[i][j]);
mat[i][j]^=mat[i][j-1];
}
ll ans=-1;
repe(i,1,m){
repe(j,i,m){
ll val=0;
parent p;
cnt=1;
arr[0].child[0]=arr[1].child[1]=NULL;
p.t=&arr[0];
insert(p.t, 0);
repe(k,1,n){
val^=mat[k][i-1]^mat[k][j];
ans=max(ans, query(p.t, val));
insert(p.t, val);
}
}
}
wll(ans);
return 0;
}Second solution
#include <bits/stdc++.h>
using namespace std;
int N, M;
int A[10001][16];
int B[10001];
int trie[10001*31][2], nxt;
void add(int x)
{
int root=1;
for(int i=30; i>=0; i--)
{
int b=(x>>i)&1;
if(!trie[root][b])
trie[root][b]=nxt++;
root=trie[root][b];
}
}
int ask(int x)
{
int ret=0;
int root=1;
for(int i=30; i>=0; i--)
{
int b=(x>>i)&1;
if(trie[root][b^1])
{
ret|=1<<i;
root=trie[root][b^1];
}
else
root=trie[root][b];
}
return ret;
}
int main()
{
scanf("%d%d", &N, &M);
assert(1<=N && N<=10000);
assert(1<=M && M<=15);
assert(N>=M);
for(int i=1; i<=N; i++)
{
for(int j=1; j<=M; j++)
{
scanf("%d", A[i]+j);
assert(1<=A[i][j] && A[i][j]<=100000000);
A[i][j]^=A[i][j-1];
}
}
int ans=0;
for(int j=1; j<=M; j++)
{
for(int k=j; k<=M; k++)
{
memset(trie, 0, sizeof trie);
nxt=2;
add(0);
for(int i=1; i<=N; i++)
{
B[i]=B[i-1]^A[i][j-1]^A[i][k];
ans=max(ans, ask(B[i]));
add(B[i]);
}
}
}
printf("%d\n", ans);
return 0;
}
0 Comments