GRAYSC - Editorial

editorial
july12
medium
pigeonhole
search

#1

PROBLEM LINK:

Practice
Contest

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 xi = 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 xi has exactly 1 bit as 1 and all other bits are
0. Also as N >= 130, we’ve at least 65 values of xi. Note all of them can
be distinct as each xi has only 1 bit set and all xi are at maximum 64 bits
long. So say xj = xk for some j and k

Then xj xor xk = 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* ^ 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][3].

TESTER'S SOLUTION:

Can be found [here][4].

RELATED PROBLEMS:

[UVA 11898][5]

#2

I solved this in O(N):

for each i in 0…N-1 I found B* = A* xor A[i+1] - there are only 64 possible values (20, 21, 22, …, 263), the question is if there are two same values in B.

There are three corner cases in this approach:

  1. 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)
  2. 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 }
  3. 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)

#3

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.


#4

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.


#5

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*=0;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%lld",&a*);
		if(i&&f)
		{
			now=a*^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

");
else
printf("Yes
");
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.


#6

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* 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

#7

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


#8

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?


#9

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 :slight_smile:


#10

Can anyone tell me why this logic fails ?

.Since two adjacent numbers differ by a single binary bit, the result of XOR’ing two adjacent numbers together is very predictable

x represents a bit whose value doesn’t matter, but is the same as the corresponding x below/above it.

xor:

xxxxxxxxxxxxx1xxxxxxxxxxxx

xxxxxxxxxxxxx0xxxxxxxxxxxx


00000000000001000000000000

This is true for ANY two adjacent numbers in the array
so now if i can find another pair of adjacent numbers, that differ by the same bit, they will ALSO XOR-out to the same value: 00000000000001000000000000

that will form the quadruple that gives zero isn’t it ?


#11

the result will be 0 for n>=67… Proof:

there 64 bits possible @max. let i1,i2,i3,… be the eles. Take the first pair (i1&i2) and XOR them. The result will look like this 0000000001000000000000000000000000000000000… 64 bits

Xor i3&i4,i4&i5,…,i66&i67 Any of these results will surely have the result mentioned above by pigeonhole principle.


#12

I cldn’t compete this month due to exams:( but kudos to the setter of this problem. I love its analysis, especially the proposed O(n) solution. big ups!


#13

wow it really hard :frowning:

oyun


#14

Is it too late to post an answer on this problem? There is a time limit or we can discuss it at length on community? This is my first time here.

Danel Sorescu
Web Developer
locuri de munca in strainatate


#15

A non-negative integer with 64 bits can differ to at most 63 nos by 1 bit (i.e. have exactly one different digit in their binary representation.). Now, suppose, N<68. Suppose, N is 67. Now, in the sequence repetition of one element is allowed i.e. if an element a exists in the input number sequence, then it can be repeated and it can be repeated upto 3 times (allowed without making the XOR of 4 nos zero). Because, if the no. is repeated >=4 times then clearly it’s over. (a,a,a (a is an element of the sequence which is repeated) and a will be chosen for XOR operation and result will be zero) Now, why repetition of only one element is allowed? Because, if two elements (say a and c) are repeated in the sequence (twice or more than twice does not matter) there will be always four elements in the sequence for which xor operation will result zero. (a,a,c,c) . Now, if N is 67 (or less than 67) then we can choose only one a among two or three a’s to try for a solution of this problem (if we choose two a or three a in the solution then solution will never be achieved. Think about it. If we choose a,a,b,c (where a,b and c are distinct elements) for a solution then a^a (^:- bitwise XOR) is zero. And the resulting solution (xor of 4 elements) will never be zero unless b=c. But it is a contradiction. since repetition of only one element is allowed) So, now it’s clear, why we can only choose one a from the repetitions for achieving the desired solution. Now deduce 3 from 67, result is 64 and these 64 elements are distinct. So, 64 distinct elements and one a, from which we can create only 64 pairs. (and remember, 64 distinct pairs are possible between adjacent elements ). Now, why we are only allowing the pairs of adjacent elements (like, in the example test cases such pairs are (1,0), (0,2), (2,3) and (3,7)) because, their resulting xor pair has only one bit turned on. (only one bit is set) that is why for N<=67 the result can be “NO”. but for N>=68, we can have 66 distinct elements and 65 such pairs. among these 65 pairs, two pairs have to be same (according to the pigeonhole principle). That’s why, for N>=68 result will always be yes.


#16

Solved in O(n^2) time complexity
http://www.codechef.com/status/GRAYSC,krodhking


#17

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


#18

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…


#19

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 :wink:


#20

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…