Недавно 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)
сделать в принципе нельзя, но в зависимости от ухищрений константа может быть очень разная.