Разбор задачи Bitwise Balance

Идея задачи

Нужно найти неотрицательное целое число a, для которого выполняется равенство:

[ (a \mid b) - (a & c) = d ]

Здесь:

• | — побитовое ИЛИ,
• & — побитовое И.

Нам даны числа b, c и d. Нужно либо восстановить подходящее число a, либо понять, что такого числа не существует.

На первый взгляд выражение выглядит неудобно: в нём есть и побитовое ИЛИ, и побитовое И, и ещё вычитание. Но в этой задаче есть очень важное наблюдение, которое делает решение коротким и аккуратным.

Главное наблюдение

Рассмотрим отдельно один бит числа a.

Пусть в некотором разряде:

• бит числа a равен x,
• бит числа b равен y,
• бит числа c равен z,
• бит числа d равен t.

Тогда в этом разряде должно выполняться:

[ (x \mid y) - (x & z) = t ]

Почему можно рассматривать каждый бит независимо?

Потому что для любого разряда значение (x & z) никогда не больше (x | y).

Действительно:

• если (x & z) = 1, то обязательно x = 1,
• тогда (x | y) тоже обязательно равно 1.

Значит, в каждом бите мы вычитаем либо 0 из 0 или 1, либо 1 из 1. Ситуации 0 - 1 не бывает. А значит, заёмов между соседними битами не возникает.

Это очень важно: если заёмов нет, то каждый бит можно обрабатывать отдельно.

Разбор одного бита

Переберём все возможные значения битов b и c.

Случай 1: y = 0, z = 0

Тогда:

[ (x \mid 0) - (x & 0) = x - 0 = x ]

Значит:

[ t = x ]

То есть бит a определяется однозначно:

• если t = 0, то x = 0,
• если t = 1, то x = 1.

Случай 2: y = 0, z = 1

Тогда:

[ (x \mid 0) - (x & 1) = x - x = 0 ]

Значит, в этом бите результат всегда равен 0.

То есть:

• если t = 1, решения нет;
• если t = 0, можно взять любой x, например 0.

Случай 3: y = 1, z = 0

Тогда:

[ (x \mid 1) - (x & 0) = 1 - 0 = 1 ]

Значит, в этом бите результат всегда равен 1.

То есть:

• если t = 0, решения нет;
• если t = 1, можно взять любой x, например 0.

Случай 4: y = 1, z = 1

Тогда:

[ (x \mid 1) - (x & 1) = 1 - x ]

Получаем:

• если t = 1, то x = 0,
• если t = 0, то x = 1.

То есть:

[ x = 1 - t ]

Удобная таблица

Из таблицы видно, что противоречие возникает только в двух случаях:

• b_i = 0, c_i = 1, d_i = 1
• b_i = 1, c_i = 0, d_i = 0

Если хотя бы в одном бите встретился такой случай, ответа не существует.

Алгоритм

Для каждого набора данных:

1. Идём по всем битам, например от 0 до 60.
2. Считываем соответствующие биты чисел b, c и d.

3. По таблице определяем:

   • можно ли подобрать бит a,
   • если можно, чему он должен быть равен.
4. Собираем число a по битам.
5. Если хотя бы в одном бите возникло противоречие, выводим -1.

Так как числа до 10^18, достаточно проверить 61 бит.

Почему алгоритм корректен

Докажем это аккуратно.

1. Биты действительно независимы

В каждом разряде бит числа (a & c) не превосходит бит числа (a | b). Поэтому при вычитании

[ (a \mid b) - (a & c) ]

не возникает займа из старших разрядов.

Значит, значение результата в каждом бите определяется только битами a, b и c в этом же разряде.

2. Для каждого бита таблица разобрана полностью

Мы рассмотрели все 4 возможные пары (b_i, c_i):

• (0, 0)
• (0, 1)
• (1, 0)
• (1, 1)

и для каждой пары точно определили:

• когда существует допустимый бит a_i,
• чему он должен быть равен.

3. Если алгоритм построил a, то оно подходит

