sim0nsays 26 мар 2016 в 09:58

Задачка про парные числа

2 мин

39K

Алгоритмы*Занимательные задачкиПрограммирование*

114

Комментарии 114

Denxc 26 мар 2016 в 10:17

Скрытый текст

Отсортировать массив.
Далее каждый эл-т сравнить с соседними. Если ни одному не равен, то он искомый.

sim0nsays 26 мар 2016 в 10:23

Видите там в условии — в один проход? Отсортировать массив в один проход нельзя

Denxc 26 мар 2016 в 10:52

В таком случае и ваше тривиальное решение не удовлетворяет условию, так как прохода 2.

sim0nsays 26 мар 2016 в 10:55

Нет, потому что второй проход не по изначальному массиву, а по другому, константного размера. Более конкретно — "в один проход" означает, что элементы входного массива можно прочитать по разу, и только подряд, от первого к последнему

kahi4 26 мар 2016 в 11:24

В таком случае и решение Denxc работает — считываем оригинальный массив только раз, сортируем его в другой (вставками, например), проходим по второму.

Denxc 26 мар 2016 в 11:25

Память не константная нужна для этого.

kahi4 26 мар 2016 в 11:32

Выделяем память размером с исходный массив, сортируем пузырьком (константная память).

Denxc 26 мар 2016 в 11:36

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

extempl 26 мар 2016 в 20:10

Выделяем ВСЮ доступную память — это будет достаточно константно для всех случаев? :)

sim0nsays 26 мар 2016 в 20:26

Смотрим уточнение под катом :)

extempl 26 мар 2016 в 20:28

Да, я вспомнил об этом уже после комментария, но тут речь о том является ли решение Denxc аналогично рабочим вашему из поста.

sim0nsays 26 мар 2016 в 20:42

Понял. В классическом смысле нет — в посте память ограничена 4G для любого размера массива, а если копировать его для сортировки — то нет, может получиться и больше 4G. Т.е. Затраты памяти не константны. Понятием максимального размера обычно не оперируют

Ogra 26 мар 2016 в 11:37

Память размером с исходный массив — это не константная память =)

kahi4 26 мар 2016 в 12:59

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

Ogra 26 мар 2016 в 18:11

Представьте, что у вас железка с 4Кб оперативки, а данные приходят по сети. Дополнительной памяти нет, возможности второго прохода нет.

BelBES 26 мар 2016 в 15:11

Числа надо полагать целые (иначе как проверять на равенство 2 флота), тогда заводим один массив размером с диапазон 32-битных чисел, за один проход по исходному массиву строим гистограмму, а за второй проход по вспомогательному массиву находим в гистограмме 2 бина со значением 1 :-)

gecube 26 мар 2016 в 16:25

Это решение констатно по памяти, но массив unsigned char [2^32] для гистограммы в 4KB RAM не влезет.
Скажем так — так можно сделать в случае, если N оооооооочень большое.

BelBES 26 мар 2016 в 16:51

В задании я вижу только требование того, что объем дополнительной памяти должен быть константным, это условие выполняется)
Откуда взялись 4KB RAM — мне не понятно, вон у МТ вообще бесконечная лента памяти;)

Mrrl 26 мар 2016 в 18:12

Давайте, чтобы не было разночтений — памяти у вас четыре килобайта.

lgorSL 26 мар 2016 в 11:07

Есть идея, но до решения не получилось довести (а может, и нельзя так).

Скрытый текст

Сделать xor всех элементов массива друг с другом, получим xor различающихся чисел. Я пытался придумать ещё одну операцию, чтобы получить больше информации, и её основе восстановить эти два числа, но в голову ничего не пришло.

acerikfy 26 мар 2016 в 11:14

У меня была такая же идея, но как получить такую информацию — сложный вопрос
Скорее всего подход другой должен быть

sim0nsays 26 мар 2016 в 11:15

Да, нужна какая-то еще идея :)

Ogra 26 мар 2016 в 11:26

Должно получиться

Пусть массив называется N.
Создаем массив из 32 32-битных чисел. uint32_t A[32];
Проходим по массиву N:

Если в числе N[i] установлен бит j, xor-им N[i] с A[j].

Проходим по массиву A — некоторые из чисел будут нулями, два оставшихся — искомые числа.

Ogra 26 мар 2016 в 11:31

Правка

В массиве A будут либо нули (у числа 1 и у числа 2 на этой позиции 0), либо число 1 ( у числа 1 на этой позиции 1, а у числа 2 на этой позиции 0), либо число 2(аналогично), либо число 1 xor число 2. (у обоих единица) Поскольку, чтобы вычислить число 1 xor число 2 достаточно пройтись xor по всему массиву, задача решена =)

lgorSL 26 мар 2016 в 11:37

Есть один нюанс.

Скрытый текст

