Разбор задачи «Хранители кристаллов»

Идея задачи

Даны все числа от 0 до n-1, где ([codeforces.com](https://codeforces.com/problemset/problem/1630/A))ки. Нужно разбить их на пары так, чтобы сумма значенийa & bпо всем парам была ровноk`.

Задача конструктивная: не нужно искать пары перебором или оптимизацией. Здесь важно заметить удачное свойство чисел от 0 до n-1 и по нему сразу построить ответ.

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

Так как n — степень двойки, число n - 1 в двоичной записи состоит только из единиц:

• при n = 4 это 3 = 11₂,
• при n = 8 это 7 = 111₂,
• при n = 16 это 15 = 1111₂.

Для любого числа x рассмотрим число

y = (n - 1) ^ x

Это побитовое дополнение числа x внутри диапазона от 0 до n-1.

Например, при n = 8:

• 0 <-> 7,
• 1 <-> 6,
• 2 <-> 5,
• 3 <-> 4.

Почему такие пары удобны? Потому что

x & ((n - 1) ^ x) = 0

У числа и его дополнения нет битов, которые одновременно равны 1, значит их побитовое И равно нулю.

Следовательно, если попарить все числа именно так, то суммарный вклад всех пар будет равен 0.

Это базовая конструкция. Теперь нужно научиться немного менять её так, чтобы получать нужное значение k.

Разбор случаев

Случай 1. k = 0

Это самый простой случай.

Достаточно вывести пары

• (0, n-1)
• (1, n-2)
• (2, n-3)
• и так далее.

То есть для каждого x берём пару

(x, (n - 1) ^ x)

У каждой такой пары значение AND равно нулю, значит и общая сумма тоже равна нулю.

Случай 2. 0 < k < n - 1

Хотим получить суммарный вклад ровно k.

Для этого возьмём две специальные пары:

• (k, n - 1)
• (0, (n - 1) ^ k)

Посчитаем их вклад:

• k & (n - 1) = k, потому что n - 1 состоит из единиц во всех нужных битах,
• 0 & ((n - 1) ^ k) = 0.

Итого эти две пары уже дают сумму k.

Все остальные ещё не использованные числа можно попарить стандартным способом:

(x, (n - 1) ^ x)

Их вклад будет равен нулю, поэтому общая сумма останется равной k.

Пример

Пусть n = 8, k = 5.

Тогда n - 1 = 7.

Берём специальные пары:

• (5, 7) даёт 5 & 7 = 5,
• (0, 2) даёт 0 & 2 = 0, потому что 2 = 7 ^ 5.

Оставшиеся числа: 1, 3, 4, 6.

Попарим их дополнениями:

• (1, 6)
• (3, 4)

Их вклад равен нулю.

Итоговая сумма: 5.

Случай 3. k = n - 1

Это особый случай.

Подслучай n = 4

Здесь ответа не существует.

Числа: 0, 1, 2, 3.

Возможные разбиения всего три:

• (0, 1) и (2, 3) дают сумму 0 + 2 = 2,
• (0, 2) и (1, 3) дают сумму 0 + 1 = 1,
• (0, 3) и (1, 2) дают сумму 0 + 0 = 0.

Получить 3 невозможно, поэтому нужно вывести -1.

Подслучай n > 4

Здесь решение уже существует, но базовая конструкция напрямую не сработает, поэтому используем специальный шаблон:

• (n - 1, n - 2)
• (1, 3)
• (0, n - 4)

Посчитаем вклад:

• (n - 1) & (n - 2) = n - 2,
• 1 & 3 = 1,
• 0 & (n - 4) = 0.

Сумма равна

(n - 2) + 1 = n - 1.

То есть мы уже получили нужное значение.

Все остальные числа снова можно разбить на пары вида

(x, (n - 1) ^ x)

Их вклад будет равен нулю.

Пример

Пусть n = 8, k = 7.

Тогда можно взять:

• (7, 6) → 7 & 6 = 6,
• (1, 3) → 1 & 3 = 1,
• (0, 4) → 0 & 4 = 0.

Сумма уже равна 7.

Оставшиеся числа 2 и 5 образуют пару (2, 5), у которой 2 & 5 = 0.

Почему конструкция корректна

Докажем это по случаям.

1. Обычные дополнительные пары

Для любой пары вида

(x, (n - 1) ^ x)

все биты одного числа противоположны битам второго. Значит, не существует позиции, где в обоих числах одновременно стоит 1. Следовательно,

x & ((n - 1) ^ x) = 0.

2. Случай k = 0

Все пары имеют вид дополнений, значит каждая даёт вклад 0. Суммарный ответ равен 0.

3. Случай 0 < k < n - 1

Мы специально создаём пары:

• (k, n - 1) с вкладом k,
• (0, (n - 1) ^ k) с вкладом 0.

Остальные пары дают вклад 0, потому что составлены из дополнений. Значит итоговая сумма равна k.

4. Случай k = n - 1, n > 4

Специальные три пары дают вклад

(n - 2) + 1 + 0 = n - 1.

Остальные пары имеют нулевой вклад. Следовательно, итоговая сумма равна n - 1.

5. Случай n = 4, k = 3

Мы перебрали все возможные разбиения и увидели, что суммы 3 среди них нет. Значит ответа действительно не существует.

Как реализовать построение

Удобно завести массив used, который показывает, какие числа уже заняты в специальных парах.

Дальше можно пройти по всем x от 0 до n-1, вычислить

y = (n - 1) ^ x

и, если ни x, ни y ещё не использованы, добавить пару (x, y).

Так мы аккуратно доберём все оставшиеся числа.

Сложность

Для каждого теста мы делаем один проход по всем числам от 0 до n-1.

Поэтому:

• время работы: O(n),
• память: O(n).

Это хорошо укладывается в ограничения.

Эталонное решение на C++

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

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

    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;

        if (k == n - 1) {
            if (n == 4) {
                cout << -1 << '\n';
                continue;
            }

            vector<bool> used(n, false);

            cout << n - 1 << ' ' << n - 2 << '\n';
            cout << 1 << ' ' << 3 << '\n';
            cout << 0 << ' ' << n - 4 << '\n';

            used[n - 1] = true;
            used[n - 2] = true;
            used[1] = true;
            used[3] = true;
            used[0] = true;
            used[n - 4] = true;

            for (int x = 0; x < n; x++) {
                int y = (n - 1) ^ x;
                if (used[x] || used[y]) {
                    continue;
                }
                cout << x << ' ' << y << '\n';
                used[x] = true;
                used[y] = true;
            }
        } else {
            vector<bool> used(n, false);

            if (k == 0) {
                for (int x = 0; x < n; x++) {
                    int y = (n - 1) ^ x;
                    if (used[x] || used[y]) {
                        continue;
                    }
                    cout << x << ' ' << y << '\n';
                    used[x] = true;
                    used[y] = true;
                }
            } else {
                cout << k << ' ' << n - 1 << '\n';
                cout << 0 << ' ' << ((n - 1) ^ k) << '\n';

                used[k] = true;
                used[n - 1] = true;
                used[0] = true;
                used[(n - 1) ^ k] = true;

                for (int x = 0; x < n; x++) {
                    int y = (n - 1) ^ x;
                    if (used[x] || used[y]) {
                        continue;
                    }
                    cout << x << ' ' << y << '\n';
                    used[x] = true;
                    used[y] = true;
                }
            }
        }
    }

    return 0;
}

