Серии Timsort
Timsort начинает с того, что режет массив на серии и кладёт их одну за другой на стек. Повторите эту первую часть работы и выведите длины серий в том порядке, в каком они попадают на стек.
- Наименьшая длина серии. Пусть m = n и r = 0. Пока m ≥ 64: если m нечётно, r = 1; затем m делится на 2 нацело. В конце minrun = m + r. Так считали в CPython до версии 3.14: при n < 64 minrun = n, иначе minrun от 32 до 64.
- Серия. С текущей позиции берётся самый длинный кусок, который либо не убывает (каждый следующий элемент не меньше предыдущего), либо строго убывает. Какой из двух — решают первые два элемента: если второй меньше первого, кусок строго убывающий. Убывающий кусок Timsort разворачивает, но длина от этого не меняется.
- Дополнение. Если серия короче minrun, она удлиняется до minrun — или до конца массива, если до него ближе, — за счёт следующих элементов, которые Timsort вставляет в неё вставками. Следующая серия ищется сразу после удлинённой.
Вход
В первой строке — n (1 ≤ n ≤ 2·105), во второй — n целых чисел от 1 до 109.
Выход
В первой строке — число серий k, во второй — их длины через пробел.
В первом примере n = 6 < 64, minrun = 6, и весь массив — одна серия, удлинённая вставками. Во втором n = 133, minrun = 34. Первая серия — числа от 100 до 30, строго убывающие, 71 штука; следующее 30 равно предыдущему, и убывание уже не строгое. Вторая серия — 30, 29, 28, всего три, и её удлиняют до 34. На остаток приходится 28.
Примеры
Пример 1
6 5 3 8 1 9 2
1 6
Пример 2
133 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 30 29 28 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
3 71 34 28
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Почему убывающая серия должна убывать строго? Что случится с двумя равными элементами, если такую серию развернуть?
2Идея
Это прямое моделирование, и вся трудность — в трёх правилах. Неубывающая серия допускает равные соседей, а убывающая — нет: её разворачивают, и два равных элемента при развороте поменялись бы местами, а Timsort устойчив и такого не делает. Короткая серия удлиняется до minrun, и следующая ищется с того места, где кончилось удлинение, а не естественная серия. И minrun считается по старшим шести битам n с единицей, если среди отброшенных битов была хоть одна единица: тогда n/minrun — степень двойки или чуть меньше, и дальше слияния идут ровными парами.
3Разбор
Считаем minrun. Идём по массиву: с текущей позиции lo определяем направление по первым двум элементам и продлеваем серию, пока оно сохраняется — строго для убывания, нестрого для роста. Если длина меньше minrun, заменяем её на min(minrun, n − lo). Записываем длину и переходим к lo + длина. Элементы внутри удлинения не важны: Timsort их отсортирует, но на длины следующих серий это не влияет.
3+Решение
4Сложность
O(n): каждая позиция просматривается один раз.
5Типичные ошибки
- Нестрогое убывание. Второй пример: числа 100…30, 30, 29, 28 выглядят как одна невозрастающая серия из 74 элементов, но у Timsort это 71 и затем новая серия.
- Искать следующую серию после естественной, а не после удлинённой. Удлинение забирает элементы следующей серии, и они уже не начнут новую.
- minrun без добавки. При n = 65 старшие шесть бит дают 32, но отброшенная единица делает minrun равным 33.