GRAYSC - Editorial

yellow_agony · July 11, 2012, 3:43pm

PROBLEM LINK:

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Pigeonhole Principle, Sets

PROBLEM:

You’re given N 64 bit integers such that any two successive numbers differ at exactly 1 bit. Your job is to find out if there are 4 integers such that their xor is equal to 0.

QUICK EXPLANATION:

Whenever N >= 130, it is always possible to find 4 integers of the given list such that their xor is 0. For smaller N, one could do an exhaustive search in O(N^3 log N).

DETAILED EXPLANATION:

Solution of this problem is simpler than many of you might’ve imagined. For all
N >= 130, answer is always YES. Let’s see why : Assume there are >= 130
numbers in input array A.

Let x_i = A[2i] xor A[2i+1] for i in [0, N/2)
As any two successive values of A differ at exactly one bit, binary
representation of each x_i has exactly 1 bit as 1 and all other bits are
0. Also as N >= 130, we’ve at least 65 values of x_i. Note all of them can
be distinct as each x_i has only 1 bit set and all x_i are at maximum 64 bits
long. So say x_j = x_k for some j and k

Then x_j xor x_k = 0
=> A(2j) xor A(2j+1) xor A(2k) xor A(2k+1) = 0
And so the answer is YES.

Small Case:
What if N < 130? We could do an exhaustive search. One could try moving all
4 numbers and see if their xor is 0 or not. This takes O(N^4) time and is probably
too costly. We can do this in O(N^3 log N) as well. Let’s see how.

Say if there are four indices i1, i2, i3, i4 such that
A[i1] xor A[i2] xor A[i3] xor A[i4] = 0.
Then A[i1] xor A[i2] xor A[i3] = A[i4]

So we could move over all three numbers of array, find their xor and
check if it is present in set as well or not.

for i in 1 to N
  for j in i+1 to N
    for k in j+1 to N
      x = A[i] ^ A[j] ^ A[k]
      if A[k+1...N] contains x, return true

return false

Note : Actually 130 is only an upper bound. We don’t have a case for N > 67 for
which answer is No. Maybe such a case doesn’t exist and our proof given above could
be strengthened. If you have a case where N > 67 and answer is NO, please share it here.

SETTER’S SOLUTION:

Can be found here.

TESTER’S SOLUTION:

Can be found here.

RELATED PROBLEMS:

UVA 11898

betlista · July 11, 2012, 4:14pm

I solved this in O(N):

for each i in 0…N-1 I found B[i] = A[i] xor A[i+1] - there are only 64 possible values (2⁰, 2¹, 2², …, 2⁶³), the question is if there are two same values in B.

There are three corner cases in this approach:

sequence A = { 3, 2, 3, 7 } => B = { 1, 1, 4 }, but these two 1s are not two pairs - four numbers (we are looking same numbers but not adjacent)
sequence A can contain 2 pairs of same numbers without having same acceptable (not adjacent) elements in B, for example A = { 2, 3, 2, 6, 14, 6 } => B = { 1, 1, 4, 8, 8 }
sequence A can contain 4 same numbers without having same acceptable (not adjacent) elements in B, for example A = { 2, 3, 2, 6, 2, 10, 2 } => B = { 1, 1, 4, 4, 8, 8 } (all same are adjacent)

sid_gup · July 11, 2012, 5:15pm

I had the same algorithm initially, but i believe test data was not correct at that time. Then i switched to pigeonhole.

betlista · July 11, 2012, 5:25pm

I think that you can always test input with assert statement in C/C++ and if your check fail you will get SIGABRT instead of WA, so you can write your feedback…

sid_gup · July 11, 2012, 5:33pm

Yeah i know. But somehow at that time, i wasn’t convinced with this algorithm and pigeonhole was another idea in my mind. So i stopped thinking too much about it

rohanag · July 11, 2012, 5:55pm

I don’t know about the formal proof for N > 67, but for N = 67, we can have ‘NO’ cases because pairs of adjacent elements can have the same XOR value, but those adjacent elements cannot form the answer, as they have an element in common.

For eg take 3 numbers: a,b,c : such that a xor b = b xor c , but our answer cannot be yes here, because b is taken twice.

I hope the following example can save my shoddy explanation.

A concrete example, for 5 digit binary numbers (numbers upto 2^5 - 1). As betlista mentioned, we can only have 5 possible Xor values: 1,2,3,4,5. If the xor values for adjacent pairs repeat, we have the answer YES, except for cases, where neighboring xor values are equal.

Here is a case where there are 2 pairs of equal xor values ( 8 elements in total ), but the answer is still NO.

10001 , 10000, 10001, 10011, 10001, 10101, 11101, 01101

10001 xor 10000 = 1,
10000 xor 10001 = 1,
10001 xor 10011 = 2,
10011 xor 10001 = 2,
10001 xor 10101 = 3,
10101 xor 11101 = 4,
11101 xor 01101 = 5

So for 5 digits, we have a sequence of 8 numbers for which the answer is NO. Similarly for 64 bit binary numbers , we can make a case upto N == 67, where the answer is NO, but we can’t go higher than 67.

In the example , I could put in only 2 pairs of XOR values that were repeated, i.e 1 and 2. Whenever I tried to make a case with 3 pairs, the answer would automatically be YES, because in making the third pair, I would have to put in a number in the sequence, which had already come before.

saurabhmodi102000 · July 11, 2012, 6:01pm

There is a proof for N >= 69 that answer shall always be yes. Also,the limit on N can probably be reduced further.

See,
consider N = 69.Now,there are 68 possible pairs for N = 69.

