The original blog was accidentally deleted by one of the other authors. You can find an archive of the original editorial here: https://web.archive.org/web/20220705073720/https://mirror.codeforces.com/blog/entry/104088.

A — The Third Three Number Problem

Authors: antontrygubO_o, Gheal

Hints

Hint 1

An answer exists only when $$$n$$$ is even.

Hint 2

$$$a \oplus a = 0$$$

$$$a \oplus 0 = a$$$

Solution

First and foremost, it can be proven that $$$(a \oplus b) + (b \oplus c) + (a \oplus c)$$$ is always even, for all possible non-negative values of $$$a$$$, $$$b$$$ and $$$c$$$.

Proof

Firstly, $$$a \oplus b$$$ and $$$a+b$$$ have the same parity, since $$$a + b = a \oplus b + 2 \cdot (a \text{&} b) $$$. Therefore, $$$(a \oplus b) + (b \oplus c) + (a \oplus c)$$$ has the same parity as $$$(a+b)+(b+c)+(a+c)=2 \cdot (a+b+c)$$$.

Therefore, if $$$n$$$ is even, one possible solution is $$$a=0$$$, $$$b=0$$$ and $$$c=\frac{n}{2}$$$. In this case, $$$(a \oplus b) + (b \oplus c) + (a \oplus c)= 0+\frac{n}{2}+\frac{n}{2}=n$$$. Otherwise, there are no solutions.

Time complexity per testcase: $$$O(1)$$$.

Post Scriptum

This is actually the third iteration of the problem, which was suggested by antontrygubO_o .

The first iteration had $$$|a-b|+|b-c|+|a-c|=n$$$, and the second one had $$$gcd(a,b)+gcd(b,c)+gcd(a,c)=n$$$.

A.txt 2 KB