Недавно AlexanderBolshakov показал в этом посте — который без сомнения скоро канет в небытие потому что его заминусовали — несколько интересных задач со старинной олимпиады. С Zlobober стали они обсуждать задачу T4:

3млн человек с разными фамилиями выстроились в одну колонну и записали каждый у себя на бумажке фамилию свою и стоящего впереди (кроме первого). Бумажки у них отобрали, перемешали и в произвольном порядке в виде пар фамилий записали на магнитную ленту (односвязный список).

Как возможно быстрее узнать фамилию человека на 1234567 месте? Ограничение по памяти — не более 32 магнитных лент (списков) и не более 64кб памяти с произвольным доступом.

А правда, как это решать?

Мне на ум приходит пока следующее:

Ну сначала препроцессим данные — отсортируем и заменим фамилии на порядковые номера по алфавиту например, после чего исходную ленту перезапишем в виде пары чисел. Это у нас займёт O(N*logN).

Дальше из исходной ленты мы создадим две копии и отсортируем каждую — одну по порядку возрастания собственных фамилий, другую по порядку возрастания предшествующих.

Допустим если фамилии были однобуквенные и люди стояли так:

A D R O C I T E

То после этого шага (который тоже займёт O(N*logN)) у нас будет две ленты:

AD CI DR IT OC RO TE
OC AD TE CI RO DR IT

Эти пары можно явно слить за один проход в тройки (отбрасывая AD и TE как концевые по тому признаку что для них нет пары):

OCI ADR CIT ROC DRO ITE

Эти тройки я опять могу скопировать и отсортировать по первым и последним буквам, потом слить и получить пятёрки, дальше фрагменты по 9, 17 и т.п. Собственно хранить эти фрагменты целиком необязательно, от каждого нужна первая и последняя буквы.

От каждого шага будем оставлять по одной отсортированной (по первым буквам) ленте — с двойками, тройками, пятёрками, девятками... Так у нас будут ленты с фрагментами длиной до 2^20 и их формирование займёт O(N*logN^2) по-моему.

В принципе после этого я могу любую фамилию на этих лентах отыскать также за O(N*logN).

Но мне сдаётся что у меня получается много лишних действий (хранение ненужных фрагментов в том числе) избавившись от которых можно было бы формирование лент ужать до O(N*logN). Кроме того Я ни на одном шаге не попытался использовать память с произвольным доступом.

Правильны ли мои размышления и что тут можно улучшить?

В то же время я подозреваю что лучше чем O(N*logN) сделать в принципе нельзя, но в зависимости от ухищрений константа может быть очень разная.