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.