Во всех битах мы выбираем a_i так, чтобы выполнялось локальное равенство

[ (a_i \mid b_i) - (a_i & c_i) = d_i. ]

Так как биты независимы, то после объединения всех разрядов получаем

[ (a \mid b) - (a & c) = d. ]

4. Если алгоритм вывел -1, то решения не существует

Если в каком-то разряде встретилось противоречие, то в этом бите нельзя подобрать a_i, чтобы получить нужный бит d_i.

Так как биты независимы, исправить это за счёт других разрядов невозможно. Значит, решения не существует.

Следовательно, алгоритм корректен.

Сложность

Мы проверяем всего 61 бит для каждого теста.

• Время: O(61) на один набор, то есть фактически O(1)
• Память: O(1)

Эталонная реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        unsigned long long b, c, d;
        cin >> b >> c >> d;

        unsigned long long a = 0;
        bool ok = true;

        for (int i = 0; i <= 60; i++) {
            int bi = (b >> i) & 1ULL;
            int ci = (c >> i) & 1ULL;
            int di = (d >> i) & 1ULL;

            if (bi == 0 && ci == 0) {
                if (di == 1) {
                    a |= (1ULL << i);
                }
            } else if (bi == 0 && ci == 1) {
                if (di == 1) {
                    ok = false;
                    break;
                }
            } else if (bi == 1 && ci == 0) {
                if (di == 0) {
                    ok = false;
                    break;
                }
            } else {
                if (di == 0) {
                    a |= (1ULL << i);
                }
            }
        }

        if (ok) {
            cout << a << '\n';
        } else {
            cout << -1 << '\n';
        }
    }

    return 0;
}

Эталонная реализация на Python

import sys

input = sys.stdin.readline

t = int(input())
for _ in range(t):
    b, c, d = map(int, input().split())

    a = 0
    ok = True

    for i in range(61):
        bi = (b >> i) & 1
        ci = (c >> i) & 1
        di = (d >> i) & 1

        if bi == 0 and ci == 0:
            if di == 1:
                a |= (1 << i)

        elif bi == 0 and ci == 1:
            if di == 1:
                ok = False
                break

        elif bi == 1 and ci == 0:
            if di == 0:
                ok = False
                break

        else:
            if di == 0:
                a |= (1 << i)

    if ok:
        print(a)
    else:
        print(-1)

Разберём маленький пример вручную

Пусть:

• b = 3, это 011 в двоичной записи,
• c = 3, это 011,
• d = 0, это 000.

Нужно найти a.

Смотрим по битам:

• в нулевом бите: b_i = 1, c_i = 1, d_i = 0, значит a_i = 1
• в первом бите: b_i = 1, c_i = 1, d_i = 0, значит a_i = 1
• в остальных битах все нули, значит можно брать a_i = 0

Получаем a = 3.

Проверим:

[ (3 | 3) - (3 & 3) = 3 - 3 = 0 ]

Всё верно.

Типичные ошибки

Ошибка 1. Пытаться подбирать a обычным перебором

Числа могут быть до 10^18, поэтому перебор невозможен.

Ошибка 2. Думать, что при вычитании будут заёмы между битами

В этой задаче именно важное свойство выражения и состоит в том, что заёмов нет. Без этого наблюдения решение кажется гораздо сложнее.

Ошибка 3. Перебирать слишком мало битов

Так как числа могут доходить до 10^18, нужно проверять хотя бы до 60-го бита включительно.

Ошибка 4. Считать, что ответ единственный

Ответов может быть несколько. В некоторых случаях бит a_i можно выбрать разными способами. Нужно вывести любой подходящий.

Вывод

Хотя формула выглядит необычно, задача сводится к очень простой побитовой конструкции.

Ключевая идея такая:

• заметить, что в выражении (a | b) - (a & c) нет заёмов между битами;
• разобрать 4 случая для пары битов (b_i, c_i);
• по ним восстановить число a.

После этого решение получается коротким, быстрым и надёжным.