Эталонное решение на Python

import sys

input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n, k = map(int, input().split())

    if k == n - 1:
        if n == 4:
            print(-1)
            continue

        used = [False] * n
        ans = []

        ans.append((n - 1, n - 2))
        ans.append((1, 3))
        ans.append((0, n - 4))

        used[n - 1] = True
        used[n - 2] = True
        used[1] = True
        used[3] = True
        used[0] = True
        used[n - 4] = True

        for x in range(n):
            y = (n - 1) ^ x
            if used[x] or used[y]:
                continue
            ans.append((x, y))
            used[x] = True
            used[y] = True

        for a, b in ans:
            print(a, b)

    else:
        used = [False] * n
        ans = []

        if k == 0:
            for x in range(n):
                y = (n - 1) ^ x
                if used[x] or used[y]:
                    continue
                ans.append((x, y))
                used[x] = True
                used[y] = True
        else:
            ans.append((k, n - 1))
            ans.append((0, (n - 1) ^ k))

            used[k] = True
            used[n - 1] = True
            used[0] = True
            used[(n - 1) ^ k] = True

            for x in range(n):
                y = (n - 1) ^ x
                if used[x] or used[y]:
                    continue
                ans.append((x, y))
                used[x] = True
                used[y] = True

        for a, b in ans:
            print(a, b)

Что полезно запомнить из этой задачи

В задачах на побитовые операции часто очень полезно смотреть на число вида 2^m - 1. У такого числа все младшие биты равны единице, поэтому операции с ним часто превращаются в аккуратное «дополнение» числа внутри диапазона.

Здесь именно это свойство позволило построить почти все пары с нулевым вкладом, а затем добавить несколько специальных пар, которые дают нужную сумму.

Это хороший пример конструктивной задачи, где важнее заметить правильный шаблон, чем пытаться что-то подбирать перебором.