?

Log in

No account? Create an account
entries friends calendar profile My Website Previous Previous Next Next
Возвращаясь к напечатанному - Уголок Школьника
scolar
scolar
Возвращаясь к напечатанному
Некоторое время назад я написал про одну задачку для интервью. На днях, будучи у меня в гостях, Сашка С. сказал, что можно её усложнить, а именно: предложить найти два числа, встречающихся ровно по одному разу в последовательности, в которой все остальные числа встречаются по два раза. Под питие вина я её решать не стал, а вот сегодня в послеобеденной дрёме решил, и, как мне кажется, решение довольно элегантное, а задачка начинает тянуть на несложную олимпиадную. По крайней мере, на интервью я её давать бы не стал.

Решение, белым по белому:
Итак, будем держать массив из N = 8*sizeof(int) элементов. Далее: один проход по последовательности. Для каждого элемента последовательности цикл по битам: если бит установлен, то XORим число с элементом массива с номером этого бита.

Итак, что после того, как цикл закончен?

Представим себе в наш массив в виде двоичной матрицы N*N, и рассмотрим её побочную большую диагональ (NE-SW). Что означает ноль на этой диагонали? - то, что либо оба числа попали в соответствующий элемент, либо оба не попали. Единица - что одно попало, а второе нет. То есть на этой диагонали XOR наших двух чисел. Далее, поскольку искомые два числа различны, то на этой диагонали найдётся единица. Бинго: идя по этой диагонали сверху вниз, находим первую единицу: в соответствующей строке - одно из чисел. XORим его с числом на диагонали - получаем второе.

Чуть более строго: мы ищем непарные элементы a, b последовательности M. Рассмотрим её подпоследовательности M_i, состоящие из всех элементов M, у которых i-ый бит - единица. Для каждой из таких подпоследовательностей посчитаем x_i = xor(M_i). Это всё делается за один проход.

Теперь найдём минимальное i такое, что (x[i] & (1 << i) != 0) - это, кстати, самая правая единица числа a xor b. Вот мы и нашли множество, в которое входит одно и только одно из чисел a и b. Значит x[i] - одно из этих чисел. Ну а поскольку мы знаем a xor b (оно на побочной диагонали, ну или его тоже считали, проходя по последовательности), то есть и второе.

Пример: пусть у нас целое число 4-битное, и последовательность такова: парные числа 3, 6, 10, 12, непарные 7 и 13.

M_0 = 3, 3, 7, 13
M_1 = 3, 3, 6, 6, 7, 10, 10
M_2 = 6, 6, 7, 12, 12, 13
M_3 = 10, 10, 12, 12, 13

x_0 = 10
x_1 = 7
x_2 = 10
x_3 = 13

1010
0111 - первая единица - тут одно из чисел, в данном случае 7
1010
1101

Ксорим найденное 7 с тем, что на диагонали - получаем 13.

Старик Кантор, поди, в гробу вертится вокруг своей оси диагонали.


Забавная конструкция получилась.
22 comments or Leave a comment
Comments
spamsink From: spamsink Date: August 20th, 2009 12:43 am (UTC) (Link)
В подобных (олимпиадно-интервьюшных) задачах разрешается пользоваться только дополнительной памятью размера O(1). Эта задача решается в два прохода по массиву с использованием пары-тройки рабочих ячеек. Рассказать?
scolar From: scolar Date: August 20th, 2009 12:45 am (UTC) (Link)
У меня, заметим, память O(1) и проход один.
spamsink From: spamsink Date: August 20th, 2009 12:49 am (UTC) (Link)
Неспортивно. sizeof(int) = O(log N). Мое решение работает для целых любого размера.

scolar From: scolar Date: August 20th, 2009 12:55 am (UTC) (Link)
Следуя этой логике, любое решение с памятью, достаточной для хранения целого числа, стоит отбраковывать.

