1

Меня заинтересовала задача acm-icpc-team с чисто алгоритмической точки зрения. Начну кратко с постановки задачи (я опишу сразу мат.модель - для тех, кого интересует исходная постановка https://www.hackerrank.com/challenges/acm-icpc-team):

Имеется последовательность чисел (a_1, ...a_N). Нужно найти максимальное количество пар (a_i, a_j), таких что a_i | a_j (побитовое ИЛИ) имеет максимальное количество установленных битов. (2 <= n <= 500, 1 <= m (количество бит в числе (учитывая возможные старшие нулевые)<= 500).

Ради интереса я попробовал реализовать решение перебором за O(M * N^2) на Питоне (на вход подаются бинарные представления чисел):

def tops(x, y):
    c = 0
    for i in range(len(x)):
        c += 1 if x[i] == '1' or y[i] == '1' else 0
    return c

n,m = map(int, input().strip().split())
max_v, max_c = 0, 0
ts = [input().strip() for i in range(n)]
for i in range(n):
    for j in range(i + 1, n):
        ts_c = tops(ts[i], ts[j])
        if max_v < ts_c:
            max_v, max_c = ts_c, 0
        if max_v == ts_c:
            max_c += 1
print(max_v, max_c, sep='\n')            

Решение прошло по ограничениям по скорости. Но меня интересует более оптимальный алгоритм. Поэтому хочется узнать, может кто-нибудь знает какой-нибудь алгоритм, который позволит решить эту задачу более быстрым способом? Гугл быстро мне в этом вопросе не помог. Единственно что я нашел чем-то похожу задачу - maximum inner-product search (но там используется скалярное произведение вместо bitwise or). поэтому в ту тему углубляться не стал

UPD: я посмотрел бегло обсуждение проблемы (решение задачи)- в ответе предлагается только брутфорс, поэтому думаю ответ на задачу видимо будет более сложен

2
  • XOR операция возможно как-то поможет, хотя сходу я не вижу.
    – 0andriy
    27 авг 2017 в 12:48
  • @0andriy, а можете пояснить, каким образом может помочь? 27 авг 2017 в 14:31

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Посмотрите другие вопросы с метками или задайте свой вопрос.