Задачка

[nyaf]

Дано две последовательности чисел длины N. Числа рациональные, любые.
Для каждого числа k из первой последовательности найти все числа m из второй, что |k - m| <= R.

У меня получается O(NlogN + количество_ответов). Кто лучше?

P.S. На самом деле задачка про точки, и нужно найти лежащие в радиусе R. Но, думаю, это сводится.

Comments

[burunduk1]

Сортировка + 2 указателя (это видимо как раз то, что у тебя получается) - наилучший вариант с точки зрения практики...
А в теории, если я не ошибаюсь, фибоначева куча умеет за O(1) выбрать минимум и добавить, можно это использовать и получить O(N + кол-во_ответов)

[nyaf]

Я подумывал о сортировке только второго списка + два binary search для каждого запроса. Два указателя тоже идея, может даже быстрее будет. Правда тогда и первый список надо отсортировать.

Фибоначчиеву кучу непонятно как использовать тут, там же удаление за логарифм всё равно... А выбрать минимум и добавить за O(1) я могу и в вектор + переменную :)

[jp_bur]

Вообще-то, было бы интересно услышать про само сведение. Мне кажется, что про точки решается каким-то "разделяй и властвуй".

burunduk1, а удалять разве не нужно? Fibonacci heap поддерживает добавление за O(1), но удаление за амортизированный log(N). У нее вся прелесть не в этих операциях, а, скорее, в mergeability.

[nyaf]

Подразумевалось:
1. найти множества таких точек по каждой координате
2. найти пересечение множеств
3. ещё пробежаться и оставить точки, где декартово расстояние <= R
Но... да, там сложность получается побольше, конечно, потому что обрабатывается не количество_ответов, а ещё все лишние точки, лежащие в полосах (от x-R до x+R, от y-R до y+R). И их надо эффективно пересечь (ещё ~ MlogM от их количества).

Либо:
1. найти множество таких точек по одной коодринате
2. из него выбрать аналогично по второй координате
3. ещё пробежаться и оставить где декартово расстояние <= R
Тут тоже дополнительная сложность получается из-за обработки точек, не выходящих в ответ...

Вообще, на практике, наверно надо как-нибудь покластеризовать эти точки, да похешировать. И тогда будет всё близко к О(кластеризация + N + количество_ответов), а кластеризация какое-нибудь NlogN.