UJGOI Party#411

UJGOI Party (Editorial)

Author:

Oleksandr Tymkovych

Task preparation:

Oleksandr Tymkovych, Pavlo Tsitsei

Editorial:

Oleksandr Tymkovych

Block : a_i\le 1: Without any increments, the XOR is at most one. When can we get ? Consider some cases when is present in the array and not.

Blocks 2, 3, 4, 5: Refer to the solution of block . The solutions to these blocks still exist, with some crucial observations missed.

Block : without additional constraints

One can notice that a_i:=a_i+1 is the same operation as a_i:=a_i\oplus \Big(a_i\oplus (a_{i}+1)\Big)=a_i\oplus b_i where b_i=a_i\oplus (a_{i}+1).

Namely, we replace the "" with "\oplus b_i". In the problem, we need to minimize a_1\oplus \dots\oplus a_n, hence the problem reduces to finding a set \mathcal{S}\subseteq [n] that for x=\bigoplus\limits_{i\in \mathcal{S}}b_i the value a_1\oplus \dots \oplus a_n\oplus x is minimal possible.

The next observation is that every b_i has the form of 2^k-1 for some .

To find the set , we can do greedy, trying to cancel out the most significant bits of A=a_1\oplus \dots \oplus a_n using elements from . Notice that has at most \lceil\log_2 10^9\rceil \approx 30 different values, so for each bit from we can iterate through all different elements in to find the proper value.