Гайдо́ра чи не Гайдо́ра?#12298

Гайдо́ра чи не Гайдо́ра? (Розбір)

Автор задачі:	Хайдара Аль Макдід
Підготовлено:	Хайдара Аль Макдід
Редагував:	Хасан Салех (MathModel)

Розв'язок

Ми хочемо максимізувати значення

a_{1} & a_{2} & \dots & a_{n}

a_1 \,\&\, a_2 \,\&\, \dots \,\&\, a_n

після вибору точно $k$ різних індексів і заміни кожного вибраного $a_{i}$ a_i на його 32-бітне побітове заперечення $\sim a_{i}$ \sim a_i. Оскільки $\sim$ береться над 32 бітами, ми можемо розглядати це як $\sim x = (2^{32} - 1) - x$ \sim x = (2^{32}-1) - x, або, еквівалентно, $\sim x = (MASK^x)$ \sim x = (\texttt{MASK} \,\hat{}\, x) з $MASK = 2^{32} - 1$ \texttt{MASK} = 2^{32}-1.

Нехай остаточна відповідь буде $X$ . Для кожного біта, який дорівнює $1$ в $X$ , кожен елемент у фінальному масиві також повинен мати цей біт рівним $1$ , інакше AND матиме $0$ у цій позиції. Це підказує про побудову $X$ жадібно біт за бітом, починаючи з найбільш значущого біта до найменш значущого: ми підтримуємо поточну відповідь ans, і для кожного біта $j$ з $31$ до $0$ ми намагаємося встановити його в $1$ поверх того, що ми вже зафіксували.

Конкретно, на біті $j$ ми формуємо кандидатне значення

cand = ans ∣ (1 ≪ j),

\texttt{cand} = \texttt{ans} \,\vert\, (1 \ll j),

що означає, що ми хочемо, щоб фінальний AND мав усі біти, які дорівнюють $1$ у cand. Для цього зафіксованого cand ми проводимо перевірку здійсненності на всьому масиві. Для кожного елемента $x = a_{i}$ x = a_i є лише два стани у фінальній конфігурації: або ми зберігаємо його як $x$ , або ми перевертаємо його на $y =\sim x = (MASK - x)$ y = \sim x = (\texttt{MASK} - x). Щоб cand було досяжним, для кожної позиції $i$ принаймні один з цих варіантів повинен повністю покривати всі біти cand:

keep_ok ⟺ (x & cand) = cand, flip_ok ⟺ (y & cand) = cand .

\text{keep\_ok} \iff (x \,\&\, \texttt{cand}) = \texttt{cand}, \qquad \text{flip\_ok} \iff (y \,\&\, \texttt{cand}) = \texttt{cand}.

Дивлячись на $(keep_ok, flip_ok)$ (\text{keep\_ok}, \text{flip\_ok}), ми ділимо індекси на три корисні типи:

Якщо обидва є хибними, ні $x$ , ні $\sim x$ не мають усіх бітів cand, тому цей індекс ніколи не може задовольнити cand. Тоді cand сама по собі є неможливою, і ми повинні відхилити цей біт.
Якщо $keep_ok = false$ \text{keep\_ok} = \text{false} і $flip_ok = true$ \text{flip\_ok} = \text{true}, ми змушені перевернути цей індекс, щоб задовольнити cand. Нехай $F$ буде кількість таких змушених індексів.
Якщо $keep_ok = true$ \text{keep\_ok} = \text{true} і $flip_ok = true$ \text{flip\_ok} = \text{true}, цей індекс є гнучким: як збереження, так і перевертання все ще задовольняють cand. Нехай $C$ буде кількість таких гнучких індексів.

(Коли $keep_ok = true$ \text{keep\_ok} = \text{true} і $flip_ok = false$ \text{flip\_ok} = \text{false}, ми просто повинні зберегти елемент; це не споживає жодного перевертання і не дає жодної гнучкості.)

Ми повинні виконати точно $k$ перевертів загалом. Для фіксованого cand усі $F$ змушені індекси повинні бути перевернуті, тому нам потрібно принаймні $F$ перевертів. З іншого боку, ми можемо за бажанням перевернути будь-яку підмножину з $C$ гнучких індексів, тому загальна кількість перевертів, які ми можемо реалізувати, залишаючи cand задовольняти, коливається від $F$ (тільки змушені) до $F + C$ F+C (змушені плюс усі гнучкі). Отже, cand є здійсненним, якщо і тільки якщо

F \leq k \leq F + C .

F \le k \le F + C.

Якщо ця нерівність виконується, ми знаємо, що існує спосіб вибрати точно $k$ індексів для перевертання так, щоб кожен фінальний елемент покривав усі біти cand. У цьому випадку ми приймаємо цей біт і встановлюємо $ans := cand$ \texttt{ans} := \texttt{cand}. Якщо ні, ми залишаємо біт на $0$ в ans і переходимо до наступного нижчого біта.

Оскільки ми обробляємо біти з найбільш значущого вниз і встановлюємо біт лише тоді, коли існує якась конфігурація з точно $k$ перевертаннями, яка підтримує всі вибрані біти до цього моменту, отримане ans є лексикографічно (а отже, чисельно) максимальним фінальним AND, який можна досягти. Для кожної з $32$ позицій біта ми скануємо всі $n$ елементів один раз, тому загальна складність становить $O (32 n) = O (n)$ O(32n) = O(n) за часом і $O (1)$ додаткової пам'яті, крім масиву вхідних даних.

n,k=map(int, input().split())
a=list(map(int, input().split()))

MASK=(1<<32)-1
ans=0

for j in range(31, -1, -1):
    p=1<<j
    cand = ans | p
    forced = 0
    flex = 0
    ok = True
    for x in a:
        keep = (x & cand) == cand
        flipped = (~x) & MASK     
        flip = (flipped & cand) == cand

        if not keep and not flip:
            ok = False
            break
        if not keep and flip:
            forced += 1       
        elif keep and flip:
            flex += 1         

    if not ok:
        continue

    rem = k - forced
    if rem < 0 or rem > flex:
        continue

    ans = cand

print(ans)

Python