Разбор задачи «Neon Panels»

Идея задачи

Нам дан массив b длины n-1. Нужно восстановить массив a длины n так, чтобы для каждого i выполнялось:

b[i] = a[i] & a[i+1]

Здесь & — побитовое AND.

Нужно либо построить любой подходящий массив a, либо вывести -1, если такого массива не существует.

Что означает побитовое AND

Если в числе b[i] некоторый бит равен 1, то этот бит обязан быть равен 1 и в a[i], и в a[i+1].

Если в b[i] бит равен 0, то это означает, что хотя бы в одном из чисел a[i] или a[i+1] этот бит равен 0.

Значит, каждое значение b[i] задаёт требования к соседней паре элементов массива a.

Как придумать конструкцию

Посмотрим на внутренний элемент a[i], где 1 <= i <= n-2.

Он участвует сразу в двух равенствах:

• b[i-1] = a[i-1] & a[i]
• b[i] = a[i] & a[i+1]

Если какой-то бит равен 1 в b[i-1], то этот бит обязан быть равен 1 в a[i]. Если какой-то бит равен 1 в b[i], то этот бит тоже обязан быть равен 1 в a[i].

Значит, естественный выбор такой:

a[i] = b[i-1] | b[i]

То есть мы берём побитовое OR соседних значений массива b.

Для крайних элементов всё проще:

• a[0] = b[0]
• a[n-1] = b[n-2]

Получаем конструкцию:

• a[0] = b[0]
• a[i] = b[i-1] | b[i] для 1 <= i <= n-2
• a[n-1] = b[n-2]

Но после этого обязательно нужно проверить, что все равенства действительно выполняются.

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

Иногда массив a, построенный по формуле, не подходит.

Рассмотрим пример:

b = [1, 0, 1]

Тогда по нашей формуле:

• a[0] = 1
• a[1] = 1 | 0 = 1
• a[2] = 0 | 1 = 1
• a[3] = 1

Проверим:

• a[0] & a[1] = 1 & 1 = 1 — хорошо
• a[1] & a[2] = 1 & 1 = 1, а должно быть 0 — плохо

Значит, здесь ответа не существует, и нужно выводить -1.

Поэтому алгоритм такой:

1. Строим массив a по формуле.
2. Проверяем все соседние пары.
3. Если хотя бы в одном месте не сошлось, выводим -1.

Почему проверка достаточно надёжна

Мы строим самый естественный кандидат на ответ:

• все биты, которые обязаны стоять в a[i], мы в него включаем;
• лишних ограничений мы специально не добавляем.

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

Именно поэтому достаточно проверить построенный массив. Если он подходит — выводим его. Если нет — ответа нет.

Пошаговый пример

Пусть:

b = [2, 4, 4, 2]

Тогда строим:

• a[0] = 2
• a[1] = 2 | 4 = 6
• a[2] = 4 | 4 = 4
• a[3] = 4 | 2 = 6
• a[4] = 2

Получаем:

a = [2, 6, 4, 6, 2]

Проверяем:

• 2 & 6 = 2
• 6 & 4 = 4
• 4 & 6 = 4
• 6 & 2 = 2

Все значения совпали. Значит, такой массив подходит.

Алгоритм

Для каждого теста:

1. Считать n и массив b длины n-1.

2. Построить массив a:

   • a[0] = b[0]
   • a[n-1] = b[n-2]
   • для внутренних позиций a[i] = b[i-1] | b[i]
3. Проверить для всех i, что (a[i] & a[i+1]) == b[i]
4. Если да — вывести массив a, иначе -1.

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

Докажем корректность.

Лемма 1

Если в некотором бите число b[i] содержит 1, то этот бит обязан быть равен 1 и в a[i], и в a[i+1].

Доказательство. По определению:

b[i] = a[i] & a[i+1]

Побитовое AND даёт 1 только тогда, когда в обоих числах в этом бите стоит 1. Лемма доказана.

Лемма 2

Для любой внутренней позиции i число a[i] обязано содержать все единичные биты из b[i-1] и b[i].

Доказательство. Из леммы 1:

• все единичные биты b[i-1] обязаны быть в a[i], потому что b[i-1] = a[i-1] & a[i];
• все единичные биты b[i] обязаны быть в a[i], потому что b[i] = a[i] & a[i+1].

Значит, a[i] должен содержать объединение этих битов, то есть b[i-1] | b[i]. Лемма доказана.

Лемма 3

Если построенный массив a удовлетворяет всем равенствам, то он является корректным ответом.

Доказательство. Это очевидно: если для всех i выполнено (a[i] & a[i+1]) == b[i], то массив a подходит по условию задачи.

Лемма 4

Если построенный по формуле массив a не проходит проверку, то ответа не существует.

Идея доказательства. Мы включили в каждый a[i] все биты, которые обязаны там стоять из-за соседних ограничений. Если при таком выборе уже возникает лишняя единица в AND соседней пары, значит, требования массива b противоречат друг другу. Исправить это невозможно, потому что убрать конфликтующий бит нельзя: он требуется хотя бы одним из соседних значений b.

Итог

Значит, наш алгоритм либо строит корректный ответ, либо верно определяет, что ответа нет.

Оценка сложности

Построение массива a занимает O(n). Проверка тоже занимает O(n).

Итого на один тест:

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;
        cin >> n;

        vector<int> b(n - 1);
        for (int i = 0; i < n - 1; i++) {
            cin >> b[i];
        }

        vector<int> a(n);
        a[0] = b[0];
        a[n - 1] = b[n - 2];

        for (int i = 1; i < n - 1; i++) {
            a[i] = b[i - 1] | b[i];
        }

        bool ok = true;
        for (int i = 0; i < n - 1; i++) {
            if ((a[i] & a[i + 1]) != b[i]) {
                ok = false;
                break;
            }
        }

        if (!ok) {
            cout << -1 << '\n';
        } else {
            for (int i = 0; i < n; i++) {
                cout << a[i] << (i + 1 == n ? '\n' : ' ');
            }
        }
    }

    return 0;
}

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

import sys


def solve():
    input = sys.stdin.readline
    t = int(input())
    out = []

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

        a = [0] * n
        a[0] = b[0]
        a[n - 1] = b[n - 2]

        for i in range(1, n - 1):
            a[i] = b[i - 1] | b[i]

        ok = True
        for i in range(n - 1):
            if (a[i] & a[i + 1]) != b[i]:
                ok = False
                break

        if not ok:
            out.append("-1")
        else:
            out.append(" ".join(map(str, a)))

    sys.stdout.write("\n".join(out))


solve()

Частые ошибки

1. Не делать финальную проверку

Это самая важная ошибка. Формула

a[i] = b[i-1] | b[i]

часто работает, но не всегда. Без проверки можно вывести неверный ответ там, где нужно печатать -1.

2. Неправильно обработать края массива

Нужно отдельно задать:

• a[0] = b[0]
• a[n-1] = b[n-2]

У крайних элементов только один сосед, поэтому формула для внутренних элементов к ним не применяется.

3. Перепутать операции | и &

При построении массива используется именно OR, а при проверке — AND.

Что важно запомнить

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

• AND говорит, какие биты обязаны быть одновременно у двух соседей.
• Поэтому внутренний элемент должен содержать объединение обязательных битов слева и справа.
• После построения обязательно нужно проверить результат.

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