Возможно, останется только одно число. Но это уже не страшно, можно ещё при проходе по массиву поксорить всё, и тогда второе число будет легко получить.
P.S> Не обновил комментарии перед отправкой(

sim0nsays 26 мар 2016 в 11:37

Кажется, вот контрпример

Это 4 трехбитных числа:
1 1 0 0
0 0 0 1
1 1 0 1

Ogra 26 мар 2016 в 11:42

Второй комментарий важен, без него не работает, конечно же.

sim0nsays 26 мар 2016 в 11:47

Можно тогда более подробно описать, что происходит с A после прохода по массиву?

Ogra 26 мар 2016 в 11:59

Скрытый текст

Пусть X, Y — искомые числа.
X_j == Y_j == 0 -> A[j] == 0
X_j == 0, Y_j == 1 -> A[j] == Y
X_j == 1, Y_j == 0 -> A[j] == X
X_j == 1, Y_j == 1 -> A[j] == X xor Y

sim0nsays 26 мар 2016 в 21:26

Скрытый текст

и мол кроме A считаем xor всего, чтобы сравнивать со значениями в A, чтобы понять кто есть кто?

Ogra 27 мар 2016 в 05:48

Скрытый текст

Да, считаем xor всего. Сравнением со значениями в А можно найти как минимум одно из заданных чисел (если они различаются лишь в одном бите), ну а при наличии одного числа и xor двух искомых чисел можно легко вычислить второе.

sim0nsays 27 мар 2016 в 07:59

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

Ogra 27 мар 2016 в 18:20

Полный алгоритм

Пусть массив называется N, искомые числа — X и Y. N[i] — i-й элемент в массиве N, X_j — j-й бит в числе X.
Создаем массив из n n-битных чисел. e.g. uint32_t A[32], обнуляем его;
Создаем переменную NXored, обнуляем.
Проходим по массиву N:

Если в числе N[i] установлен бит j, xor-им N[i] с A[j].
В любом случае xor-им N[i] с NXored

После прохождения цикла, NXored будет содержать X xor Y, а массив А будет содержать не больше четырех уникальных чисел: ноль, X, Y, и X xor Y:
X_j == Y_j == 0 -> A[j] == 0
X_j == 0, Y_j == 1 -> A[j] == Y
X_j == 1, Y_j == 0 -> A[j] == X
X_j == 1, Y_j == 1 -> A[j] == X xor Y
Поскольку числа X и Y различны, то как минимум в одном бите у них будут различия, значит в массиве А точно содержится одно из искомых чисел. Проходим по массиву А, ищем значение отличное от нуля и от NXored — пусть это будет X. После этого легко вычисляется второе искомое число: Y = X xor NXored.
Пример для 8-битных чисел на языке С: http://ideone.com/zHSWiT.
P.S. Памяти потребуется n² бит для массива, n бит для NXored, 2n для сохранения результата (хотя тут можно и сэкономить). Всего n (n + 3) бит. Решая простенькое квадратное уравнение, получаем, что имея 4 Кб памяти, можно оперировать 179-битными числами :)

ZyXI 27 мар 2016 в 19:17

Скрытый текст

У вас здесь использование неопределённого значения. Если одно из «уникальных» чисел 0, то ваш код выведет мусор, X и Y нужно проинициализировать как 0 и NXored. А сам алгоритм несколько лучше, я и ещё несколько людей использовали 64 или 65 накопителей.

Ogra 27 мар 2016 в 19:32

Заголовок спойлера

Да, действительно, спасибо за замечание ;)

Evsign 26 мар 2016 в 20:02

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

Ogra 27 мар 2016 в 08:10

Держите! http://ideone.com/zHSWiT

Evsign 27 мар 2016 в 10:25

Спасибо!

Mrrl 26 мар 2016 в 11:40

https://habrahabr.ru/post/243819/, задача 5?

sim0nsays 26 мар 2016 в 11:55

Ага, действительно. В моем посте — ее более краткая версия

VaalKIA 26 мар 2016 в 16:57

А мне, кажется — нет. Тут же нет никакого порядка, там числа строго упорядоченны и их попарно вычитают, тут просто два отличаются.

kmu1990 26 мар 2016 в 11:42

Идея

Считаем xor по группам, т. е. xor всех чисел, у которых установлен 1-ый бит, xor всех чисел, у которых установлен 2-ой бит, и так далее. Кроме того считаем xor всех чисел вообще. Далее в xor-е всех чисел ищем установленный бит, берем xor группы чисел, в которых установлен этот бит, он будет равен одному из неизвестных чисел, а второе найти не трудно.
Почему? Потому что, если в xor-е всех чисел на k-ой позиции стоит 1, то значит наши неизвестные числа в этой позиции отличаются, а значит одно из них попадет в группу, а второе нет.

sim0nsays 26 мар 2016 в 11:49

Отлично!

gecube 26 мар 2016 в 13:57

гениально!

VaalKIA 27 мар 2016 в 03:43

Реализация на Lazarus/Delphi

OlegMax 28 мар 2016 в 15:26

Если вы пролистали до этого комментария, то, возможно, вы уже сдались. Тогда попробуйте еще подумать вот с этой подсказкой:

Небольшая подсказка в правильном направлении

XORим вместе все числа с нечетными значениями и, отдельно, XORим вместе все числа с четными значениями.
Дальше сами...

Randl 26 мар 2016 в 11:58

Идея, возможно отношения к решению не имеет

Если про XOR'ить все числа, получим A XOR B, где A и B — наши числа. А как их получить — пока не знаю

НЛО прилетело и опубликовало эту надпись здесь

WowaBBS 26 мар 2016 в 16:26

Скрытый текст

Решение не будет слишком отличаться от оригинального, вместо сложения по модулю два (xor), нужно будет использовать сложение по модулю три. И реализовать тритичный регистр.

НЛО прилетело и опубликовало эту надпись здесь

WowaBBS 26 мар 2016 в 22:24

Тут самая сложная задача, если в общей сумме не будет ни одной единицы. Например:

WowaBBS 26 мар 2016 в 22:32

Входные числа:
10
01
11
Суммы по битам
1 21
2 12
Общая сумма
22
Если не будет ни одной единицы, и число двоек будет больше двух, то точного решения нельзя получить.

WowaBBS 26 мар 2016 в 22:58

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

НЛО прилетело и опубликовало эту надпись здесь

sim0nsays 27 мар 2016 в 08:00

В комментах видны все уровни, от "что это вообще такое", до "слишком просто". Спасибо за расширение задачи

