AND path#180

AND path (Editorial)

Максимізується побітове AND по шляху, а особливість цієї операції в тому, що результат ніколи не «вмикає» біт, якого немає хоча б в одного числа шляху. Тому працює класична техніка — жадібне добирання відповіді від старшого біта.

Ітеруватимемо біти від найстаршого до нульового, підтримуючи поточну маску-кандидат $ans$ (спочатку нуль). На кроці для біта $t$ спробуємо маску $cand = ans ∣ 2^{t}$ \mathrm{cand} = \mathrm{ans} \mathbin{|} 2^t і перевіримо, чи існує шлях, у якому всі клітинки містять усі біти цієї маски. Якщо існує — залишаємо $ans = cand$ \mathrm{ans} = \mathrm{cand}, інакше цей біт недосяжний і ми його не беремо.

Перевірка — проста динаміка на сітці. Клітинка $(i, j)$ вважається прохідною, якщо $a_{i, j} & cand = cand$ a_{i,j} \mathbin{\&} \mathrm{cand} = \mathrm{cand}. Тоді

reach [i] [j] = прохідна (i, j) та (reach [i - 1] [j] або reach [i] [j - 1]),

\mathrm{reach}[i][j] = \text{прохідна}(i,j) \ \text{та} \ \bigl(\mathrm{reach}[i-1][j] \ \text{або} \ \mathrm{reach}[i][j-1]\bigr),

з базою $reach [1] [1] = прохідна (1, 1)$ \mathrm{reach}[1][1] = \text{прохідна}(1,1). Шлях існує, якщо $reach [n] [m]$ істинне.

Чому жадібність коректна? Старший біт «важить» більше, ніж усі молодші разом узяті, тому якщо його можна отримати — його треба брати, незалежно від того, що буде далі.

Складність — $O (B \cdot n \cdot m)$ \mathcal{O}(B \cdot n \cdot m), де $B$ — кількість бітів у числах. Значення можуть бути великими, тому працюйте у 64-бітному типі й перебирайте біти аж до $62$ -го.

cand = ans ∣ 2^{t}

ans = cand

a_{i, j} & cand = cand

reach [i] [j] = прохідна (i, j) та (reach [i - 1] [j] або reach [i] [j - 1]),

reach [1] [1] = прохідна (1, 1)

O (B \cdot n \cdot m)