GRAYSC - Editorial

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 ?

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

sorry for confusion I meant %llu in this case, now it should work fine :wink:

anyway, I’m still interested in counter example…

1 Like

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?

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

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

2 Likes

here is the counter example

5
9223372036854775808
9223372036854775809
9223372036854775810
9223372036854775812
9223372036854775816

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

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.

1 Like

@neil_812 :thanks

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!

1 Like

@javadecoder: is there something incorrect in my post?

wow it really hard :frowning:

oyun

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

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.

Solved in O(n^2) time complexity

//