Zealint 26 мар 2016 в 12:40

Действительно, задача слишком известная, чтобы считаться задачкой на выходные, она требует понимания классических приёмов программирования (по крайней мере, в сфере разработки алгоритмов), а кто занимался олимпиадами, просто скорее всего заранее знает решение или его идею.
Я всего лишь хочу порекомендовать автору более надёжно защищаться от троллей в подобных задачах. Например, можно было написать, что время работы алгоритма должно быть O(N), тогда не было бы мыслей о сортировках. Объём памяти можно было бы ограничить ещё сильнее (выше изложено одно из правильных решений, там чётко ясно, сколько будет памяти).
Здесь ещё можно попридираться к формулировке в том, что число N вообще говоря ограничено сверху, так как всего 2³² разных чисел и если каждое встречается максимум 2 раза, то ясно, что вообще говоря задача может быть решена за константное время :) Было бы лучше сказать, что каждое число встречается чётное число раз, а два из них — нечётное. Тогда N уже точно не ограничено ничем.
Ну и, возможно, имело бы смысл давать задачи, которые действительно мало известны. Но это имхо.

sim0nsays 26 мар 2016 в 19:51

"На выходные" — имелось ввиду, что можно подумать в бэкграунде, пока занимаешься другими делами, а код писать особо не нужно.
Под катом было более четкое ограничение — памяти всего 4K (и даже разбор тривиального "решения") Похоже уточнения под катом никто не читает, буду знать.

Zealint 26 мар 2016 в 22:05

Нет, почему же, я внимательно прочитал задачу с пояснениями и решил сказать, что можно было бы сделать ограничение на память более точным (я же так и написал "ограничить ещё сильнее"). Я всего лишь внёс ряд предложений по улучшению подобных задач, не более того. Просто у меня есть опыт постановки задач таким образом, чтобы никакой троллинг в принципе был невозможен. Давать подобные задачи — вполне хорошая затея, особенно когда они будут не из классики олимпиадного программирования. Поддерживаю.

sim0nsays 27 мар 2016 в 04:45

Я плохо знаком с классикой олимпиад, мой критерий был — чтобы инсайт не требовал специальных знаний и очень просто писался код. Опять же, верю что задачке сто лет в обед, просто запостили ее недавно и я ее раньше не видел.
Если вы еще таких знаете — рассказывайте обязательно!

gecube 26 мар 2016 в 13:52

Заголовок спойлера

если бы задача формулировалась по-другому, а именно был бы массив из N чисел, среди которых все парные, а есть непарное, то можно было бы пробежаться по массиву XOR'я каждый следующий элемент. На выходе имеем искомое число.
В данном случае я смогу получить только XOR-сумму этих чисел. Затраты памяти константные. Дальше пока не додумал.

VaalKIA 26 мар 2016 в 16:42

Если просто поксорить, то не очень понятно будет что мы получим, по идее надо подсчтитать каждый бит, тогда нечётные числа — это те биты, которые принадлежат непарным числам, однако даже у непарных чисел могли какие-то биты совпасть и надо определить — какие. То есть надо сделать какую-то зависимость остальных бит в числе от уникальных, ну типа CRC, например инвертировать все биты в зависимости от N-го получим не 32 суммы, а 33*32 суммы и сможем восстановить все биты. Наверняка это всё можно сделать гораздо проще.

sim0nsays 26 мар 2016 в 20:28

Ничего не понял :) можно как-то конкретнее, что предлагается? Какой конкретно CRC, как потом узнавать биты?

VaalKIA 27 мар 2016 в 00:20

С инверсией я погорячился, она не подходит, поскольку хоть число и не парное, но нам важны совпадающие биты, а они, как раз будут парные в любом случае. Насчёт CRC это только идея, существует полно всяких видов корректирующих кодов.
Основная идея была в том, что если показать зависимость бит, то по этой зависимости можно восстановить сами биты. Но я не учёл, что мы в любом случае не получаем абсолютные значения, а получаем или/или, то есть и сами корректирующие коды хоть и будут отличными для этих двух чисел, но сумма по модулю будет 11111 в идеальном случае, а самих кодов мы не получим.
Фактически должно было быть так: есть число A, есть какое-то преобразование, зависящее от значения самого числа A->A', значение сложения для парных не изменится, для непарных A+A mod 2 и A'+A' mod 2 будут различны, можно попытаться восстановить отсюда биты. Например, пусть это будет циклический сдвиг если первый бит равен 1це:
два непарных числа:
101
001
суммы по модулю чисел и их сдвига:
100 и 111
второе число отражает зависимость бит внутри числа, а первое зависимость бит одного непарного от второго. Можно составить систему уравнений. В общем. над придумать такое преобразование. что бы в итоге можно было получить простую зависимость с однозначным решением.

VaalKIA 27 мар 2016 в 02:25

Кстати выше уже привели решение: парные числа нас не интересуют, они при xor ни на что не влияют, а все числа можно разделить на две группы: у которых установлен какой-то бит и на те у кого этот же бит сброшен, парные так и останутся парными — каждая пара в свою группу, а непарные по любому, отличному биту попадут в разные группы, xor в этой группе уже даст это число, поскольку оно там одно.

Вот код (делал побыстрому) для Lazarus, но он у меня работает неверно, откуда-то берётся третье число в xor'ах

const
  Count = 50;

type
  MasTyp = array [1..Count + 2] of byte;

procedure Init(var mas: MasTyp);
var
  alone, i: byte;
  flag: boolean;
