Гайки и болты

[marie-la]

Это известная задача про гайки и болты - есть $n$ болтов, $n$ гаек, каждый болт подходит ровно к одной гайке, при попытке совместить болт с гайкой становится известно, подходят ли они друг другу и если нет, то что больше - болт или гайка. И нужно придумать детерминированный алгоритм, находящий все пары болт-гайка за меньше чем $O(n^2)$ сравнений.
Нужен простой алгоритм, мне не нужно как можно меньше сравнений, главное, чтоб вышло меньше чем $O(n^2)$. Вроде как идея должна быть найти болт, делящий все гайки пополам, а затем работать с двумя половинами. Но как такой болт найти менее чем за квадратичное время?
Выручайте, сроки горят, а я что-то туплю!

[Someone]

Гайки и болты заранее отсортированы? Если нет, то можно ли сравнивать гайку с гайкой и болт с болтом? Является ли диаметр единственным существенным параметром болтов и гаек?

Д. Кнут. Искусство программирования для ЭВМ. Том 3. Сортировка и поиск.

[Gagarin1968]

Здесь на форуме уже была эта задача.

[marie-la]

Gagarin1968 в сообщении #1463878 писал(а):

Здесь на форуме уже была эта задача
.

Спасибо! Там так и не решили как автор хотел :( Так что и сейчас, наверное, без шансов.

[worm2]

Но выяснили, что это очень сложная задача, не квалификационного уровня (даже на должность профессора). Несколько лет никто в мире не мог решить!
Непонятно, что значит "сроки горят". Если вам задали её на собеседовании, от вас ждут не решения, а попыток рассуждений, которые и будут оценивать. На каждое рассуждение будут, скорее всего, задавать уточняющие вопросы, так что мы тут всё равно не сможем помочь.

[Sender]

Если что, есть статьи, где изложены асимптотически оптимальные алгоритмы для этой задачи. Например, https://hungary.pure.elsevier.com/en/publications/matching-nuts-and-bolts-in-on-log-n-time

[Mihaylo]

Попробую развить простой подход: применить обычный метод сортировки (произвольный). Основной смысл следующий: смешиваем два несортированных массива болтов и гаек в один общий несортированный, каждый элемент при этом помечаем буквами Б (болт) или Г (гайка). Мы получаем обычный массив для обычного алгоритма сортировки, но при сортировке не забываем параллельно сортировать массив маркеров Б/Г. Основной сортируемый массив имеет размерность $2n$, то есть $O(n)$.
1. Особенность сортировки: нельзя сравнивать одноименные элементы (Б нельзя сравнивать с Б, Г нельзя сравнивать с Г). Можно пробовать сравнивать, но тогда сравнение выдает ошибку, а сравнение при этом не засчитывается (сравнение одноименных элементов безопасно!). Важное предложение: при ошибке сравнения - переходить к следующему/другому элементу (skip). В этом моменте (skip) стандартные алгоритмы сортировки могут отличаться в поведении.
Пусть skip происходит влево или вправо, тогда рано или поздно найдется разноименный элемент, пригодный для сравнения, либо конец массива.
2. Болт и гайка, которые совпали, располагать друг за другом в произвольном порядке, а совпадение помечать массивом маркеров совпадения: С=0 - не совпало, С=1 - совпало. Этот массив также сортировать параллельно с основным массивом. Сортировка останавливается, когда весь массив C состоит из 1.

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