How to the algorithms for Expogo work (Google Code Jam 2020 Round 1B)?

Question

Google Code Jam 2020, Round 1B is just over and I was pretty puzzled by the "Expogo" task:

You need to reach (X, Y) starting at (0, 0). You can move north / east / south / west. At time i your step length is 2**i (starting with i=0, increasing by one with every move).

Find the shortest sequence leading to (X, Y) or if it is impossible to get there.

Looking at a couple of solutions (e.g. Linguo, ctunoku, roflmoqkz, jaems, chaotic_iak), I see this kind of solution pretty often (taken from chaotic_iak, applied black):

def solve(x, y):
    if x % 2 == y % 2:
        return "IMPOSSIBLE"
    s = ""
    while x != 0 or y != 0:
        # Handling the easy cases:
        if abs(x) + abs(y) == 1:
            if x == 1:
                return s + "E"
            if x == -1:
                return s + "W"
            if y == 1:
                return s + "N"
            if y == -1:
                return s + "S"

        # This is what I don't get:
        if x % 2 == 1:
            y //= 2
            if (y % 2 == 1 and x % 4 == 1) or (y % 2 == 0 and x % 4 == 3):
                x = (x - 1) // 2
                s += "E"
            else:
                x = (x + 1) // 2
                s += "W"
        else:
            x //= 2
            if (x % 2 == 1 and y % 4 == 1) or (x % 2 == 0 and y % 4 == 3):
                y = (y - 1) // 2
                s += "N"
            else:
                y = (y + 1) // 2
                s += "S"

There seems to be a crucial insight in the problem which I don't get. First of all, why does same parity mean that it is impossible? I can see that (1, 1) is impossible, because you can easily get the first 1 and then you can only get 2. But how would one prove that it is impossible?

My main question: Why does the author divide by 2? The order of steps matters. The steps have length 2**i where i is the i-th step one takes (starting with 0). Why do they add +1?

What I understood

Let's just focus on X and assume it is positive. Then one path to go there is by getting the binary representation. For every position where it has a 1, one needs to go to E. In the other cases, one needs to do something else.

Instead of taking one E at step i, one can also take an E at i+1 and a W at i. This way, one can have infinitely many representations:

5 = 101
  = E0E : 4 + 1
  = EEW : 4 + 2 - 1
  = EW0E : 8 - 4 + 1
  = EWW0E : 16 - 8 - 4 + 1
  = EWWW0E : 32 - 16 - 8 - 4 + 1
  = ...

Answer 1

We can't get the same parity because only the first move is odd so either it is applied on the X or on the Y axis, never on both.

The division by two in this instance is just a convenient way to examine each bit from the least to most significant. Since we are obliged to use each bit either as a subtraction (south and west) or an addition (north and east), two problems can arise between the two coordinates, detected by the failure of both of these statements:

(x % 2 == 0 and y % 4 == 3)

(x % 2 == 1 and y % 4 == 1)

First, we could have an unset bit in the next position of both coordinates, which means x has a zero and y % 4 = 1, which means the next bit for y is also zero. In this case we add 1 to y, which is actually adding 2^p, where p is the current position of our pointer. This shifts the current set bit of the y coordinate left and creates a zero (a subtraction) at the current position.

Example: (4, 1)

x: 100
y:   1
    ^--- problem

solution: add 2^0 to y, creating a subtraction

110

south, north, east

A second problem is that x and y could both have a bit set in the next position. That's when x has a set bit and y % 4 == 3, meaning both the current and next bit of y are set. In this case, adding 2^p (the current bit) to y will flip both of these bits (and all adjacent to the left) in y, therefore using the first bit as a subtraction, and freeing up the second bit to be used by x.

Example: (6, 3)

x: 110
y:  11
    ^--- problem

solution: add 2^0 to y, creating a subtraction

x: 110
y: 100
   ^--- problem

solution: add 2^1 to x, creating a subtraction

x: 1000
y:  100

   south, west, north, east
x:       - 2            + 8  = 6
y: - 1           + 4         = 3

Based on the results of the code for some examples, I came up with this routine. It shows that the minimal binary number, N, that expresses x + y + s as powers of two where s equals NOT(N) (that is, the subtraction of s, or the "west" and "south" movements, can generate x + y), can be generated by adding x + y + (NOT(x + y) >> 1).

function f(x, y){
  let xy = x + y
  console.log((xy).toString(2))
  let p = 1
  let s = 0
  xy >>= 1
  while (xy){
    if (!(xy & 1))
      s |= p
    xy >>= 1
    p <<= 1
  }
  console.log(s.toString(2))
  console.log((x + y + s).toString(2))
  console.log('')
}

var cs = [
  [8, 9],
  [2, 3],
  [10, 5]
]

for (let [x,y] of cs)
  f(x,y)