Автор: | Олександр Тимкович |
Підготовка задачі: | Олександр Тимкович, Павло Ціцей |
Розбір: | Олександр Тимкович |
Блок : a_i\le 1: Без будь-яких збільшень, XOR завжди не більше одного. Коли ми можемо отримати ? Розгляньте деякі випадки, коли присутній у масиві, а коли ні.
Блоки 2, 3, 4, 5: Зверніться до розв'язання блоку . Розв'язки цих блоків все ще існують, але з деякими важливими спостереженнями, які були пропущені для повного розв'язку.
Блок : без додаткових обмежень
Можна помітити, що a_i:=a_i+1 є такою ж операцією, як a_i:=a_i\oplus \Big(a_i\oplus (a_{i}+1)\Big)=a_i\oplus b_i, де b_i=a_i\oplus (a_{i}+1).
А саме, ми замінюємо "" на "\oplus b_i". У задачі нам потрібно мінімізувати a_1\oplus \dots\oplus a_n, отже, задача зводиться до знаходження множини \mathcal{S}\subseteq [n], для якої x=\bigoplus\limits_{i\in \mathcal{S}}b_i значення a_1\oplus \dots \oplus a_n\oplus x є мінімально можливим.
Наступне спостереження полягає в тому, що кожен b_i має форму 2^k-1 для деякого .
Щоб знайти множину , ми можемо використовувати жадібний підхід, намагаючись скасувати найбільш значущі біти A=a_1\oplus\dots \oplus a_n, використовуючи елементи з . Зверніть увагу, що має не більше \lceil\log_2 10^9\rceil \approx 30 різних значень, тому для кожного біта з ми можемо перебрати всі різні елементи в , щоб знайти відповідне значення.