Примечания к задаче

Крош и битовые операции — очень интересная задача, основанная на свойствах операции побитового исключающего ИЛИ, которую можно встретить в Зимнем личном турнире памяти С. А. Григорьева в 2023 году.

Условия к задаче

Данные

Имя входного файла: Стандартный ввод / input.txt

Имя выходного файла: Стандартный вывод / output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Условие

Крош недавно ознакомился с битовыми операциями, и ему в голову пришла следующая задача: Пусть дан массив A из 2ⁿ неотрицательных элементов $$$a_{0}$$$,$$$a_{1}$$$,...,$$$a_{2ⁿ−1}$$$. Ему нравится операция побитового исключающего ИЛИ – xor, поэтому он рассматривает все пары индексов (i,j), такие, что i⊕j=k, где k – заданное число, ⊕ – операция побитового исключающего ИЛИ. По всем таким парам он хочет найти наибольшее суммарное значение величины $$$a_{i}$$$+$$$a_{j}$$$.

Формат входных данных

В первой строке вам дано число n (1 ≤ n ≤ 18) и число k (1 ≤ k < 2ⁿ). В следующей строке вам даны 2ⁿ целых неотрицательных чисел – $$$a_{0}$$$,$$$a_{1}$$$,...,$$$a_{2ⁿ−1}$$$ (0 ≤ $$$a_{i}$$$ ≤ 10⁹).

Формат выходных данных

Выведите ответ на задачу.

Система оценки

• Подзадача 1 (40 баллов) n ≤ 9.
• Подзадача 2 (60 баллов) без дополнительных ограничений.

Пример

Стандартный ввод:

3 3

1 4 2 7 3 1 5 2

Стандартный вывод:

8

Объяснение задачи

Ввод

Первым делом, мы должны прописать правильный ввод данных.

Реализовать ввод нескольких значений в одну строку можно при помощи встроенной функции map:

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

Таким образом, мы присвоили переменным n, k значения, введя их в одну строку. Тоже самое мы делаем с набором чисел a. При этом, мы преобразуем его в список при помощи функции list:

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

Теперь, в переменной a хранится список, состоящий из введённых во второй строке чисел через пробел. Получаем код:

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

Алгоритм решения

Что же делать дальше? Как решить задачу?

40 баллов ✓

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

Давайте попробуем его написать, для начала создаём вложенный цикл, в котором мы будем перебирать индексы i и j:

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(2 ** n):
    for j in range(2 ** n):
        pass

Мы перебираем индексы именно до 2ⁿ, так как длина списка по условию задачи равна 2ⁿ. Ничего не делающий оператор-заглушка pass оставлен для удобства, он показывает место, где мы ещё не успели дописать код.

Теперь нам нужно сделать поиск максимума, это тоже не так трудно. Перед началом цикла создадим переменную, в которую будем записывать максимум, а в самом цикле сделаем проверку выполнения равенства i⊕j=k и обновление максимума, которое ориентируется на сумму i-того и j-того элементов. Не забудем и про вывод ответа, в результате получив следующий код:

n, k = map(int, input().split())
a = list(map(int, input().split()))
mx = -1
for i in range(2 ** n):
    for j in range(2 ** n):
        if i ^ j == k and a[i] + a[j] > mx:
            mx = a[i] + a[j]
print(mx)

Обратите внимание, что за выполнение операции побитового исключающего ИЛИ в языке Python отвечает оператор ^.

Из-за вложенного цикла данный код будет работать довольно медленно, из-за чего он превысит ограничение по времени выполнения на второй подзадаче. В результате, за этот код мы получим 40 баллов.

100 баллов ✓✓

Как же оптимизировать алгоритм и не напороться на ограничение по времени выполнения? Для этого нам нужно избавиться от вложенного цикла из решения на 40 баллов, так как он сильно замедляет время работы нашей программы.

Сделать это можно, опираясь на интересное свойство операции xor. Это свойство гласит о том, что если выполняется равенство i⊕j=k, то тогда j=i⊕k (в этом можно убедиться и самостоятельно, подобрав разные числа и сравнив значения чисел i, j, k). Таким образом, зная индекс i, мы можем найти подходящий к нему индекс j при помощи числа k (т. к. j=i⊕k). Это означает, что мы можем перебирать только индексы i и уже по ним находить индексы j и проводить поиск максимальной суммы.

Вот так мы и должны заменить вложенный цикл на линейный, что позволит нам обойти ограничение по времени выполнения нашей программы. Теперь осталось лишь написать наш "победный" код. Сделать это очень просто, для начала создадим линейный цикл, перебирающий индексы i:

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(2 ** n):
    pass

Мы перебираем индексы именно до 2ⁿ, так как длина списка по условию задачи равна 2ⁿ. Ничего не делающий оператор-заглушка pass оставлен для удобства, он показывает место, где мы ещё не успели дописать код.

Далее нам нужно сделать поиск максимума, это тоже не так трудно. Перед началом цикла создадим переменную, в которую будем записывать максимум, а в самом цикле будем находить индекс j по формуле j=i⊕k и обновлять максимум, ориентируясь на сумму i-того и j-того элементов. Не забудем и про вывод ответа, в результате получив следующий конечный код:

n, k = map(int, input().split())
a = list(map(int, input().split()))
mx = -1
for i in range(2 ** n):
    j = i ^ k
    if a[i] + a[j] > mx:
        mx = a[i] + a[j]

Обратите внимание, что за выполнение операции побитового исключающего ИЛИ в языке Python отвечает оператор ^.

За счёт использования в коде линейного цикла вместо вложенного, данная программа не превысит ограничения по времени ни на одной из подзадач, в результате чего мы получим 100 баллов за её решение. Вот и всё, задача решена.

Мой комментарий

Вот таким вот получился разбор, очень надеюсь, что вам он понравился. Если так и есть, то обязательно голосуйте плюсиком за этот разбор, мне будет очень приятно :)

Обратите внимание, что задача для этого разбора намного сложнее задачи для предыдущего, так что если вам что-то непонятно, вы хотите предложить задачу на разбор или рассказать о вашем решении, то обязательно пишите в комментариях ваши сообщения, я буду очень рад с вами пообщаться!

Всем удачи! :D