Эта память зависит не от длины последовательности, а от архитектуры процессора - в таких задачах это принимается. Компилятор C статически такой массив разместит - значит, годится.
spamsink From: spamsink Date: August 20th, 2009 12:56 am (UTC) (Link)
Уточню: допустимое в подобных задачах количество памяти в битах - O(sizeof(int)), а у Вас - O(sizeof(int)2).
scolar From: scolar Date: August 20th, 2009 01:03 am (UTC) (Link)
Похоже, не договоримся: во всех случаях, известных мне, требовалось, чтобы размер дополнительной памяти не зависил от размера входной последовательности.

Второй проход представляется мне существенно большим злом.
spamsink From: spamsink Date: August 20th, 2009 01:35 am (UTC) (Link)
В два прохода красивее: сперва найдем X = XOR от двух искомых чисел, а потом пройдем по массиву, обращая внимание только на числа, у которых есть 1 в том бите, где у X младшая единица.
scolar From: scolar Date: August 20th, 2009 01:41 am (UTC) (Link)
Ну да, и оно фактически эквивалентно моему - тот самый поиск первой единицы на побочной диагонали и принцип построения массива.
a_bronx From: a_bronx Date: August 21st, 2009 10:38 pm (UTC) (Link)
В два прохода плохо для потоковых данных. C другой стороны у однопроходного алгоритма есть внутренний цикл длиной sizeof(int), который может оказаться куда большим злом (например, если числа не ограничены, и посему спрямить цикл невозможно).
scolar From: scolar Date: August 20th, 2009 03:27 am (UTC) (Link)
Я там, кстати, поправил решение, а то со вторым числом ошибка вышла изначально. Зато какая забавная конструкция получилась.
a_bronx From: a_bronx Date: August 21st, 2009 11:00 pm (UTC) (Link)
Надо бы ещё поправить "будем держать массив из N = 8 sizeof(int)*sizeof(int) элементов"
a_bronx From: a_bronx Date: August 21st, 2009 11:07 pm (UTC) (Link)
Или лучше "из N2 элементов, где N = sizeof(int)", а то там дальше N используется уже в смысле размера матрицы.
spamsink From: spamsink Date: August 21st, 2009 11:48 pm (UTC) (Link)
8 - это количество бит в байте.
a_bronx From: a_bronx Date: August 21st, 2009 11:51 pm (UTC) (Link)
Зачем нам размер байта, если биты сдвигаем в int-е?
spamsink From: spamsink Date: August 22nd, 2009 12:00 am (UTC) (Link)
sizeof(int) есть размер целого в байтах. Чтобы узнать размер целого в битах, нужно умножить sizeof(int) на 8.
a_bronx From: a_bronx Date: August 22nd, 2009 12:03 am (UTC) (Link)
А, чёрт, ступил :)
a_bronx From: a_bronx Date: August 22nd, 2009 12:06 am (UTC) (Link)
Отбой, я думал про размер _битового_ массива :)
scolar From: scolar Date: August 22nd, 2009 12:35 am (UTC) (Link)
Нет, конечно. Мне нужно по целому на бит.
beldmit From: beldmit Date: August 20th, 2009 05:08 am (UTC) (Link)
Мда. Обидно, но решение выше моего понимания.
scolar From: scolar Date: August 20th, 2009 05:17 am (UTC) (Link)
Я там проапдейтил, как смог.
scolar From: scolar Date: August 20th, 2009 05:39 am (UTC) (Link)
И пример разобрал.
From: a_shen Date: August 21st, 2009 01:06 am (UTC) (Link)

да, я уже про это немного думал

если хотеть сделать за один проход для n-битовых чисел с памятью k битов, то можно пытаться найти k функций на n-битовых словах, которые разделяют пары: если {a,b} не равно {a' b'} то для одной из функций f(a) xor f(b) должно не равнятьс f(a') xor f(b'). Такие функции существуют при k порядка 2n, но надо иметь их явно и ещё быстро выполнять обратное декодирование, чего я не понимаю...

попытаюсь подумать ещё
22 comments or Leave a comment