Codeforces Round #804 (Div. 2) Editorial reupload

Правка en13, от Gheal, 2022-10-31 21:11:37

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en42 Английский tibinyte 2022-11-06 21:29:15 0 (published)
en41 Английский tibinyte 2022-11-06 19:15:16 0 (saved to drafts)
en40 Английский Gheal 2022-10-31 22:14:25 0 (published)
en39 Английский Gheal 2022-10-31 22:12:04 16
en38 Английский Gheal 2022-10-31 22:11:13 13 Tiny change: 'er authors of round 804. We are v' -> 'er authors. We are v'
en37 Английский Gheal 2022-10-31 22:10:53 211
en36 Английский Gheal 2022-10-31 22:04:25 26
en35 Английский Gheal 2022-10-31 22:03:40 39
en34 Английский Gheal 2022-10-31 22:01:52 74
en33 Английский Gheal 2022-10-31 21:57:17 200
en32 Английский Gheal 2022-10-31 21:57:01 747
en31 Английский Gheal 2022-10-31 21:48:53 629
en30 Английский tibinyte 2022-10-31 21:41:38 7
en29 Английский tibinyte 2022-10-31 21:41:03 38
en28 Английский Gheal 2022-10-31 21:38:59 40
en27 Английский tibinyte 2022-10-31 21:37:09 17
en26 Английский Gheal 2022-10-31 21:34:15 81
en25 Английский Gheal 2022-10-31 21:33:19 2311
en24 Английский tibinyte 2022-10-31 21:33:02 34
en23 Английский tibinyte 2022-10-31 21:32:50 340
en22 Английский tibinyte 2022-10-31 21:31:52 3999
en21 Английский tibinyte 2022-10-31 21:29:21 303
en20 Английский tibinyte 2022-10-31 21:29:00 18 Tiny change: 'anks to \ncadmiumky\n ):\n\nT' -> 'anks to \n[user:cadmiumky]\n ):\n\nT'
en19 Английский tibinyte 2022-10-31 21:28:31 4797
en18 Английский Gheal 2022-10-31 21:27:42 924
en17 Английский Gheal 2022-10-31 21:18:46 409
en16 Английский Gheal 2022-10-31 21:16:45 519
en15 Английский Gheal 2022-10-31 21:13:59 46
en14 Английский Gheal 2022-10-31 21:12:58 48
en13 Английский Gheal 2022-10-31 21:11:37 1405
en12 Английский tibinyte 2022-10-31 00:18:26 7
en11 Английский tibinyte 2022-10-31 00:18:18 79
en10 Английский tibinyte 2022-10-31 00:18:10 73
en9 Английский tibinyte 2022-10-31 00:18:00 3259
en8 Английский tibinyte 2022-10-31 00:16:45 3531
en7 Английский tibinyte 2022-10-31 00:15:55 2754
en6 Английский tibinyte 2022-10-31 00:15:29 2047
en5 Английский tibinyte 2022-10-31 00:14:20 1085
en4 Английский tibinyte 2022-10-31 00:12:33 2468
en3 Английский tibinyte 2022-10-31 00:08:20 10
en2 Английский tibinyte 2022-10-31 00:07:58 2606
en1 Английский Gheal 2022-10-30 23:34:08 50 Initial revision (saved to drafts)