# GRAYSC - Editorial **URL:** \ **Category:** editorial\ **Tags:** editorial, july12, medium, pigeonhole, search\ **Created:** [July 11, 2012, 3:43pm UTC](https://discuss.codechef.com/t/graysc-editorial/388 "2012-07-11T15:43:39Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![yellow\_agony](https://discuss.codechef.com/user_avatar/discuss.codechef.com/yellow_agony/32/24644_2.png) [@yellow\_agony](https://discuss.codechef.com/u/yellow_agony)\ **Post date:** [July 11, 2012, 3:43pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/1 "2012-07-11T15:43:39Z")
## PROBLEM LINK: [Practice](http://www.codechef.com/problems/GRAYSC) [Contest](http://www.codechef.com/JULY12/problems/GRAYSC) ## 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[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](http://www.codechef.com/download/Solutions/2012/July/Setter/GRAYSC.cpp). ## TESTER’S SOLUTION: Can be found [here](http://www.codechef.com/download/Solutions/2012/July/Tester/GRAYSC.cpp). ## RELATED PROBLEMS: [UVA 11898](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2998) ---
**Author:** ![betlista](https://discuss.codechef.com/user_avatar/discuss.codechef.com/betlista/32/203_2.png) [@betlista](https://discuss.codechef.com/u/betlista)\ **Post date:** [July 11, 2012, 4:14pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/2 "2012-07-11T16:14:39Z")
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 (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) ---
**Author:** ![rohanag](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@rohanag](https://discuss.codechef.com/u/rohanag)\ **Post date:** [July 11, 2012, 5:55pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/3 "2012-07-11T17:55:19Z")
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. ---
**Author:** ![saurabhmodi102000](https://discuss.codechef.com/user_avatar/discuss.codechef.com/saurabhmodi102000/32/64_2.png) [@saurabhmodi102000](https://discuss.codechef.com/u/saurabhmodi102000)\ **Post date:** [July 11, 2012, 6:01pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/4 "2012-07-11T18:01:23Z")
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. ---
**Author:** ![kavishrox](https://discuss.codechef.com/user_avatar/discuss.codechef.com/kavishrox/32/368_2.png) [@kavishrox](https://discuss.codechef.com/u/kavishrox)\ **Post date:** [July 11, 2012, 6:42pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/5 "2012-07-11T18:42:31Z")
Please anyone tell me for which cases my code for this problem gives WA ``` #include 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;i1) 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. ---
**Author:** ![dr0b3rts](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@dr0b3rts](https://discuss.codechef.com/u/dr0b3rts)\ **Post date:** [July 11, 2012, 9:51pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/6 "2012-07-11T21:51:35Z")
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 ``` ---
**Author:** ![javadecoder](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@javadecoder](https://discuss.codechef.com/u/javadecoder)\ **Post date:** [July 11, 2012, 10:12pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/7 "2012-07-11T22:12:41Z")
Simple Brute Force : [http://www.codechef.com/viewsolution/1176364](http://www.codechef.com/viewsolution/1176364) ---
**Author:** ![neil\_812](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@neil\_812](https://discuss.codechef.com/u/neil_812)\ **Post date:** [July 11, 2012, 11:21pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/8 "2012-07-11T23:21:59Z")
I am dying to know why this solution gets WA [CodeChef: Practical coding for everyone](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 [CodeChef: Practical coding for everyone](http://www.codechef.com/viewsolution/1152313). So could anyone please tell me what the problem is? ---
**Author:** ![red\_coder](https://discuss.codechef.com/user_avatar/discuss.codechef.com/red_coder/32/415_2.png) [@red\_coder](https://discuss.codechef.com/u/red_coder)\ **Post date:** [July 12, 2012, 10:43am UTC](https://discuss.codechef.com/t/graysc-editorial/388/9 "2012-07-12T10:43:10Z")
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 🙂 ---
**Author:** ![shashank\_jain](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shashank_jain/32/163_2.png) [@shashank\_jain](https://discuss.codechef.com/u/shashank_jain)\ **Post date:** [July 13, 2012, 12:29am UTC](https://discuss.codechef.com/t/graysc-editorial/388/10 "2012-07-13T00:29:34Z")
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 ? ---
**Author:** ![bala31](https://discuss.codechef.com/user_avatar/discuss.codechef.com/bala31/32/573_2.png) [@bala31](https://discuss.codechef.com/u/bala31)\ **Post date:** [July 15, 2012, 6:00pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/11 "2012-07-15T18:00:50Z")
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. ---
**Author:** ![bodmas](https://discuss.codechef.com/user_avatar/discuss.codechef.com/bodmas/32/11310_2.png) [@bodmas](https://discuss.codechef.com/u/bodmas)\ **Post date:** [July 17, 2012, 4:52am UTC](https://discuss.codechef.com/t/graysc-editorial/388/12 "2012-07-17T04:52:18Z")
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! ---
**Author:** ![oyun](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@oyun](https://discuss.codechef.com/u/oyun)\ **Post date:** [July 17, 2012, 7:59pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/13 "2012-07-17T19:59:35Z")
wow it really hard ☹ [oyun](http://oyun.mynet.com/) ---
**Author:** ![sayaksan](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sayaksan](https://discuss.codechef.com/u/sayaksan)\ **Post date:** [June 18, 2014, 1:16am UTC](https://discuss.codechef.com/t/graysc-editorial/388/15 "2014-06-18T01:16:55Z")
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. ---
**Author:** ![krodhking](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@krodhking](https://discuss.codechef.com/u/krodhking)\ **Post date:** [May 27, 2015, 7:14pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/16 "2015-05-27T19:14:24Z")
Solved in O(n^2) time complexity > **[CodeChef: Practical coding for everyone](https://www.codechef.com/status/GRAYSC?usernames=krodhking)** > > Learn to code for free using our beginner friendly and interactive learning courses. Get all the practical skills required to excel at computer science. Start learning with CodeChef today and unlock your potential as a developer! ---
**Author:** ![sid\_gup](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sid\_gup](https://discuss.codechef.com/u/sid_gup)\ **Post date:** [July 11, 2012, 5:15pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/17 "2012-07-11T17:15:17Z")
I had the same algorithm initially, but i believe test data was not correct at that time. Then i switched to pigeonhole. ---
**Author:** ![betlista](https://discuss.codechef.com/user_avatar/discuss.codechef.com/betlista/32/203_2.png) [@betlista](https://discuss.codechef.com/u/betlista)\ **Post date:** [July 11, 2012, 5:25pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/18 "2012-07-11T17:25:37Z")
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… ---
**Author:** ![sid\_gup](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sid\_gup](https://discuss.codechef.com/u/sid_gup)\ **Post date:** [July 11, 2012, 5:33pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/19 "2012-07-11T17:33:11Z")
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 😉 ---
**Author:** ![kavishrox](https://discuss.codechef.com/user_avatar/discuss.codechef.com/kavishrox/32/368_2.png) [@kavishrox](https://discuss.codechef.com/u/kavishrox)\ **Post date:** [July 11, 2012, 6:46pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/20 "2012-07-11T18:46:21Z")
oops sorry something gone wierd please refer to the solution at [CodeChef: Practical coding for everyone](http://www.codechef.com/viewsolution/1170413) and tell me for what cases it goes wrong… ---
**Author:** ![betlista](https://discuss.codechef.com/user_avatar/discuss.codechef.com/betlista/32/203_2.png) [@betlista](https://discuss.codechef.com/u/betlista)\ **Post date:** [July 11, 2012, 6:50pm UTC](https://discuss.codechef.com/t/graysc-editorial/388/21 "2012-07-11T18:50:20Z")
it returns no for ``` 6 2 3 2 6 14 6 ``` [Next page](https://discuss.codechef.com/t/graysc-editorial/388.md?page=2)