begin
  Randomize;
  for i := 1 to Count div 2 do
  begin
    mas[i] := Random(256);
    mas[Count - i + 1] := mas[i];
  end;
  mas[Count + 1] := 0;
  mas[Count + 2] := 0;

  flag := True;
  while flag do
  begin
    alone := Random(256);
    for i := 1 to Count div 2 do
    begin
      if mas[i] = alone then
        break;
    end;
    if i = (Count div 2) then//зависит от компилятора
    begin
      flag := False;
      mas[Count + 1] := alone;
    end;
  end;

  flag := True;
  while flag do
  begin
    alone := Random(256);
    for i := 1 to Count div 2 do
    begin
      if mas[i] = alone then
        break;
    end;
    if i = (Count div 2) then//зависит от компилятора
    begin
      flag := False;
      mas[Count + 2] := alone;
    end;
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  mas: MasTyp;
  i, n, bit, value1, value2: byte;
  xor_bit, xor_byte_of_bit: array [1..8] of byte;
begin
  Init(mas);

  Form1.Memo1.Lines.Text := '';
  for i := 1 to Count + 2 do
    Form1.Memo1.Lines.Text := Form1.Memo1.Lines.Text + (IntToStr(Mas[i]) + ' ');

  for i := 1 to High(xor_bit) do
  begin
    xor_bit[i] := 0;
    xor_byte_of_bit[i] := 0;
  end;

  //Основной цикл---------------------------------------------------------------
  for i := 1 to Count + 2 do
  begin
    for n := 1 to 8 do
    begin
      bit := Ord((mas[i] and (1 shl (n - 1))) > 0);
      xor_bit[n] := xor_bit[n] xor bit;
      if bit = 1 then
        xor_byte_of_bit[n] := xor_byte_of_bit[n] xor mas[i];
    end;
  end;
  //Основной цикл---------------------------------------------------------------

  Form1.Memo1.Append('value1 ' + BinStr(mas[Count + 1], 8));
  Form1.Memo1.Append('value2 ' + BinStr(mas[Count + 2], 8));

  Form1.Memo1.Append('Xor бит');
  for i := High(xor_bit) downto 1 do
  begin
    Form1.Memo1.Lines.Text := Form1.Memo1.Lines.Text + (IntToStr(xor_bit[i]) + ' ');
  end;

  Form1.Memo1.Append('Xor по группам бит');
  for i := High(xor_byte_of_bit) downto 1 do
  begin
    Form1.Memo1.Lines.Text := Form1.Memo1.Lines.Text +
      (IntToStr(xor_byte_of_bit[i]) + ' ');
    if (i - 1) mod 8 = 0 then
      Form1.Memo1.Lines.Text := Form1.Memo1.Lines.Text + ' ';
  end;

  //Поиск в группах
  value1 := 0;
  value2 := 0;
  for i := 1 to 8 do
  begin
    if xor_bit[i] = 1 then
    begin
      if value1 = 0 then
        value1 := i;
      if xor_byte_of_bit[value1] <> xor_byte_of_bit[i] then
      begin
        value2 := i;
        break;
      end;
    end;
  end;
  Form1.Memo1.Append('value1 ' + IntToStr(xor_byte_of_bit[value1]));
  Form1.Memo1.Append('value2 ' + IntToStr(xor_byte_of_bit[value2]));
end;

Вывод (сначала массив, а искомые числа всегда последние два)

73 126 189 4 215 110 8 156 149 76 37 4 211 167 108 208 35 251 221 50 104 67 135 220 178 178 220 135 67 104 50 221 251 35 208 108 167 211 4 37 76 149 156 8 110 215 4 189 126 73 180 6
value1 10110100
value2 00000110
Xor бит
1 0 1 1 0 0 1 0
Xor по группам бит
180 0 180 180 0 178 6 0
value1 6
value2 180

VaalKIA 27 мар 2016 в 03:26

Нашёл ошибку, второе число нельзя искать среди групп, его надо вычислять ксоря найденное первое с общим ксором. 178 тут верно, это они оба попали в одну группу, но алгоритм это учитывает, а программа не учитывает вот что: если числа отличаются в одном бите. то они никак оба не будут выведенны, потому что мы не делаем xor по нулю, а только по еденице и в единственной отличающейся группе у второго ноль.

измения в код

 xor_full := 0;
  //Основной цикл---------------------------------------------------------------
  for i := 1 to Count + 2 do
  begin
    xor_full := xor_full xor mas[i];

...

 //Поиск в группах
  value1 := 0;
  value2 := 0;
  for i := 1 to 8 do
  begin
    if xor_bit[i] = 1 then
    begin
        value1 := xor_byte_of_bit[i];
        value2 := xor_full xor value1;
        break;
    end;
  end;
  Form1.Memo1.Append('value1 ' + IntToStr(value1));
  Form1.Memo1.Append('value2 ' + IntToStr(value2));

rPman 26 мар 2016 в 20:55

Самое тупое и простое решение, не эффективное O(n^2)

текущий минмум = 0 (точнее минимально возможное число, способное быть записано в 32бита, т.е. для чисел со знаком это -2,147,483,648)
цикл в (размер массива/2) итераций
{
текущее количество = 0
для каждого элемента массива
{
ищем количество чисел равных текущему минимуму (если элемент равен текущему минимуму то увеличиваем количество)
ищем следующий минимум (число больше текущего минимума и меньше или равно текущему элементу)
}
если количество чисел было больше 1 то выводим текущий минимум
}

rPman 26 мар 2016 в 21:07

Черт, ошибку нашел у себя:

размер внешнего цикла нужно исправить на деление с округлением в большую сторону +1 или просто тупо +2, иначе для случая когда искомые числа максимальные для массива — они не будут найдены)
либо цикл бесконечный и выходим, когда не сможем найти следующий минимум (но тогда будет доп условие)

