I have been trying to solve ‘Magic bitwise AND’ from SPOJ classical problem set:
Problem Link
But I am repeatedly getting wrong answer.I am using the property of ‘bitwise and’ that ‘bitwise and’ of a and b is less than or equal to smaller of two. So I created a reference array ‘ands’ such that ands[i] is a[i]&a[i+1]&…a[n-1] where ‘a’ is the input array sorted in increasing order.Such that if ‘&’ of already selected elements (curr) and ands[i] (since ands[i] will be equal to smallest of (a[i…n],& of a[i…n])) is greater than current ans then return since now selecting any aj from j=i to j=n-1 won’t lead to any decrease in ans.Also if count reaches k or index reaches n(number of elements in a) return.
Beside this I am selecting a subset in a naive recursive manner.And since max ai is 2^60,
I am initializing ans with 2^63 -1.
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <cstring>
#include <queue>
#include <cassert>
#include <algorithm>
#define mod 1000000007
using namespace std;
typedef unsigned long long ll;
typedef long double ld;
vector<ll> a;
ll n,k,ans,ands[100];
inline ll Scan_f()
{
ll noRead=0;
//register char p=getchar_unlocked();
register char p=getc(stdin);
//for(;p<48 || p>57;p=getchar_unlocked());
for(;p<48 || p>57;p=getc(stdin));
//while(p>47 && p<58){ noRead = (noRead << 3) + (noRead << 1) + (p - '0');p=getchar_unlocked();}
while(p>47 && p<58){ noRead = (noRead << 3) + (noRead << 1) + (p - '0');p=getc(stdin);}
return noRead;
};
void solve(int idx,int cont,ll curr)
{
ll tp;
ans = min(ans,curr);
if(idx == n || cont == k)
return;
tp = curr&ands[idx];
if(tp >= ans)
return;
tp = curr&a[idx];
solve(idx+1,cont+1,tp);
solve(idx+1,cont,curr);
}
int main()
{
//freopen("input2.txt","r",stdin);
long int i,j,T;
ll temp,tp;
temp = 1;
for(i=1;i<=63;i++)
{
temp = temp*2;
}
temp = temp-1;
T = Scan_f();
while(T > 0)
{
n = Scan_f();
k = Scan_f();
for(i=0;i<n;i++)
{
tp = Scan_f();
a.push_back(tp);
}
sort(a.begin(),a.end());
for(j=0;j<n;j++)
{
ands[j] = a[j];
for(i=j;i<n;i++)
{
ands[j] = a[i]&ands[j];
}
}
ans = temp;
solve(0,0,temp);
printf("%llu\n",ans);
a.clear();
memset(ands,temp,sizeof(ands));
T--;
}
return 0;
}