SEQUENCE - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

Such “gradual” sequences are similar to the well-known Gray codes. Here is one way (of many) to generate the Gray code x[0], x1, …, x[2^n-1] starting with x[0] = 0. To get the value of x*, if i is odd then x* is simply x[i-1] with the least significant bit flipped. Otherwise, let j be such that the j’th bit of x[i-1] is 1 and all bits of x[i-1] that are less significant than the j’th bit are 0. Then x* is obtained from x[i-1] by flipping the bit at position j+1. This can be done with clever bitwise operations.

Now, if a and b differ in more than one bit then we may simply output the Gray code. Otherwise, if a and b differ in only one bit then there is no solution for n = 1 or n = 2. Finally, I claim that there is always a solution for n >= 3 if a and b differ in precisely one bit.

We begin by finding a gradual sequence where 0 is not consecutive to a XOR b (XOR means bitwise XOR of binary numbers). To do this, start with the Gray code as mentioned above (or any other gradual sequence you can generate). If 0 and a XOR b are not consecutive, then we are done. Otherwise, since n >= 3 there is some bit 0 <= k < n such that 2^k is not consecutive to 0 in the gradual sequence. Now, let c* be the bit that changes between x* and x[i+1] and note that the x* can be recovered from the sequence of c* if we assume x[0] = 0. Let 2^j = a XOR b. Modify the sequence c* by changing c* = k values to c* = j and c* = j values to c* = k. This will generate a new gradual sequence y* that starts with y* = 0. However, by construction we will not have 0 and a XOR b adjacent in y*. Finally, the gradual sequence of values y* XOR a will not have a and b consecutive.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.