?

Log in

No account? Create an account
Три задачи для программистов - Олег Етеревский [entries|archive|friends|userinfo]
Oleg Eterevsky

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Три задачи для программистов [13 August 2007|15:09]
Oleg Eterevsky
[Tags|, ]

  1. (Простая и известная всем программистам.) Есть массив из чисел. Все числа, кроме одного, повторяются в нём по два раза (ественно, повторяться могут не подряд). Требуется найти неповторяющееся число за линейное время и с константной дополнительной памятью.
  2. (Её мне вчера сообщил knop и я решил её после двухчасовых раздумий.) Всё то же самое, но неповторяющихся чисел два. Нужно найти оба.
  3. (Эту я решать не умею.) В массиве повторяется только одно число. Нужно его найти.

Upd Сидящий рядом nikolenko, как оказалось, первую задачку не знал и за 5 минут её пока не решил. Так что определение "простая и известная всем программистам" к ней, наверное, всё-таки не подходит. :-)

LinkReply

Comments:
From: seliv
2007-08-13 11:47 am (UTC)
1. Проксорить все числа, что получится в итоге - и есть то одно неповторяющееся.
2. Пусть неповторяющиеся числа - A и B, A != B. Проксорив последовательность, получим некое число C = A ^ B, в котором есть хотя бы один ненулевой бит с номером bn (т.к. A != B). Значит, A и B отличются как минимум в этом бите. Далее пробегаемся по последовательности ещё раз, ксоря отдельно числа с bn == 1 и bn == 0, результатом этих двух ксоров и будут числа A и B.
(Reply) (Thread)
[User Picture]From: eterevsky
2007-08-13 11:54 am (UTC)
Правильно.
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]From: eterevsky
2007-08-13 12:20 pm (UTC)
Нет. Мне вообще ничего не известно про её решение. Хочется придумать любое решение лучшее O(n^2) при константной памяти или O(n log(n)) при линейной.
(Reply) (Parent) (Thread)
(Deleted comment)
(Deleted comment)
(Deleted comment)
(Deleted comment)
(Deleted comment)
(Deleted comment)
(Deleted comment)
[User Picture]From: gianthare
2007-08-13 12:31 pm (UTC)
А числа целые?
(Reply) (Thread)
[User Picture]From: gianthare
2007-08-13 12:32 pm (UTC)
хотя неважно, можно все равно с ними работать как с целыми?
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: amarao_san
2007-08-13 12:43 pm (UTC)
1. ксор массива в изначально нулевой счётчик. Итоговое число в счётчике - искомое.

2. вторую думаю.

3. третью тоже.
(Reply) (Thread)
[User Picture]From: amarao_san
2007-08-13 01:05 pm (UTC)
Можно ли писать в массив обрабатываемых чисел?
(Reply) (Thread)
[User Picture]From: amarao_san
2007-08-13 01:05 pm (UTC)
upd: обратимо, т.е. так, чтобы на выходе тот же массив, что был, плюс два искомых числа.
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: avva
2007-08-13 01:45 pm (UTC)
Первая известная, вторая очень хорошая. Думал, думал, кажется придумал. За линейное время с дополнительным коэффициентом разрядности чисел.
(Reply) (Thread)
[User Picture]From: avva
2007-08-13 02:12 pm (UTC)
Ага, и без коэффициента уже даже. Красота!
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: edwardahirsch
2007-08-13 07:33 pm (UTC)
Вторая вроде как ничем не отличается от первой: поддерживается две суммы; если при делении пополам нам не повезло, то на следующем шаге у нас половина; 1+1/2+1/4+... =O(1).

А про третью известно, что это можно сделать? Надо какой-то более хитрый гомоморфизм применить тогда (Вы же алгебраист, нет?).

Upd - гнать из Гугла!
(Reply) (Thread)
[User Picture]From: eterevsky
2007-08-13 09:14 pm (UTC)
Стоп-стоп. Я, кажется, не понимаю Вашего решения: как Вы собираетесь делить пополам?
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: mikev
2007-08-13 07:40 pm (UTC)
2. Как и в первой задаче сделаем XOR для всего массива. Поскольку искомые числа A и B различны, в ответе получим A^B, отличное от нуля. Возьмем в этом числе какой-нибудь разряд, равный единице, и отберем из исходного массива все числа, где 1 в этом разряде. Туда попадет одно из искомых и сколько-то пар. Для них все сводится к задаче 1. Потом все то же сделаем для чисел с нулем в этом разряде.
(Reply) (Thread)
[User Picture]From: eterevsky
2007-08-13 09:15 pm (UTC)
Да, именно так. :-)
(Reply) (Parent) (Thread)
[User Picture]From: faceted_jacinth
2007-08-13 08:16 pm (UTC)
Я вторую решил читерски: необходимая память квадратично зависит от битности каждого числа. Но поскольку она, вроде фиксирована, то так можно сделать, не правда ли?

