CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) Разбор

Revision en2, by glebustim, 2023-09-18 20:09:22

We apologize for the technical difficulties in Task B. We hope you enjoyed the rest of the contest. We will add hints soon.

1870A - MEXanized Array

Tutorial

1870B - Friendly Arrays

Note that after performing the operation on $$$b_j$$$, which has some bit set to 1, this bit will become 1 for all numbers in $$$a$$$ (and will remain so, as a bit cannot change from 1 to 0 in the result of an OR operation). If $$$n$$$ is even, then in the final XOR, this bit will become 0, as it will be equal to the XOR of an even number of ones. If $$$n$$$ is odd, then this bit will be 1 in the final XOR.

Therefore, if $$$n$$$ is even, by performing the operation on $$$b_j$$$, we set all the bits that are 1 in $$$b_j$$$ to 0 in the final XOR. If $$$n$$$ is odd, we do the opposite and set these bits to 1. So, if $$$n$$$ is even, the XOR does not increase when applying the operation, which means that to obtain the minimum possible XOR, we need to apply the operation to all the numbers in $$$b$$$, and the maximum XOR will be the original XOR. For odd $$$n$$$, it is the opposite: the minimum is the original XOR, and the maximum is obtained after applying the operation to all elements in $$$b$$$.

To apply the operation to all elements in $$$b$$$, it is sufficient to calculate their bitwise OR and apply the operation to the array $$$a$$$ with it.

Tutorial

1870C - Colorful Table

Tutorial

1870D - Prefix Purchase

Tutorial

1870E - Another MEX Problem

Tutorial

1870F - Lazy Numbers

Tutorial

1870G - MEXanization

Tutorial

1870H - Standard Graph Problem

Tutorial

Please rate the problems, it will help us make the problems better next time!

Problem Feedback

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en16 English SomethingNew 2023-09-18 23:58:37 1057
en15 English SomethingNew 2023-09-18 21:33:38 6 Tiny change: 'ince $a_l >= a_{r_2}$,' -> 'ince $a_l \geq a_{r_2}$,'
ru17 Russian SomethingNew 2023-09-18 21:33:14 8
en14 English SomethingNew 2023-09-18 21:31:49 4
en13 English SomethingNew 2023-09-18 21:29:14 2 Tiny change: 'equal to $x$, and $0$' -> 'equal to $j$, and $0$'
ru16 Russian SomethingNew 2023-09-18 21:28:54 2 Мелкая правка: 'о равный $x$ и $0$ ин' -> 'о равный $j$ и $0$ ин'
ru15 Russian SomethingNew 2023-09-18 21:27:08 6 Мелкая правка: 'бработало через $k$ верши' -> 'бработало $k$ верши'
ru14 Russian SomethingNew 2023-09-18 21:26:43 1015
en12 English SomethingNew 2023-09-18 21:08:19 10
ru13 Russian SomethingNew 2023-09-18 21:07:05 10
ru12 Russian SomethingNew 2023-09-18 21:06:06 13
en11 English SomethingNew 2023-09-18 21:05:17 13
en10 English SomethingNew 2023-09-18 21:03:37 16
ru11 Russian SomethingNew 2023-09-18 21:02:44 1533
en9 English SomethingNew 2023-09-18 20:52:17 1696
en8 English glebustim 2023-09-18 20:41:22 1767
ru10 Russian glebustim 2023-09-18 20:40:56 1613
en7 English SomethingNew 2023-09-18 20:17:54 238
en6 English SomethingNew 2023-09-18 20:15:54 15
en5 English SomethingNew 2023-09-18 20:15:31 0 (published)
ru9 Russian SomethingNew 2023-09-18 20:14:45 0 (опубликовано)
ru8 Russian glebustim 2023-09-18 20:14:05 1040
en4 English SomethingNew 2023-09-18 20:13:44 102
ru7 Russian SomethingNew 2023-09-18 20:12:46 60
ru6 Russian SomethingNew 2023-09-18 20:12:13 48
ru5 Russian SomethingNew 2023-09-18 20:11:18 4 Мелкая правка: 'cdot \sqrt(n))$, вот та' -> 'cdot \sqrt{n})$, вот та'
en3 English glebustim 2023-09-18 20:09:49 68
ru4 Russian SomethingNew 2023-09-18 20:09:47 9685
en2 English glebustim 2023-09-18 20:09:22 1110
en1 English SomethingNew 2023-09-18 20:06:50 12342 Initial revision for English translation (saved to drafts)
ru3 Russian SomethingNew 2023-09-18 19:57:56 13962
ru2 Russian SomethingNew 2023-09-18 19:48:41 502
ru1 Russian SomethingNew 2023-09-18 19:46:32 16165 Первая редакция (сохранено в черновиках)