CS
Задачник Базовый курс EN

Задача

Цена поиска

связный список вероятностная структура стек предподсчёт базы данных

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

У списка есть голова с башней высоты H — наибольшей из высот элементов. Поиск элемента x начинается в голове на уровне H. На каждом уровне, пока на нём следующий узел существует и его ключ меньше ключа x, поиск переходит к этому узлу — один шаг. Когда переходить некуда, поиск спускается на уровень ниже — тоже один шаг; с первого уровня «спуск» — это шаг к самому x. Узел виден на уровне ℓ, если высота его башни не меньше ℓ. Третий тест — список из сцены статьи: 735 страниц сервера Космического центра Кеннеди после всего дня 13 июля 1995 года.

Вход

В первой строке n (1 ≤ n ≤ 2·10⁵). Во второй — n чисел h₁, …, hn (1 ≤ hi ≤ 32): высоты башен элементов по возрастанию ключей.

Выход

Два числа: сумму шагов поиска по всем n элементам и наибольшее число шагов одного поиска.

Примеры

Пример 1

Вход
12
1 2 1 3 1 2 1 4 1 2 1 3
Выход
68 7

Пример 2

Вход
5
1 1 1 1 1
Выход
15 5

Ограничения

Время · Python
4000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
10 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Пройти каждый поиск честно — верно, но список, где все башни высоты 1, — это обычный связный список, и поиск последнего элемента проходит его весь: 2·10¹⁰ шагов на всех. Нужно считать шаги, не шагая.

2Подсказка 2

Спусков всегда ровно H, по одному на уровень. Остаётся сосчитать переходы вправо — то есть узлы, на которые поиск x наступает. Какие элементы левее x лежат на его пути?

3Подсказка 3

Пройдите путь задом наперёд, как в доказательстве из статьи: от x влево. Первым будет сосед слева. Куда путь шагнёт после него?

4Идея

Узел i левее x лежит на пути поиска тогда и только тогда, когда его башня не ниже всех башен между ним и x. Значит, путь назад — цепочка: сосед слева от x, потом ближайший слева от него элемент с башней не ниже, потом ближайший слева от того — и так до головы. Длину такой цепочки для каждого элемента считает один проход монотонным стеком: chain[i] = 1 + chain[ближайший слева не ниже i]. Шагов у поиска элемента j — chain[j − 1] + H.

5Разбор

Почему путь именно такой. На уровне ℓ поиск x стартует с последнего элемента перед x, чья башня достаёт до уровня ℓ + 1 (или с головы), и идёт вправо через все элементы до x, чьи башни достают до ℓ. Элемент i окажется на пути, если найдётся уровень ℓ ≤ hi, на котором между i и x нет башен выше ℓ: тогда поиск на уровне ℓ стартует не правее i и пройдёт через него. Подходящее ℓ — наибольшая из высот между i и x (или 1, если между ними никого), и оно не больше hi ровно тогда, когда башня i не ниже всех башен между ними. Это и есть условие.

Равные башни. Условие нестрогое: если между i и x есть башня той же высоты, поиск на этом уровне пройдёт через обе. Цепочка «ближайший слева не ниже» учитывает это; строгое «выше» потеряло бы шаги.

Стек. Идём слева направо и держим в стеке элементы, башни которых строго убывают, если смотреть от дна к вершине. Новый элемент i снимает со стека все элементы ниже себя; оставшаяся вершина — ближайший слева не ниже i, её цепочка на единицу короче цепочки i. Каждый элемент входит в стек и выходит из него один раз.

В сумме шагов может набраться больше 2³¹ — в шестом тесте, где все башни высоты 1, это 20 000 100 000, — в Go нужен int64. На настоящем списке из сцены сумма — 12 973 шага на 735 поисков, в среднем 17,65 шага; самый длинный поиск — 42 шага.

5+Решение
6Сложность

O(n) времени и памяти: один проход стеком и один проход по ответам — сколько бы ни было шагов у самих поисков.

7Типичные ошибки
  • Честное моделирование. Правильно, но на списке без экспресс-линий каждый поиск — проход с начала: шестой тест.
  • Строгое «выше». Теряет узлы с башнями той же высоты: во втором примере, где все башни единичные, получится 9 шагов вместо 15.
  • Забытые спуски. Кроме переходов вправо поиск делает H шагов вниз, и H — высота головы, то есть самой высокой башни, а не самого элемента.
  • 32-битная сумма. В шестом тесте сумма больше 2·10¹⁰.

Алгоритмы задачи

DS Структура данных Список с пропусками Связный список с экспресс-линиями по броскам монетки: поиск и вставка за O(log n) в среднем, без поворотов. O(log n) в среднем на поиск, вставку, удаление и ранг 1 задача DS Приём Монотонный стек Стек с упорядоченными значениями: ближайший больший элемент и наибольший прямоугольник за O(n). O(n) 2 задачи
Каталог алгоритмов