Интервьюшную загадку заганули - Playing poohsticks in the Styx — LiveJournal

Попарных - это как? Соседние числа? Или каждое с каждым?

(Reply) (Thread)

Каждое с каждым, конечно.

(Reply) (Parent) (Thread)

define "хэмминговых расстояний" plz

(Reply) (Thread)

См. ниже.

(Reply) (Parent) (Thread)

А хэммингово расстояние между двумя числами - количество бит в XOR-е между ними?

(Reply) (Thread)

Разумеется.

(Reply) (Parent) (Thread)

Для каждого разряда по отдельности посчитать. Подсчитать, сколько в младших разрядах нулей и единиц, перемножить, сдвинуть числа вправо. Повторять для всех разрядов, или пока остались ненулевые числа (не уверен, что из этого эффективнее), накапливая результат.

(Reply) (Thread)

Посчитаем a[i] -- число единиц в i-м бите во всех числах, тогда ответ: b n^2 - sum_i=0..b (a[i]^2 - (n-a[i]^2)), где b -- номер максимального установленного бита.

Видимо, при использовании пирамидальной схемы с битовыми трюками, это можно сделать за O(n+b).

(Reply) (Thread)

Что то типа суммы произведений (суммы в каждом бите x (общее число элементов - сумма в каждом бите))

(Reply) (Thread)

А можно сначала построить дерево?

(Reply) (Thread)

Зачем?

(Reply) (Parent) (Thread) (Expand)

Похоже, что оно связано с предыдущей задачей про минимальное нужное количество бит для сложения :-)

В классическом виде алгоритм подсчета бит, который рассматривает слово как массив N однобитных чисел, делит на два массива по N/2 2-битных чисел, складывает и т.д. использует числовое пространство неэффективно. То есть, например, для 32-битного слова после

a = (a & 0x55555555) + ((a>>1) & 0x55555555)

каждое 2-битное число может хранить значения вплоть до 3, а на самом деле они окажутся не больше 2. Поэтому туда можно добавить еще одну половинку расслоенного числа, которая потом пойдет обрабатываться дальше "забесплатно". Если в процессоре есть достаточно регистров, можно выстроить целую пирамиду таких частичных результатов, которые будут добавляться по мере возможности. Xраниться будут что-нибудь типа 32-битного числа/массива (64 бит не надо, у нас нет столько чисел в массиве, и вообще верхнюю категорию достаточно log2(arraysize)), 16-битного, 8-битного, 4-битного, 2-битного, остающейся второй половинки 2-битного.

Но оптимальный порядок сложения будет запутанным, про него надо подумать отдельно.

(Reply) (Thread)

Нет, не связано. :) И считать сумму установленных бит в слове для решения задачи не нужно.

(Reply) (Parent) (Thread)

O(числа битов данных) устроит? А то ведь и быстрее можно.

(Reply) (Thread)

Интереснее побыстрее, конечно.

(Reply) (Parent) (Thread) (Expand)

Я не очень понимаю, что такое хэммингово расстояние для целых чисел. Оно же для строк.

(Reply) (Thread)

Рассмотри числа как битовые строки.

(Reply) (Parent) (Thread)

А, знаю. use bags

(Reply) (Thread)

Is Hamming distance the edit distance on the bitwise representation of the numbers, or something else?

(Reply) (Thread)

Not the edit distance. :)

(Reply) (Parent) (Thread)

O(N)*M, если все числа не больше 2^M (что на практике константа, так?):

s = 0
for j in [0...M]:
  k = 0
  for i in [0...N]:
    k += numbers[i] % 2
    numbers[i] = numbers[i] // 2
  s += k * (N - k) # <-- число пар 1 и 0 в j-м разряде

Edited at 2016-04-15 07:57 am (UTC)

(Reply) (Thread)

Формально так (и легко можно не модифицировать массив), но интереснее за один проход по массиву.

(Reply) (Parent) (Thread) (Expand)

Я так понимаю, что неотрицательность - это неспроста, да?

(Reply) (Thread)

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

(Reply) (Parent) (Thread)

Похоже что надо использовать свойство XOR: (a^b)^(b^c)=a^c.
В процессе прохождения массива, надо накапливать частичные суммы, а также делать ХOR всех накопленных пар по диагонали.
Вот пример для массива {a,b,c,d}
1. a^b
2. a^b^c, b^c
3. a^b^c^d, b^c^d, c^d

В процессе делаем XOR пар по диагонали
(a^b)^(b^c)=a^c
(a^b^c)^(b^c^d)=a^d
(b^c)^(c^d)=b^d

(Reply) (Thread)

Это получается та же квадратичная сложность. Я раскрыл комменты.

(Reply) (Parent) (Thread)