Xum
Contest: Codeforces Global Round 11
Difficulty rating: 2500
Tags: bitmasks, constructive algorithms, math, matrices, number theory

You have a blackboard and initially only an odd number $$$x$$$ is written on it. Your goal is to write the number $$$1$$$ on the blackboard.

You may write new numbers on the blackboard with the following two operations.

- You may take two numbers (not necessarily distinct) already on the blackboard and write their sum on the blackboard. The two numbers you have chosen remain on the blackboard.
- You may take two numbers (not necessarily distinct) already on the blackboard and write their bitwise XOR on the blackboard. The two numbers you have chosen remain on the blackboard.

Input format:
The single line of the input contains the odd integer $$$x$$$ ($$$3 \le x \le 999,999$$$).

Output format:
Print on the first line the number $$$q$$$ of operations you perform. Then $$$q$$$ lines should follow, each describing one operation.

- The "sum" operation is described by the line "$$$a$$$ + $$$b$$$", where $$$a, b$$$ must be integers already present on the blackboard.
- The "xor" operation is described by the line "$$$a$$$ ^ $$$b$$$", where $$$a, b$$$ must be integers already present on the blackboard.

You can perform at most $$$100,000$$$ operations (that is, $$$q\le 100,000$$$) and all numbers written on the blackboard must be in the range $$$[0, 5\cdot10^{18}]$$$. It can be proven that under such restrictions the required sequence of operations exists. You can output any suitable sequence of operations.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3

Example output:
5
3 + 3
3 ^ 6
3 + 5
3 + 6
8 ^ 9

Example input:
123

Example output:
10
123 + 123
123 ^ 246
141 + 123
246 + 123
264 ^ 369
121 + 246
367 ^ 369
30 + 30
60 + 60
120 ^ 121

Editorial:
We present two different solutions. The first solution is by Anton, the second is mine.
• The first solution is deterministic, it is fundamentally based on Bezout's Theorem and comes with a proof. It performs $$$\approx 100$$$ operations and writes numbers up to $$$O(x^3)$$$.
• The second solution is randomized, uses some xor-linear-algebra and comes without a proof. It performs $$$\approx 1000$$$ operations and writes numbers up to $$$O(x^2)$$$.
Deterministic, provable, "gcd" solution
Step 0: If $$$u$$$ is written on the blackboard, then we can write $$$nu$$$ on the blackboard with $$$O(\log(n))$$$ operations.
How? Just using the sum operation as in the binary exponentiation (same algorithm, just replace multiplication with addition and exponentiation with multiplication).
Step 1: Write on the blackboard a number $$$y$$$ coprime with $$$x$$$.
Let $$$e\in\mathbb N$$$ be the largest integer such that $$$2^e\le x$$$ (i.e., $$$2^e$$$ is the largest bit of $$$x$$$). Notice that $$$y=(2^ex)\wedge x = (2^e+1)x - 2^{e+1}$$$ and therefore $$$gcd(x,y)=gcd(x,2^{e+1})=1$$$.
Step 2: Write $$$1=gcd(x,y)$$$ on the blackboard.
Let $$$a, b\ge 0$$$ be such that $$$ax-by=1$$$ ($$$a,b$$$ exist thanks to Bezout's theorem) with $$$b$$$ even (if $$$b$$$ is odd, we can add $$$y$$$ to $$$a$$$ and $$$x$$$ to $$$b$$$, getting an even $$$b$$$). Since $$$by$$$ is even, we have $$$ax\wedge by = 1$$$ and therefore we are able to write $$$1$$$ on the blackboard.
Randomized, unproven, linear-algebraic solution
We are going to talk about subspaces and basis; they shall be understood with respect to the operation xor on nonnegative integers.
The rough idea is to sample randomly two numbers from the subspace generated by the numbers currently on the blackboard and write their sum on the blackboard.
First, we choose the maximum number of bits $$$L$$$ that any number on the blackboard will ever have. A good choice is $$$2^L > x^2$$$ ($$$L=40$$$ works for any odd $$$x$$$ below $$$10^6$$$).
We iterate the following process until $$$1$$$ belongs to the subspace generated by the numbers written on the blackboard.
Let $$$S$$$ be the subspace generated by the numbers currently on the blackboard (i.e., the set of numbers that can be written as the xor of some numbers on the blackboard). Let $$$b_1,\dots, b_k$$$ be a basis for $$$S$$$. Randomly choosing $$$k$$$ bits $$$e_1,\dots,e_k$$$ we can produce a random element in $$$S$$$ as $$$$$$(e_1b_1)\wedge(e_2b_2)\wedge\cdots \wedge(e_kb_k) \,.$$$$$$ Let us choose two random numbers $$$u, v\in S$$$.
• If $$$u+v \ge 2^L$$$, we choose a different pair of numbers.
• If $$$u+v\in S$$$ (we can check this in $$$O(k)$$$ since we know a basis for $$$S$$$), we choose a different pair of numbers.
• Otherwise, we add $$$u+v$$$ to $$$S$$$ and update the basis accordingly.
It turns out that this approach solves all odd values $$$3\le x\le 999,999$$$ instantaneously.
Could we choose a much smaller $$$L$$$? The answer is no. If $$$x=2^{19}+1$$$ then there is a xor-subspace $$$S$$$ that contains $$$x$$$ and such that if $$$u,v\in S$$$ and $$$u+v<2^{38}$$$ then $$$u+v\in S$$$. Notice that this implies that any strategy needs to write on the blackboard some "some big numbers". This is why any approach that avoids large numbers by design is doomed to fail.
Comment: Why should this solution work? Fundamentally, and this is the main idea of the problem, because the two operations $$$+$$$ and $$$\wedge$$$ are not related by any strange hidden structure. It would be a miracle if we could find a very big subspace for $$$\wedge$$$ that is closed also for $$$+$$$. And, since miracles are rare, here there is no miracle.
It should not be very hard to show that this solution works for any odd $$$x$$$, i.e. there is not a subspace that contains $$$x$$$ and is closed for sums that are below $$$2^L$$$ (if $$$2^L>x^2$$$). Nonetheless, I could not show it. On the other hand, I think that proving that this solution has a very good (expected) time-complexity is very hard, but I would be happy if someone proves me wrong.