mgrigorov_ua 26 мар 2016 в 21:34

Такие задачи у меня всегда вызывают чувство ущербности…
И вроде программистом себя считаешь и вроде на работу ходишь каждый день, а всё равно, никуда не заглядывая, решить не можешь.
Да чего там… подглядывая в спойлеры, мало чего понял :(
Жду решения с детальным разжевыванием!
Спасибо.

sim0nsays 26 мар 2016 в 21:35

Ну, в реальной работе (к сожалению) такое нужно крайне немногим и крайне редко. Для меня это скорее радостная возможность вспомнить молодость и размять мозги.

НЛО прилетело и опубликовало эту надпись здесь

gecube 27 мар 2016 в 02:29

А ее и ненужно разбирать. Код на XOR реально эффективный будет, а map — медленный отстой (в этом случае). Читаемость заменяется комментариями, а код обрамляется в функцию (типа черный ящик).

НЛО прилетело и опубликовало эту надпись здесь

sim0nsays 27 мар 2016 в 04:47

Ну, шанс что выпадет именно такая задача вообще бесконечно мал, слишком уж искусственно. А вот шанс использовать битовую магию, про которую задача — почему нет.
Прием с xor указателей в списке вполне рабочий, к примеру.
Разумеется, если память и/или производительность неважна — лучше писать проще.

Demogor 27 мар 2016 в 02:53

Легкий сарказм

Вариабельное решение на js:

var r={};
var a=[1,1,2,5,7,7,11,12,11,12];
a.forEach((x)=>{
  if(!r[x])
    r[x]=1;
  else
    delete r[x];
});

Если повезет — то дубляжи будут попадаться достаточно часто и размер объекта r будет скакать в пределах 4к. Превысило? Ну что ж, не повезло.

sim0nsays 27 мар 2016 в 04:49

ыыыыыыыы! И надеемся, что у первых кастомеров объемы маленькие, а там глядишь до следующего раунда инвестиций дотянем!

Demogor 27 мар 2016 в 10:52

Нормальная русская рулетка: отвалится/не отвалится в момент сдачи.

govnokoder 27 мар 2016 в 05:05

Искомые числа: X1 и X2
Кол-во элементов: CA
Считаем сумму всех чисел (SA), XOR всех чисел (XA)
Получаем: SA = 2a + 2b + 2c +… + X1 +… + X2 +…
XA = X1 ^ X2
Перебираем первое число от 0 до 0xfffffff так, чтобы выполнялось равенство: (SA + X1 + (X1 ^ XA)) / CA — целое

sim0nsays 27 мар 2016 в 05:06

ааааа, термояд! Пишите под спойлером плз.

Кажется, контрпример

Два двухбитовых числа:
1 1 и 1 0

Demogor 30 мар 2016 в 07:36

Если я не ошибаюсь, это будет не 1 проход, а 3(сумма, xor, перебор)?

ZyXI 27 мар 2016 в 05:23

Решение

Решение простое: заводим 65 «аккумуляторов»: в нулевой xor’ятся абсолютно все числа массива по мере прохода по нему. Т.к. a^a=0, a^b=b^a, a^0=a, a^(b^c)=(a^b)^c, то в аккумуляторе в результате оказывается а0=u1^u2, где u1 и u2 — искомые уникальные числа. Получив u1^u2 нужно как‐то это разделить на u1 и u2, для этого используем то, что u1≠u2 (свойство уникальности). Т.к. u1≠u2, то хотя бы один бит в u1 отличен от u2, поэтому оставшиеся 64 аккумулятора используются так: в n’й аккумулятор (n=1..64) xor’ятся числа, (n//2)‐й бит которых равен (n%2) (// — целочисленное деление). Таким образом образуются 32 группы по два аккумулятора: в первой группе 1‐й и 2‐й, во второй 3‐й и 4‐й, … Из‐за того, что существует хотя бы один бит, отличный от u1 и u2, существует такая группа аккумуляторов, что u1 учавствовал в определении значения одного аккумулятора, в определении значения которого не учавствовал u2. В такой группе один из аккумуляторов равен u1, а другой u2. В группах, где u1 и u2 имеют совпадающий бит один из аккумуляторов 0, а другой — u1^u2. Если u1 или u2 равен 0, то все группы будут иметь одинаковые пары значений.
Код на Python:

#!/usr/bin/python3.4

import random

from functools import partial

from numpy.random import random_integers, shuffle
from numpy import array, uint32, unique, array_equal

def create_test_array(randsize=10000):
    random_uints32 = partial(random_integers, 0, 2 ** 32 - 1)

    doubles = unique(random_uints32(size=randsize))

    u1 = next(iter(doubles))
    while u1 in doubles:
        u1 = random_uints32()

    u2 = next(iter(doubles))
    while u2 in doubles:
        u2 = random_uints32()

    arr = array(doubles, dtype=uint32)
    arr.resize([len(doubles) * 2 + 2])
    arr[len(doubles):len(doubles) * 2] = doubles
    arr[-2] = u1
    arr[-1] = u2
    shuffle(arr)
    return u1, u2, arr

def find_uniques(arr):
    acc0 = uint32(0)
    accs = array([[acc0] * 2] * 32)
    masks = array([uint32(1 << i) for i in range(32)])

    for val in arr:
        acc0 = acc0 ^ val
        for bitidx, subaccs in enumerate(accs):
            subaccs[int(bool(val & masks[bitidx]))] ^= val

    p1 = array([acc0, uint32(0)])
    p2 = array([uint32(0), acc0])

    for subaccs in accs:
        if array_equal(subaccs, p1) or array_equal(subaccs, p2):
            continue
        return subaccs

    return p1

def main():
    u1, u2, arr = create_test_array()
    fu1, fu2 = find_uniques(arr)
    print('expected: ', sorted([u1, u2]))
    print('found   : ', sorted([fu1, fu2]))

if __name__ == '__main__':
    main()

PS: комментарии пока не читал.

sim0nsays 27 мар 2016 в 05:25

Все так!

ZyXI 27 мар 2016 в 05:37

Уточнение

Я тут после прочтения комментариев понял, что вообще‐то acc0 не нужен: в группах всегда будет либо (0, u1^u2), либо (u1, u2). Т.е. можно забить на acc0 и возвращать первую пару, где оба аккумулятора не нули. А если таких нет, то вернуть самую первую пару: это вариант, когда u1 или u2 0. Эта переменная вообще появилась из‐за того, что первым соображением было «если всё xor’ить, получим u1^u2; теперь думаем, как получить отсюда u1 и u2». В комментариях некоторые люди здесь и застряли.

def find_uniques(arr):
    accs = array([[uint32(0)] * 2] * 32)
    masks = array([uint32(1 << i) for i in range(32)])

    for val in arr:
        for mask, subaccs in zip(masks, accs):
            subaccs[int(bool(val & mask))] ^= val

    for subaccs in accs:
        if subaccs[0] != 0 and subaccs[1] != 0:
            return subaccs

    return accs[0]

vasiatka 27 мар 2016 в 08:59

оставю тут. сложность O(n). память O(1). guildalfa.ru/alsha/node/29

savinov_ao 27 мар 2016 в 19:17

Напишу всё же свое предположение, хотя оно не укладывается в более жесткие требования предложенные Zealint.

Берем первые 10 простых чисел P={2, 3, 5, 7, 11, 13, 17, 19, 23, 29}. Их сумма 129. Выделяем bool d[129]; Реализуем функцию Mods(x), которая возвращает массив из 10 чисел: i-e число равно (x % P[i]) + сумма P[0..i-1].
Для всех элементов i=1..N

M=Mods(a[i]). Инвертируем d[M[j]] для j=0..9
Считаем xy ^= a[i]

Затем для x=0..2³²-1 вычисляем y = xy ^ x и проверяем что xor массивов Mods(x) и Mods(y) совпадает с d. Если совпадает, выходим по break.
Наверное так.

ankh1989 28 мар 2016 в 10:24

Можно например сначала сложить все числа в конечном поле, затем сложить квадраты этих чисел. В итоге пары сократятся и получится два уравнения: сумма двух числе и сумма их квадратов. Уравнения эти сводятся к выичслению квадратного корня в конечном поле, что можно сделать алгоритмом Шенкса. Проще конечно xor-ом, но если хочется загрузить того кто собеседование проводит, то конечные поля Галуа — самое то.

sim0nsays 28 мар 2016 в 10:27

ооооо! В конченом поле — это как? По модулю? И почему пары сократятся?

halyavin 29 мар 2016 в 09:20

Квадраты бесполезны, поскольку x²+y²=(x+y)² — мы не получаем новой информации. Нужно

Решение

использовать кубы. x³+y³=(x+y)(x²+xy+y²). Таким образом мы узнаем x²+xy+y². Как мы видели выше, сумму квадратов мы уже знаем. Вычитая ее, получаем xy. Остается решить квадратное уравнение и найти x и y. Это единственное (из предложенных в комментариях) правильное решение задачи, поскольку 32 аккумулятора — это не O(1), а O(w), где w — размер машинного слова.

sim0nsays 29 мар 2016 в 09:36

Так поясните, что подразумевается под сложениями и умножениями, и как сокращаются пары других чисел?

halyavin 29 мар 2016 в 21:08

Сложение — xor. Умножение выполняется сложнее. Вначале нужно выполнить битовое умножение без переносов, а потом посчитать CRC. Еще материал по этой теме: https://habrahabr.ru/post/212095/

ankh1989 30 мар 2016 в 09:07

Практически это делается так:
shl = x => x = x << 1 ^ (x < 0? 0x8d: 0); // x * 2 + 2**32 + 0x8d
mul = (a, b) => b && ((b & 1? a: 0) ^ shl(mul(a, b >>> 1)));
А потом применяем вот так:
mul(0x6789, 0x9876);

Zealint 29 мар 2016 в 10:30

Скрытый текст

Размер исходных чисел строго ограничен константой — 32 бита. Далее, размер входного потока по условиям задачи тоже строго ограничен (максимум, у нас два раза каждое число встречается), поэтому, строго говоря, тут любое решение будет константным как по времени, так и по памяти. Если же отбросить троллинг и сделать вид, что задача поставлена правильно, то завести 32 аккумулятора будет вполне законным решением. Ваше решение разве не зависит от размера слова? Так ли это?

Mrrl 29 мар 2016 в 11:09

Ваше решение разве не зависит от размера слова?

Зависит — примерно как 3*N бит. А решение со счётчиками — примерно N^2 бит. Конечно, ограничения задачи становятся слегка другими, но O(N)<O(N^2).

Zealint 29 мар 2016 в 13:17

При чём тут O(N^2)? В решении с 32-мя счётчиками будет один проход по циклу. Имеем те же O(N) битовых операций и O(1) памяти, в виде 32-х чисел размером 32 бита. Ну, плюс пара служебных переменных.

Mrrl 29 мар 2016 в 13:35

А в случае 16384-битных слов? Всё равно 32 счётчика?
Правда, я не уверен, что решение с x^3 вообще работает.

Zealint 29 мар 2016 в 13:58

Я же напомнил выше, что в задаче чётко указан размер слова — 32 бита. В случае K-битных слов по любому решение будет зависеть от K, хотя бы потому, что нужно как-то это слово считать в память, тут не важно, делаем мы xor или сумму в конечных полях. И всё равно я не вижу тут O(N^2).

ZyXI 29 мар 2016 в 14:00

Судя по сообщению Mrrl под N имел ввиду разрядность числа, а не то, что указано в условии. Т.е. если считать разрядность числа в задаче переменной и равной b, то будет O(Nb) битовых операций и O(b²) памяти в случае с b счётчиками и O(b) памяти для его предложения.
Чтобы не возникало недопонимания не нужно переназначать переменные из условия.

Zealint 29 мар 2016 в 14:09

Даже если так, то это уже обсуждение другой задачи. А в этой задаче размер слова чётко обозначен, и это с практической точки зрения даёт надежду на вполне эффективный алгоритм. Менять условия или пытаться решить более общую задачу вместо исходной — это не всегда хорошая идея. А в случае жёстких требований на время работы даже плохая. Не вижу также смысла пытаться ставить в качестве аргумента теоретическое время работы через символ "O" (который обозначает время для b->oo), которое никакого отношения к реальности обычно не имеет, особенно при малых значениях этого b.

halyavin 29 мар 2016 в 21:04

Очевидно, что подразумевается, что размер чисел равен машинному слову. Я не вижу другого разумного способа формализовать задачу. В стандартной модели вычислений, операции над машинными словами выполняются за O(1) и одно машинное слово занимает O(1) памяти.

Zealint 29 мар 2016 в 21:24

Ну так и я тоже не вижу никаких теоретических отличий между Вашими переменными "x" и "y" в конечном поле (по какому-то модулю, явно зависящему от размера слова), и набором переменных из решения с xor, размер которых будет в точности совпадать с размером слова, потому что размер слова не стремится к бесконечности и потому что в условиях задачи (некорректно поставленной) указано, что память не должна зависеть от размера массива, а будет ли она квадратичной или линейной по числу бит в слове, не важно. Что же касается практической эффективности обоих решений, то это тоже большой вопрос, что будет быстрее — 32 xor'a или вычисления кубов по модулю. Хотя я, конечно, не буду спорить о том, что любые правильные методы сами по себе заслуживают внимания и каждый из них по-своему хорош.

halyavin 29 мар 2016 в 22:38

Чтобы N стремился к бесконечности, битность чисел тоже должна стремиться к бесконечности. Даже в варианте где разрешены повторения парных чисел, очень странно указать 32 бита и не подразумевать, что числа имеют размер машинного слова. Тогда уж надо указывать 30 бит или 50 бит (компьютеры давно уже 64-битные, а это самое круглое число меньше 64).
Некорректно поставленная задача означает лишь то, что ее нужно преобразовать в корректно поставленную наиболее естественным способом, используя общепринятые умолчания. После чего решить. При объяснении решения, в зависимости от обратной реакции вопрошающего, возможно преобразовать решение обратно. Подход требующий 32 слова в памяти не является решением получившейся корректно поставленной задачи, значит это не правильное решение. Если бы оно подразумевалось, нужно было бы писать в условии не O(1) памяти, а O(32) памяти. Ну или сразу писать корректную формулировку с переменной длиной машинного слова.
PS Конечное поле тут не по модулю простого числа. Поле должно иметь характеристику 2, чтобы парные числа сокращались.

astowork 28 мар 2016 в 18:27

Задачке лет 5… это классика…
Скрытый текстtype
TMyElement= integer;
PMyElement= ^TMyElement;
TMyArray= array of TMyElement;
TBitInfo= record
Mask: TMyElement;
Sum: TMyElement;
end;

const
BitCount = SizeOf(TMyElement)*8;
LastBitNo= BitCount-1;
//поиск 0..2 непарных среди Count элементов массива, начиная с p
procedure Find012(p: PMyElement; Count: integer; var Res: TMyArray);
var
bi: array[0..LastBitNo] of TBitInfo;
t: TMyElement;
q: PMyElement;
i: integer;
begin;
if (p=nil) or (CountLastBitNo;
end;
end;
end;
end;

pitrpg 28 мар 2016 в 18:28

Вроде рабочий вариант решения, но с некоторыми ограничениями jsfiddle.net/669a3L45

psplus2016 28 мар 2016 в 18:31

Элементарно.
Int main()
{
vector v = {1,2,3,3,1,2,4,7};
//vector v = {1,2,7,4,1,2,3,3};
//vector v = {1,2,3,4,1,2,3,7};
int p = 0;
int s = 0;
int pp = 0;
int ss = 0;
for( size_t i = 0; i < v.size(); i++ )
{
if( i < (v.size() / 2) )
p = p ^ v[i];
else
s = s ^ v[i];

if( (i%2) == 0 )
pp = pp ^ v[i];
else
ss = ss ^ v[i];
}

if( (p^pp) == p || (s^ss) == s )
{
cout

psplus2016 29 мар 2016 в 00:09

нифига не работает :) неверная тестовая последовательность была — привела к ложному "верному" результату.

venco 28 мар 2016 в 19:56

Моя попытка#include

int main()
{
unsigned bit[32] = {}, all = 0, v, i;
while ( std::cin >> v ) {
all ^= v;
for ( i = 0; i < 32; ++i ) {
if ( v&(1

venco 29 мар 2016 в 01:26

Мда, тэги не прошли. И редактировать не могу.
В общем, посмотрел другие решения, и эта идея уже была приведена несколько раз. Памяти требуется на 32-е xor суммы.

ZyXI 29 мар 2016 в 01:38

На 33. Плюс ещё куча вещей вроде памяти под исполняемый код и временные переменные вроде i и v, которые есть, но на которые всем (включая меня) при подсчёте памяти было наплевать.

venco 29 мар 2016 в 01:56

Ок, памяти требуется O(B^2) бит, где B-размер чисел в битах, остальное — меньшего порядка.
А ещё общий xor можно собрать из побитовых xor-ов по диагонали.

nikitadanilov 29 мар 2016 в 16:04

Проще, наверное, показать код, чем описать:

Скрытый текст

static void findunique(int nr, uint32_t *a)
{
    uint32_t s[32][2] = {};
    int      i;
    int      j;
    for (i = 0; i < nr; ++i)
        for (j = 0; j < 32; ++j)
            s[j][!!(a[i] & (1 << j))] ^= a[i];
    for (j = 0; j < 32; ++j)
        if (s[j][0] != 0 && s[j][1] != 0)
            printf("%u %u\n", s[j][0], s[j][1]);
}

nikitadanilov 29 мар 2016 в 16:24

Update: все-таки опишу.
Для каждого номера бита i, от 0 до 31, найдем сумму всех элементов массива, у которых i-й бит установлен (s[i][1]) и сумму элементов, у которых i-й бит не установлен (s[i][0]), все суммы по модулю 2. Всякий парный элемент участвует точно в тех же суммах, что и его пара и, таким образом, общий вклад от пары во всякой сумме равен 0.
Предположим, сначала, что непарные элементы A и В отличны от нуля. Тогда отличны от нуля только те суммы s[i][j], в которых участвует один или оба непарных элемента. Но непарные элементы отличаются хотя бы одним битом (иначе они были бы парой) k, тогда один из них равен s[k][0], а другой — s[k][1].
Если же один из непарных элементов равен нулю, то для любого k, s[k][0] и s[k][1] и дают искомые числа.

ilya_pu 2 июн 2016 в 10:52

кхм…
я не программист, но всё же… попробую предложить свой ход решения (увы, словами, а не на «компьютерном языке»)
1. получаем из последовательности число
2. заносим его в первую свободную ячейку памяти
3. проверяем все предыдущие ячейки памяти на равенство значений в них этому числу; если находится ячейка, значение в которой равно значению в последней ячейке (тем же XOR), обе ячейки «уничтожаем» (очищаем и высвобождаем для дальнейшего использования — например, если занято n ячеек, из которых оказываются равны n и m (m<n), то переносим значение ячейки n-1 в ячейку m, после чего уменьшаем n на единицу)
4. возвращаемся на шаг 1.

Да, этот вариант потребует массы вычислений (в худшем случае — если у нас идет сначала последовательность от 1 до 4 294 967 296, а затем — та же последовательность с двумя пропущенными значениями), однако можно предположить, что число переборов в реальности сократится (хотя вопрос — во сколько раз?), поскольку значения будут поступать неупорядоченно, а значит — пары будут взаимно погашаться. Если значения «приходят» с каким-то интервалом, НЕдостаточным для обработки, то, возможно, нам потребуется уже не 4 ГБ памяти для хранения входящей последовательности, а 8ГБ (в случае, если вычислительной мощности хватает исключительно на запись значений, но не хватает на какую-либо их обработку).

Хороший вопрос (с позиции теории вероятности): каким объёмом памяти можно обойтись для решения этой задачи, скажем, в 99% случаев, при условии, что скорости вычислений хватает для расчётов, а данные не приходят слишком часто?

Ogra 6 июн 2016 в 07:56

Ваше решение имеет алгоритмическую сложность O(n²), и имеет очень узкое применение: либо на маленьких массивах, либо на таких массивах, где парные элементы всегда расположены рядом друг с другом.
Иначе вполне можно получить ситуацию, где для каждого из миллиарда элементов проводится миллиард сравнений, что дает 10¹⁸ операций. Даже если выполнять 3 миллиарда сравнений в секунду, этот процесс займет 10 лет.

ilya_pu 10 июн 2016 в 21:47

да, логично… тогда попробую предположить другой вариант: каждое значение является адресом массива из 2^32 бит, когда приходит число n (1<=n<=2^32), мы проверяем значение этого конкретного бита: если оно равно нулю, это будет означать, что такое значение ещё не встречалось (или встречалось, но чётное число раз, то есть имеет пару). второй такой же массив можно использовать для проверки, обнулялось ли значение бита, что важно знать, например, если ищем «третьего лишнего»:
если бит n в первом массиве = 0, то добавляем к нему единицу;
если бит n в первом массиве = 1, то обнуляем его, а бит n второго массива увеличиваем на единицу
теперь, по окончании проверки, у нас будут в первом массиве единицы в тех битах, которые соответствуют числам, встретившимся лишь однажды (то есть, по сути дела, не имеющие пары).

по идее, проверять и менять бит в массиве памяти — не такая сложная задача (да и вместо 4 ГБ можно будет обойтись 0,5 ГБ для одного массива или 1 ГБ для двух)… единственное, что в такой постановке задачи каждый байт оказывается значим, а следовательно — невозможно решить эту задачу с меньшим доступным объёмом памяти… на мой взгляд, любые свёртки этого пространства до меньшего объёма приведут к выпадению информации о найденных числах…

да, и… какую алгоритмическую сложность имеет решение теперь?

Ogra 14 июн 2016 в 09:04

Да, теперь сложность O(n), все отлично. Но вот памяти уходит — мама не горюй =)

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

Дело в том, что эта структура хранит информацию обо всех числах, и подходит для решения задачи о любом количестве непарных чисел — 2, 3, 1000000, неважно. А в условии речь идет строго о двух числах, и для этой конкретной задачи такая структура избыточна.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Задачка про парные числа

Комментарии 114

Публикации

Истории