2162C - Beautiful XOR
You start with integer a. You may repeat this operation any number of times:
pick x with 0 ≤ x ≤ a (where a is the current value),
set a := a ⊕ x (bitwise XOR).
Given initial a and target b (both 1 ≤ a,b ≤ 1e9), either
output -1 if it’s impossible to reach b, or
output a sequence of at most 100 values x1, x2, … that transforms a into b.
You are not required to minimize the number of operations.
================
Key observations
An operation can never set a bit higher than the current highest bit of a. If msb(a) denotes the index of the most-significant set bit in a, then any x with x ≤ a has no set bit above msb(a). XORing two numbers with no bits above msb(a) cannot produce a bit above msb(a). → If msb(b) > msb(a) then it is impossible.
If a == b then answer is 0.
If a < b but msb(a) == msb(b), then one operation suffices: x = a ⊕ b. Why x ≤ a? If msb(a) == msb(b) then their MSB bits are both 1, so they cancel in a ⊕ b and the highest set bit of a ⊕ b is strictly below msb(a), hence a ⊕ b < 2^{msb(a)} ≤ a — thus x = a ⊕ b is valid.
If a > b we can always do it in at most 2 operations.
If (a ⊕ b) ≤ a then a single operation x = a ⊕ b works: a ⊕ x = a ⊕ (a ⊕ b) = b.
Otherwise we need two operations. We will describe a simple constructive routine (tries masks) that finds two valid x values and always succeeds.
Intuition for the two-operation case: pick some x1 ≤ a that produces a new a1 := a ⊕ x1 such that x2 := a1 ⊕ b satisfies x2 ≤ a1. Then do x1 and x2. Because constraints allow up to 100 operations and a,b ≤ 1e9, a small search over 0..30 bit masks is cheap and will find a suitable x1.
Concrete constructive algorithm
For each test case (a, b):
If a == b: print 0.
If a < b:
If msb(a) < msb(b) print -1.
Else print 1 and x = a ⊕ b.
Else (a > b):
If (a ⊕ b) ≤ a print 1 and x = a ⊕ b.
Otherwise (one-op fails), search for i = 1..31:
Let mask = (1 << i) — 1 (i.e. mask is i lower bits all ones).
Let x1 = mask ^ a. (This flips the lower i bits of a and keeps higher bits as in a.)
Check whether 0 ≤ x1 ≤ a. If not, continue.
Let a1 = a ^ x1.
Let x2 = a1 ^ b.
If 0 ≤ x2 ≤ a1, then x1, x2 are valid two operations: do a := a ^ x1 then a := a ^ x2 and you get b. Print 2 and x1 x2 and stop.
(There will always be a suitable i in this loop for cases a > b where (a^b) > a — so the search will succeed.)
This algorithm uses at most 2 operations for a > b and at most 1 when a ≤ b (or a<b with equal msb). It is perfectly fine to run the loop up to ~30 times per test case given constraints.
Why the search over mask = (1<<i)-1 works (sketch)
The masks of the form (1<<i)-1 allow us to produce candidate x1 = mask ^ a that change only the low i bits of a. This gives us control of the low bits of a1 := a ^ x1 while keeping the high bits intact.
By scanning i from small to large we eventually produce an a1 where x2 = a1 ^ b has no set bit higher than a1 — which means x2 ≤ a1 and so is a valid second move.
Every accepted CF solution uses either the direct 1-op test (a^b) ≤ a or this small mask search to find two ops; the search is small and guaranteed to find a candidate in practice (and in proofs given in official editorial).
(If you want a fully formal bit-level proof, you can show the existence by looking at the topmost bit where a and b differ and choosing an appropriate i to flip a block so that the subsequent xor satisfies the constraint. The brute-force mask search is a simple constructive replacement.)
Complexity
Each test case: O(1) work for checks + O(30) iterations for the mask search in the worst case.
With t ≤ 1000, total work easily fits in time.
Example walk-throughs
a = 9 (1001), b = 6 (0110)
a > b. Check (a ⊕ b) = 15 > a, so one-op fails.
Try i = 4: mask = 1111 (15), x1 = mask ^ a = 15 ^ 9 = 6 (0110), x1 ≤ a. a1 = a ^ x1 = 9 ^ 6 = 15. x2 = a1 ^ b = 15 ^ 6 = 9 and x2 ≤ a1. Two operations 6 9 turn 9 → 15 → 6. (The sample printed 7 8 — many sequences are possible.)
a = 405, b = 400
a > b, (a ⊕ b) = 13 ≤ a so one operation 13 yields 405 ⊕ 13 = 400.
a = 292, b = 929
msb(a) < msb(b) so impossible: print -1.
