You are not logged in. Please login at www.codechef.com to post your questions!

×

GRAYSC - Editorial

8
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[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

This question is marked "community wiki".

asked 11 Jul '12, 15:43

yellow_agony's gravatar image

4★yellow_agony ♦♦
1243837
accept rate: 0%

edited 11 Jul '12, 15:55


13

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)
link

answered 11 Jul '12, 16:14

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

edited 13 Jul '12, 17:42

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

(11 Jul '12, 17:15) sid_gup4★
1

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

(11 Jul '12, 17:25) betlista ♦♦3★

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 ;)

(11 Jul '12, 17:33) sid_gup4★

@javadecoder: is there something incorrect in my post?

(17 Jul '12, 19:23) betlista ♦♦3★
10

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.

link

answered 11 Jul '12, 18:01

saurabhmodi102000's gravatar image

2★saurabhmodi102000
143114
accept rate: 0%

edited 12 Jul '12, 10:26

yellow_agony's gravatar image

4★yellow_agony ♦♦
1243837

link

answered 11 Jul '12, 22:12

javadecoder's gravatar image

4★javadecoder
6271713
accept rate: 27%

such a luck :-/

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

(11 Jul '12, 23:05) betlista ♦♦3★

I have a problem.. The problem gets Accepted everytime I submit your solution.. However if I write my own Brute Force code and submit it it gives TLE.. Any clues why?

(13 Jul '12, 16:08) elmagnifico4★

you are using long long instead of unsigned long long, when I removed unsigned I got TLE, but I have no idea why...

(13 Jul '12, 17:08) betlista ♦♦3★
2

Note : n < 2^64, so using signed long long changes the numbers(due to overflow), and this violates the property mentioned in the problem.(maybe due to which program is unable to find a solution and run in O(n^4))

(13 Jul '12, 17:56) javadecoder4★

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.

link

answered 11 Jul '12, 17:55

rohanag's gravatar image

3★rohanag
313
accept rate: 0%

edited 11 Jul '12, 18:02

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.

link

answered 15 Jul '12, 18:00

bala31's gravatar image

2★bala31
163
accept rate: 0%

edited 15 Jul '12, 18:02

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!

link

answered 17 Jul '12, 04:52

bodmas's gravatar image

5★bodmas
16127
accept rate: 0%

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.

link

answered 11 Jul '12, 18:42

kavishrox's gravatar image

3★kavishrox
285101719
accept rate: 5%

edited 11 Jul '12, 18:51

betlista's gravatar image

3★betlista ♦♦
16.9k49115225

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

(11 Jul '12, 18:46) kavishrox3★
1

it returns no for

6
2 3 2 6 14 6
(11 Jul '12, 18:50) betlista ♦♦3★

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
link

answered 11 Jul '12, 21:51

dr0b3rts's gravatar image

4★dr0b3rts
915
accept rate: 0%

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?

link

answered 11 Jul '12, 23:21

neil_812's gravatar image

5★neil_812
6114
accept rate: 0%

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?

(12 Jul '12, 00:25) yugant1232★

yeah it works. output is "yes".

(12 Jul '12, 00:57) neil_8125★

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

(12 Jul '12, 14:01) betlista ♦♦3★

Thanks for the tip, but it still gets WA.

(12 Jul '12, 23:07) neil_8125★
1

sorry for confusion I meant %llu in this case, now it should work fine ;-)

anyway, I'm still interested in counter example...

(13 Jul '12, 13:56) betlista ♦♦3★

here is the counter example

5
9223372036854775808
9223372036854775809
9223372036854775810
9223372036854775812
9223372036854775816
(13 Jul '12, 18:25) betlista ♦♦3★

Wow it got accepted now! I didn't know there was a different specifier for unsigned long long. Thanks!

(13 Jul '12, 19:30) neil_8125★
showing 5 of 7 show all

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

link

answered 12 Jul '12, 10:43

red_coder's gravatar image

3★red_coder
303
accept rate: 0%

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.

(12 Jul '12, 14:08) betlista ♦♦3★

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 ?

link

answered 13 Jul '12, 00:29

shashank_jain's gravatar image

2★shashank_jain
6192813
accept rate: 10%

That is the logic behind the O(n) solution, but there are corner cases to consider. See the first post.

(13 Jul '12, 08:07) neil_8125★

@neil_812 :thanks

(15 Jul '12, 18:03) shashank_jain2★

wow it really hard :(

oyun

link

answered 17 Jul '12, 19:59

oyun's gravatar image

0★oyun
1
accept rate: 0%

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

link

answered 30 Aug '12, 11:08

jobsalertro's gravatar image

0★jobsalertro
1
accept rate: 0%

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.

link

answered 18 Jun '14, 01:16

sayaksan's gravatar image

4★sayaksan
2614
accept rate: 0%

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

link

answered 27 May '15, 19:14

krodhking's gravatar image

5★krodhking
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×2,657
×68
×30
×13

question asked: 11 Jul '12, 15:43

question was seen: 7,943 times

last updated: 27 May '15, 19:14