Какие серии слить
Timsort кладёт серии на стек одну за другой и сливает соседние серии стека. Слияние серий длиной x и y стоит x + y: столько элементов перекладывается. Даны длины серий в порядке, в каком они попадают на стек. Посчитайте полную цену всех слияний при двух правилах — исправленном правиле Timsort 2015 года и powersort.
Правило 2015 года. Положив серию, повторяем, пока на стеке больше одной серии. Пусть длины верхних серий — …, D, C, B, A (A — верхняя). Если C ≤ B + A или D ≤ C + B (каждое условие — если соответствующие серии есть), сливаем B с меньшей из соседок: с C, если C < A, иначе с A. Иначе, если B ≤ A, сливаем B и A. Иначе останавливаемся.
Powersort. Пусть n — сумма всех длин. Когда приходит новая серия длиной n2, а верхняя серия стека начинается с позиции s1 (сумма длин всех серий под ней) и имеет длину n1, считаем силу границы между ними: a = 2s1 + n1, b = a + n1 + n2, p = 0, и повторяем: p увеличивается на 1; если a ≥ n, из a и b вычитается n; иначе, если b ≥ n, вычисление закончено; затем a и b удваиваются. Пока у серии, лежащей под верхней, сила правой границы больше p, сливаем две верхние серии. Затем верхней серии записываем силу p и кладём новую серию.
В конце оба правила сливают всё, что осталось: пока серий больше одной, берут вторую сверху и сливают её с меньшей из соседок — с той, что под ней, если та короче верхней, иначе с верхней.
Вход
В первой строке — число серий k (1 ≤ k ≤ 105), во второй — их длины, от 1 до 107.
Выход
Два числа: цена всех слияний по правилу 2015 года и по powersort.
Первый пример — серии из статьи: правило 2002 года оставило бы стек неправильным, но цена в конце та же. Второй — серии, которые Timsort кладёт на стек, сортируя время коммитов этого сайта.
Примеры
Пример 1
5 120 80 25 20 30
550 550
Пример 2
15 40 70 65 40 364 88 40 40 255 57 60 40 41 40 18
5396 4534
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Нужен только стек длин: самих данных для цены слияний не нужно. Где в стеке хранить силу границы?
2Идея
Оба правила — простое моделирование стека длин. В правиле 2015 года главное — не забыть второе условие, на четвёртую сверху серию: без него стек может нарушить правило «каждая серия длиннее двух следующих вместе» в глубине, как в первом примере, и тогда стек перестаёт расти логарифмически. Powersort вместо правил о длинах смотрит на положение серий в массиве: сила границы — глубина узла, который разделяет середины двух соседних серий в идеальном двоичном дереве над всем массивом. Сливать надо, пока граница в стеке глубже новой, — так слияния следуют почти сбалансированному дереву.
3Разбор
Для правила 2015 года держим список длин и после каждой новой серии повторяем проверку из условия, сливая и прибавляя цену. Для powersort храним у каждой серии силу её правой границы, а начало верхней серии — это сумма длин всех серий под ней, то есть число уже положенных элементов минус длина верхней. Силу новой границы считаем один раз, до слияний, затем сливаем, пока сила под верхней больше новой, и записываем новую силу верхней серии. В конце — одинаковая для обоих правил доводка.
Сумма длин доходит до 1012, а цена — до нескольких десятков таких сумм: в Go нужен 64-битный int64. Значения a и b в цикле силы остаются меньше 4n и тоже помещаются.
3+Решение
4Сложность
Каждая серия кладётся на стек один раз и сливается не больше одного раза как верхняя, поэтому слияний меньше k, а проверок — O(k). Цикл силы делает не больше log₂ n + 2 шагов. Итого O(k log n).
5Типичные ошибки
- Правило 2002 года. Без проверки четвёртой сверху серии цена на некоторых входах другая: стек сливается позже и неравномернее.
- Считать силу после слияний. Сила новой границы зависит от верхней серии такой, какой она была до слияний; так она считается и в CPython.
- Сливать при равной силе. Условие строгое: при равной силе граница остаётся на стеке.
Алгоритмы задачи
O(n log n), на готовых данных O(n)
2 задачи
SRT
Алгоритм
Сортировка слиянием
Делит пополам, сортирует половины и сливает: n log n на любом входе, устойчиво, годится для внешней памяти.
O(n log n)
2 задачи