1) Для каждого бита каждого числа вычисляем дополнительно его импликацию из предыдущего бита и тоже ксорим со вторым однобитным аккумулятором (на каждый бит). Для нулевого бита считаем импликацию из нуля. Поскольку неповторяющиеся числа разные, то где-то у нас должна появиться единичка в обычной сумме, возьмём ещё и следующий бит и построим табличечгу всех возможных комбинаций (считая, что в первом числе первый различающийся бит равен нулю)
a b a=>b xorb xorimp
0 0   1    0    1
1 0   1

0 0   0    1    1
1 1   1

0 1   1    1    0
1 0   1

0 1   0    1    1
1 1   1


О чудо! Нам удалось определить следующие биты!

2) Однако если эти следущие биты получились одинаковы, то бит через один таким образом определить не получится. Зато если мы предварительно проксорим биты a и b в каждом числе, то получим уже что-то разное, из чего можно опять же взять импликацию и всё точно определить.

3) Итого: для k-ого бита вычисляем и ксорим с соответствующим аккумулятором b[k] ^ b[k+1] ^ .. ^ b[k + i - 1] => b[k + i], плюс то же самое в обратном направлении, от старших к младшим. После зогхавывания всех чисел находим тот бит, в котором разные числа -- разные и по описанной выше методике определяем значения всех остальных их битов.

Уффф, пойду Аввин метод почитаю!
(Reply) (Thread)
[User Picture]From: faceted_jacinth
2007-08-13 08:20 pm (UTC)
в табличке последний xorb = 0, конечно.
(Reply) (Parent) (Thread)
[User Picture]From: spamsink
2007-08-14 01:04 am (UTC)
Какие ограничения на вычислительную сложность и используемую память в третьей задаче?
(Reply) (Thread)
[User Picture]From: eterevsky
2007-08-14 06:11 am (UTC)
Так как я не знаю её решения, то меня лично устроит любой алгоритм более быстрый, чем очевидные: быстрее n^2 при константной памяти или быстрее n log n при линейной.
(Reply) (Parent) (Thread) (Expand)
(no subject) - (Anonymous) Expand
[User Picture]From: nikolenko
2007-08-14 06:06 am (UTC)
Издева-ается. ;) Зато я вторую решил сегодня утром. Правда, тут у тебя, оказывается, уже написали. :) mikev написал.
(Reply) (Thread)
[User Picture]From: kobbi
2007-08-14 11:19 am (UTC)

медведебилтус

да. я таки знала, что в Одессе через Николенко нужно было тебе привед передавать (0:3
(Reply) (Thread)
[User Picture]From: eterevsky
2007-08-14 11:24 am (UTC)
Ну, в общем, надо признать, мы достаточно много времени проводим вместе. :-)
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: ingvar_77
2007-08-15 09:50 am (UTC)
Кажется я понял, как надо решать 3ю задачу, если не ступлю, то через несколько дней напишу решение (или идею если оно окажется слишком сложным)
(Reply) (Thread)
[User Picture]From: eterevsky
2007-08-15 09:57 am (UTC)
О, это будет круто.
(Reply) (Parent) (Thread)
[User Picture]From: anton_yakovlev
2007-08-23 10:18 am (UTC)
Похожая задача на первую была у меня на одной из районных олимпиад в девяностых (уже не помню, это был или 98 или 99-й год)
(Reply) (Thread)
[User Picture]From: the_phosphor
2007-08-25 03:56 pm (UTC)
В первой задаче сколько раз можно проходить массив? Если один - то это уже интереснее :)
(Reply) (Thread)
[User Picture]From: eterevsky
2007-08-26 06:36 am (UTC)
В первой? Одного достаточно.
(Reply) (Parent) (Thread) (Expand)
From: (Anonymous)
2007-09-26 11:52 pm (UTC)
With an AVL-tree you can solve your third problem in O(nlogn) total time (search and insert in O(logn) time until you find the first repetition).
(Reply) (Thread)
[User Picture]From: eterevsky
2007-09-27 08:38 am (UTC)
To solve the third problem in O(n log n) time and O(n) memory you don't have to use AVL-tree. Just sort the array and scan it once looking for repetition. The trick is to solve it either with less than linear memory (i.e. polylogarithmic or constant) and time less than O(n^2), or in O(n) time with unlimited memory.
(Reply) (Parent) (Thread)
[User Picture]From: igoralexeev
2007-10-31 01:14 am (UTC)

