ashwin1907's blog

By ashwin1907, 4 years ago, In English,

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;
}
 
 
 
 
  • Vote: I like it  
  • -2
  • Vote: I do not like it  

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Why B = A' + A + A rather than B = A + A + A?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

even after making b=a+a+a, i am getting wrong answer. What could be the error

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If solving with segment tree just take care what value you return if that segment does not lie in the range :D

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Don't use long long, use only int. That will do.