### ashwin1907's blog

By ashwin1907, 5 years ago, ,

I am trying to solve AND Round http://www.spoj.com/problems/ANDROUND/

Problem Statement:

You are given a cyclic array A having N numbers. In an AND round, each element of the array A is replaced by the bitwise AND of itself, the previous element, and the next element in the array. All operations take place simultaneously. Can you calculate A after K such AND rounds?

Here is my approach.

Let the original array be A[N] and the final array be C[N].

(1) If 2*K+1 >= N, then C[i] = bitwise AND of all elements of A, for all i.

(2) Otherwise, C[i] = bitwise AND of 2*K+1 elements of A (centered at index i) i.e.

C[i] = bitwise AND of (A[i-K], A[i-K+1],...,A[i-1], A[i], A[i+1],..., A[i+K-1], A[i+K]) where the indexes are circular.

To implement this, I have constructed another array B to handle the circularity. Let B = A'+A+A, where A' = reverse of A. Now, I have used a segment tree built on top of array B to compute the bitwise AND of a range of elements.

I am getting Wrong Answer. Is there anything fundamentally wrong in this approach?

Here is my code.

#include<algorithm>
using namespace std;

typedef long long LL;
#define INF 1000000000000000LL

LL *segtree;
LL array[30001];
LL arr[90001];

void init_segtree(LL idx, LL b, LL e)
{
if (b == e)
{
segtree[idx] = arr[b];
return;
}
int mid = (b+e)>>1;
init_segtree(2*idx+1, b, mid);
init_segtree(2*idx+2, mid+1, e);
segtree[idx] = (segtree[2*idx+1]&segtree[2*idx+2]);
}

LL query(LL idx, LL b, LL e, LL qb, LL qe)
{
if (b > qe || qb > e)
return -1LL;
if (b >= qb && e <= qe)
return segtree[idx];
int mid = (b+e)>>1;
LL ansL = query(2*idx+1, b, mid, qb, qe);
LL ansR = query(2*idx+2, mid+1, e, qb, qe);
return (ansL&ansR);
}

int main()
{
LL T;
scanf("%lld", &T);
for (int t = 0; t < T; t++)
{
LL N, K;
scanf("%lld %lld", &N, &K);
for (int i = 0; i < N; i++)
scanf("%lld", &array[i]);
if (2*K+1 >= N)
{
LL ans = array[0];
for (int i = 1; i < N; i++)
ans = (ans&array[i]);
for (int i = 0; i < N; i++)
printf("%lld ", ans);
printf("\n");
}
else
{
for (int i = 0; i < N; i++)
arr[i] = array[N-1-i];
for (int i = N; i < 2*N; i++)
arr[i] = array[i-N];
for (int i = 2*N; i < 3*N; i++)
arr[i] = array[i-2*N];
LL A = 3*N;
segtree = new LL[4*A];
init_segtree(0, 0, A-1);
for (int i = 0; i < N; i++)
printf("%lld ", query(0, 0, A-1, N+i-K, N+i+K));
printf("\n");
}
}
return 0;
}


•
• -2
•

 » 5 years ago, # |   +5 Why B = A' + A + A rather than B = A + A + A?
•  » » 5 years ago, # ^ |   0 Yes, my bad! you are right :)
 » 4 years ago, # |   0 even after making b=a+a+a, i am getting wrong answer. What could be the error
•  » » 8 months ago, # ^ |   0 If solving with segment tree just take care what value you return if that segment does not lie in the range :D
 » 4 years ago, # |   +13 Tl;dr but it has a very simple solution. Think about what would happen if you had just 1/0 in the array and what do 0s do.
 » 2 years ago, # |   0 Don't use long long, use only int. That will do.