Третья задача - поиск равных чисел в огромном массиве

Третья задачка весьма интересная.
Я нашел ее решение в такой формулировке: есть огромный массив. Найти в нем пару равных чисел. С формальной точки зрения огромный массив - это массив, в котором больше чем 2^n n-битных чисел). Понятно, что в любом случае в этом массиве есть пара равных чисел.
Алгоритм использует константную память и время O(n).
Решение такое: пробегаем весь массив и смотрим во всех числах только 0-й бит. Пробегая, считаем, каких чисел в массиве больше - с 0-м битом, равным 0 или с 1. Пусть больше с 1. Затем пробегаем массив еще раз, смотря только те числа, у которых 0-й бит равен 1 (так как чисел, у которых 0-й бит равен 1, больше). У таких чисел смотрим на следующий бит (1-й), и подсчитываем, с каким значением 1-го бита чисел больше - с 0 или с 1 (важно, что в подсчете участвуют только те числа, у которых 0-й бит равен 1!). Пусть больше чисел с 1-м битом равным 0. Опять пробегаем весь массив, смотря только на числа с 0-м и 1-м битами равными 1 и 0, и смотрим на 2-й бит: чего больше в нем - 0 или 1. И т .д. И вот в конце мы и получим 2 равных числа.
Алгоритм можно и изменить - за каждый проход массива смотреть не по 1 биту, а, например, по 2. При этом будем подсчитывать, чего больше - 00, 01, 10 или 11.
(Reply) (Thread)
[User Picture]From: eterevsky
2007-10-31 12:43 pm (UTC)
Если 2 в степени битность чисел меньше, чем их количество, то задача сразу становится совсем простой. На мой вкус, даже проще, чем первая задача.

Более того, даже без такого предположения, если у нас имеется N чисел, каждое из которых < 2^M, то с помощью цифровой сортировки мы можем решить задачу за O(M*N).
(Reply) (Parent) (Thread) (Expand)
From: manymasks
2008-02-02 11:00 am (UTC)

Третья задача.

Пол дня рабочего на смарку :)

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

Предполагаемая асимптотика в среднем O(n), худший случай O(n*sqrt(n))
Память ~ n * sqrt(n)

Основная идея:
1. Создаём массивы C и L размером k = (n / 2 * 2) + 1 (т.е. ближайшее нечётное число >=n)
2. Проходим по массиву элементов А, считаем остаток от деления на k и инкрементируем соответствующую ячейку С
3. Проходим по массиву элементов А,
варианты: в C единичка - элемент выкидывается из A.
optional - В C двойка - можно обработать без заморочек с L
в C - от 3 до sqrt(n) - то запоминаем элемент в соответствующей ячейке L (в L списки элементов <= sqrt(n))
4. Проходим по непустым L и проверяем - не попало ли в корзинку нужное число. Если не попало - выкидываем числа из A

Наихудшая асимптотика в этом случае у 4 шага (поиск пары ведём влоб ~ n^2, а учитывая, что элементов sqrt(n) - у одного поиска O(n) и таких корзинок может быть соответственно sqrt(n))

В случае ненахождения - повторяем шаги 1-4 с k = (n / 2 * 2) + 3

P.S. В своих экспериментах - я не делал L (от есть рассматривал только ячейки C с 1 и 2) и ставил больше прогонов с увеличением k (т.е. >2), в большинстве тестов впрочем ответ выявлялся не познее второго прогона. Погонял при n сравнимых с максимальным элементом и с n << максимальный элемент.
P.P.S. В тестах у меня максимальный элемент из C не превышал 5, поэтому, вероятно, можно взять просто какую-то константу вместо sqrt(n), т.е. сведя цель первого прогона - прорядить A
(Reply) (Thread)
[User Picture]From: eterevsky
2008-02-02 02:52 pm (UTC)
Найти алгоритм с хорошей в среднем ассимптотикой -- хороший вариант. Проблема в том, что в худшем случае все числа будут иметь один тот же остаток от деления на k. Что делать в этом случае -- неясно. Надёжность можно повысить случайным образом выбирая несколько вариантов k из интервала (n, 2n).
(Reply) (Parent) (Thread)
(Deleted comment)
(Deleted comment)