Obviously,by pigeonhole principle,there has to be 2 pairs definitely,the xor of whose elements is same.

Now ,consider such two pairs.One of the two things could happen.

1)The pairs could be overlapping,i.e,they have a common element,for instance 1,3,1.Here,(1,3) and (3,1) are two possible pairs.
2)There could be two disjoint pairs that have same xor values in which case we need not go further and have the answer with us.

Now ,if we encounter case 1),
we can first remove these 3 numbers,and now we are left with 66 numbers.Now,we have 65 pairs.Again ,the situation similar to above shall happen,i.e. one of the two situations shall occur.

Now if the situation 2 occurs,we need not go further,but if situation 1 happens,then that means that we have another triplet.
The first triplet was of the form, - a,b,a and the 2nd triplet was of the form - c,d,c.
the xor of a,a,c,c is 0.Therefore,we always have answer " yes" for number >= 69.

kavishrox · July 11, 2012, 6:42pm

Please anyone tell me for which cases my code for this problem gives WA

#include<stdio.h>
int ndig(long long int a)
{
	int cnt=1;
	while(a>>1)
	{
		a=a>>1;
		cnt++;
	}
	return cnt;
}
int main()
{
	short int f=1;
	int i,n,b[65],l=0;
 	long long int a[100000],now,previous;
	for(i=0;i<65;i++)
	b[i]=0;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%lld",&a[i]);
		if(i&&f)
		{
			now=a[i]^a[i-1];
			if(now==previous&&i!=1)
			l++;
			else
			l=0;
			if(i==1||(l%2==0))
			{
				b[ndig(now)]++;
				if(b[ndig(now)]>1)
				f=0;
			}
			previous=now;
		}
	}
	if(f)
	printf("No\n");
	else
	printf("Yes\n");
	return 0;
}

I considered xor of every adjacent element and increased the count of the b[65] array corresponding to the bit which was set but eeping in mind that there are not 2 such consequtive cases such that a^b==b^c for that previous,now and l variable are used…as soon as we get an array with count>1 it means that we have found out 2 such pairs such that a^b==c^d and all are distinct too…basically i concentrated on the unique set bit on xoring two gray like numbers and found out if there is a count increase of not…for the pigeonhole proof it comes from here that suppose we have a series such that a^b==b^c such that every 3 consequtive numbers share a singe xor answer thus a^b and b^c give a particular set bit,c^d and d^e give another particular set bit position and so on if it goes like this then all the 64 bits would be covered in at max to max 2n+1 cases where n are the total bits in a number which for here gives 129 according to my calculations for which the admin is probably right in giving limit<=130.

kavishrox · July 11, 2012, 6:46pm

oops sorry something gone wierd please refer to the solution at http://www.codechef.com/viewsolution/1170413 and tell me for what cases it goes wrong…

betlista · July 11, 2012, 6:50pm

it returns no for

6
2 3 2 6 14 6

dr0b3rts · July 11, 2012, 9:51pm

I had O(n^2 log n) solution and got accepted! Pigeonhole must have reduced actual runtime!

My solution checks for: a[i1] xor a[i2] == a[i3] xor a[i4], by keeping each pairwise xor in a multimap to ensure unique indexes.

for i
  for j
    let b = a[i] xor a[j]
    find all values in multimap with key b
`     if value.first not equal to i or j and value.second not equal to i or j
        then print Yes and exit
    add (key = b, value = (i,j)) to multimap
print No

javadecoder · July 11, 2012, 10:12pm

Simple Brute Force : http://www.codechef.com/viewsolution/1176364

betlista · July 11, 2012, 11:05pm

such a luck :-/

@author + tester: is there test case where correct tuple are numbers with indexes 64, 65, 66, 67 ? It should get TLE…

neil_812 · July 11, 2012, 11:21pm

I am dying to know why this solution gets WA http://www.codechef.com/viewsolution/1176713.
For every two adjacent numbers I find which bit changes and count how many times each bit changes. Then if any bit changes twice but not consecutively the answer is yes. I spent hours trying to debug this and trying every case I could possibly think of. It also handles all the cases mentionned above, but still gets WA. Eventually I recoded the exact same algorithm in Python and got AC http://www.codechef.com/viewsolution/1152313. So could anyone please tell me what the problem is?

yugant123 · July 12, 2012, 12:25am

try this… 2 0 2 3 2 6 2… it has “2 xor 2 xor 2 xor 2 = 0”… Is ur algo right for this?

neil_812 · July 12, 2012, 12:57am

yeah it works. output is “yes”.

red_coder · July 12, 2012, 10:43am

According to me the upper bound should be 130 only. For this suppose A[0] and A[1] differ in 1st least significant bit so their xor would be only 1, A[1] and A[2] also differ in 1st bit so their xor would also be 1. Similarly A[2] and A[3] xor is 10 and A[3] and A[4] xor is also 10. So for each bit set we can have three adjacent numbers and two pairs (first-second and second-third). Thus for 64 bits we can have 64*2+1= 129. thus if N>=130, we would always have YES otherwise we can have NO

betlista · July 12, 2012, 2:01pm

This is just a tip, but you should use %lld instead of %I64d, maybe this is the problem (it’s written in help).

betlista · July 12, 2012, 2:08pm

I think that @saurabhmodi102000’s description is clear about this…

If not, try to find sequence where xors are A, A, B, B, C, C, such sequence is A = { 2, 3, 2, 6, 2, 10, 2 }, but if you choose 4 times 2 the result is 0.

neil_812 · July 12, 2012, 11:07pm

Thanks for the tip, but it still gets WA.