http://www.codechef.com/problems/RESN01
I thought my algorithm is correct but it is giving wrong answer. To solve the problem i have tried to scan for every bit of integers. Say, the maximum integer has bits Cbit. For each bit j = Cbit to 0, I checked for every integer Ai whither there is an integer x which has j-th bit 0 and whither index of x has distance <= K from Ai. If so, then i have set the j-th bit of Ai to zero. This algorithm has running time O(N* bit). It is passing all the test case i have tried. But somehow it is giving wrong answer on CodeChef’s Judge. Why the algorithm is not working ?
My algo
int CountBit(int n)
{
unsigned int c; // c accumulates the total bits set in v
for (c = 0; n; c++)
n = n >>1; // clear the least significant bit set
return c;
}
int main()
{
int test,i,j, sum;
int *A;
int N, K;
int max;
int cBIT;
scanf("%d",&test);
while(test--)
{
N = read_int();
K = read_int();
max = -1;
A = new int[N+2];
FOR(i,1,N)
{
A[i] = read_Int();
if(A[i] > max) max = A[i];
}
A[0] = A[N];
A[N+1] = A[1];
cBIT = CountBit(max);
// cout<<cBIT<<endl;
// int *lastPos0 = new int[N+2];
// FOR(i,1,N)
// lastPos0[i] = N+2;
int lstZeroBit = -1;
int bit;
while(cBIT>=1)
{
lstZeroBit = -1;
FOR(i,0,N)
{
int bit = (A[i] & ( 1 << (cBIT-1))) >> (cBIT-1);
if( lstZeroBit!= -1 && (i - lstZeroBit) <= K)
{
A[i] &= ~(1u << (cBIT - 1) ) ;
}
if(bit==0)
{
lstZeroBit = i;
}
}
lstZeroBit = -1;
for(i=N+1;i>0;i--)
{
int bit = (A[i] & ( 1 << (cBIT-1))) >> (cBIT-1);
if(lstZeroBit != -1 && (lstZeroBit - i) <= K)
{
A[i] &= ~(1u << (cBIT -1)) ;
}
if(bit==0)
{
lstZeroBit = i;
}
}
cBIT--;
}
printf("%d",A[1]);
FOR(i,2,N)printf(" %d",A[i]);
printf("\n");
}
}