the_grue: (Default)
Постфактум простенькая, но я вчера неожиданно на ней подвис. Чувствовал, что _этот_ способ есть, но никак не удавалось формализовать интуицию. Кстати говоря, это не интервьюшный риддл - задача возникла в процессе разработки реального софта.

Пусть "деловая неделя" - это интервал из L дней, где L <= 7. Деловая неделя всегда начинается в определенный день W календарной недели (W ∈ [0 .. 6]). (Условия вполне жизненные - на самом деле есть страны, в которых деловая неделя пересекает границу календарной.) Имея W и L, а также день D ∈ [0 .. 6], найдите самый краткий/простой способ определить, лежит ли D внутри какой-нибудь деловой недели или нет.

P.S. Вообще-то правильных, но неидеальных решений у этой задачи много. Как узнать, является ли ваше решение тем самым? Если у вас возник этот вопрос, то это не оно :)
the_grue: (Default)
The bottleneck assignment problem (BAP) is formulated as follows: given a weighted bipartite graph G=(A,B,E), |A|=|B|=n, and an associated cost function c(a,b), find a bijective map M:B->A, s.t. the maximal cost on its edges is minimized. A slight generalization of the problem is when the vertex sets are of different cardinality (n=|B|<|A|=m), and the problem is to find a bijective map from B to a subset of A with the same constraint. The best generic algorithms are able to solve LBAP in O(n2.5/sqrt(log(n))) time. But the problem has more compelling worst-case bounds in several significant cases. Apparently, it has been very popular within the computational geometry field, as most of the special cases consider LBAP in a setting, where its vertices are points in the plane or in higher dimensions, and the cost function is a (usually Euclidean) norm. Solving the planar case requires O(n1.5 log(n)) time [1].

Curiously, the existing literature completely overlooks the case, where points lie in a one-dimensional space (e.g. they are just real numbers). This might be related to the fact that in the canonical formulation |B|=|A|, which happens to have a trivial linear-time solution in 1D: assuming A and B are sorted, just connect each ai to bi. But this doesn't lead us anywhere in the generalized case (n<m).

It therefore took me some time to figure out an efficient solution. The basic method is taken from a planar algorithm by Efrat et al [1], with all its details replaced by algorithms more suited for the 1D case. The resulting algorithm has O(m*log(m)) running time. I feel this could still be improved, but in the absence of a better option, here is the algorithm:
solution )
the_grue: (Default)
Сколько бит можно записать в 42 десятичных цифры? Другая формулировка: во сколько бит поместится то же количество значений, что и в 42 десятичных цифры?

Ответ скажу потом :)
the_grue: (Default)
Две задачки на вероятности, которые объединяет тот факт, что пока не увидишь доказательство, верить в правильный ответ очень не хочется ,) Вот поэтому я и удивляюсь, когда говорят, что теория вероятности считается легким предметом.

[livejournal.com profile] avva: Какая из последовательностей в среднем появится раньше, если бросать монету - орел, решка, орел или орел, решка, решка?

[livejournal.com profile] nadja_s: А вы знаете, что при игре в кости вы будете ждать выпадения последовательности 6,6,6 в среднем дольше, чем последовательности 4,5,6? Казалось бы - какая разница, а вот!
the_grue: (Default)
Эх, отпуск, отпуск! Сижу, извращаюсь над той самой злобной задачкой. Совсем как в good old days. Только в дейз я извращался на Java, а теперь на Factor. По предложению zefelder-а, мы решили длиной меряться - у кого функция короче :) Пока что с кодом в 116 символов веду я:
:: f | seq |
	seq 0 [ bitxor ] reduce
	seq 0 pick [| b h | h b bitxor b > b 0 ? bitxor ] curry reduce
	tuck bitxor ;


Зеффова программка из 139 символов на хаскелле явно чище тем, что четко разделяет две разных операции - фильтрацию и "ксоринг", и проигрывает только из-за необходимости импортировать модуль. Впрочем, ее стилистические преимущества имеют алгоритмическую цену - они требуют O(N) памяти, что противоречит условию задачи, и к тому же лишний цикл по всему массиву. Но вроде как lazy evaluation нейтрализует оба эффекта. Если так, то это решение мне очень по душе. Хотя и как-то коробит формально полагаться на оптимизацию.
import Data.Bits
f :: [Int] -> (Int, Int)
f list = (a, a `xor` b) where 
	a = foldr1 xor [c | c<-list, c > c `xor` b]
	b = foldr1 xor list
the_grue: (Default)
Попалась однажды шайка оголтелых компьютерных пиратов. Повязали их и всех вместе этапировали в тюрьму. Посадили в общую камеру. Сидят день, сидят два - наконец открывается дверь, заходит начальник тюрьмы.
- Дорогие мои уголовнички! Линчеватели Бритни Спирз, насильники Джоанны Роулинг, а особенно вы, clippo-маны недопоносовы! Всем вам хорошо известно, что за совершение тяжких преступлений, обесценивающих самозабвенный труд талантливых музыкантов, писателей, программистов и актрис порнографического кино, вас ждет пожизненное прозябание в одиночных камерах, оборудованных вместо окон небьющемися мониторами и динамиками, но без каких-либо устройств ввода. (И чтобы не притупилось чувство ответственности за проступки, каждых 15 минут на мониторе будет появляться поп-ап Windows XP, требующий установить свежие обновления, а из динамиков - раздаваться дефолтовый пузырчатый звук.)

Дрогнули от ужаса пираты, а начальник продолжает:
- В моей власти держать вас в этой дыре столько, сколько мне захочется. Но суд обязал меня выпускать каждого из вас иногда погулять. Есть у нас тут внутренний дворик, вот туда и будем вас выводить. Жаль только, забыл суд сказать, как часто это надо делать. Поэтому выпускать я вас буду тогда, когда мне захочется. Один, может, будет выходить каждый день, а остальные годами света белого не увидят. Вот почти и все. Так и проведете вы остаток своей жизни... Разве что...

Навострили уши уголовники, а начальник, хмыкнув, окинул их взглядом и говорит:
- Есть в том дворике, куда вас будут выводить гулять, модем с кнопкой и индикатором соединения. Один раз кнопку нажмешь - модем запищит-задаялит. Второй - дисконнектнется. Так вот, если в один прекрасный день один из вас выйдет во дворик погулять и справедливо заметит, что все остальные уже бывали в нем хотя бы раз, в тот же день отпущу всю кодлу. Но если ошибется - в течение месяца подвергну вас всех страшным пыткам, после чего казню через распиливание.

Закрылась дверь за начальником тюрьмы, а побледневшие преступники приступили к жаркому спору... До чего они могли додуматься?
the_grue: (Default)
Есть массив из N элементов, из них для каждого элемента, кроме двух, есть нечетное количество элементов, ему равных. Для обоих непарных элементов есть четное количество (может быть, ноль) элементов, ему равных. Найти эти два числа. Требования: время - O(N), память - O(1).

Для начала можно решить то же самое, но только с одним непарным числом, - это проще ;)

----------------------------------------------------------
Над сложным вариантом я мучился 3 дня... Просьба комментить полные/частичные решения под заголовком СПОЙЛЕР.
the_grue: (Default)
Один верблюд вырастил за год 10000 бананов. Город, где можно их продать, находится на расстоянии 1000 км. За один раз верблюд может нести 1000 бананов, при этом съедая один банан каждый километр пути. Какое максимальное количество бананов сможет продать верблюд?

via: [livejournal.com profile] sirius_solnca

Update: задачка сложнее, чем кажется
Page generated Sep. 21st, 2017 04:03 pm
Powered by Dreamwidth Studios