?

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:
Page 1 of 2
<<[1] [2] >>
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)
Page 1 of 2
<<[1] [2] >>