Курс без откатов
Для заставки к отчёту нужен график, на котором курс только растёт. Подделывать числа нельзя, а выбросить часть дней можно: на графике останутся настоящие курсы настоящих дней, просто не все. Чтобы картинка была честнее, дней хочется оставить как можно больше.
Дан ряд из n курсов по дням, в тиынах. Выберите как можно больше дней так, чтобы в выбранные дни, по порядку, курс строго рос: два одинаковых курса подряд на графике выглядят как ступенька, а не как рост. В тестах есть настоящие курсы доллара, евро и юаня к тенге за пять лет — в них курс на субботу, воскресенье и понедельник почти всегда один и тот же.
Вход
В первой строке — n (1 ≤ n ≤ 100 000). Во второй — n целых чисел a1, …, an (1 ≤ ai ≤ 109): курс в каждый день.
Выход
В первой строке — наибольшее число дней k. Во второй — номера этих дней по возрастанию, через пробел (дни нумеруются с единицы). Если вариантов несколько, выведите любой.
Примеры
Пример 1
12 42375 42402 42513 42432 42432 42432 42638 42583 42551 42424 42516 42516
4 1 2 10 12
Пример 2
5 50000 49900 49850 49850 49000
1 5
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сначала честная таблица: для каждого дня i — сколько дней в самой длинной растущей цепочке, которая кончается в день i. Как она считается из таблицы для предыдущих дней? И сколько это стоит при n = 100 000?
2Подсказка 2
Из всех цепочек длины k полезнее та, что кончается ниже: её легче продолжить. Храните для каждой длины только самый низкий конец. Как устроен этот массив и что с ним делает очередной день?
3Идея
Это наибольшая возрастающая подпоследовательность. Массив tops: tops[k] — самый низкий курс, которым может кончаться растущая цепочка из k + 1 дней. Он строго возрастает, поэтому для нового курса x место находит двоичный поиск: первая клетка, где tops[k] ≥ x. Если такой нет — цепочка удлинилась, иначе x заменяет tops[k]. Чтобы назвать сами дни, каждый день запоминает предыдущий день своей цепочки — тот, что лежал в tops[k − 1] в момент его прихода.
4Разбор
Идём по дням. Для курса x ищем k = bisect_left(tops, x), запоминаем prev[i] = top_at[k − 1] (или «нет», если k = 0) и кладём x на место k, вместе с номером дня в top_at[k]. В конце ответ — длина tops, а дни восстанавливаются от top_at последней клетки по указателям prev назад и разворачиваются.
Почему указатель верный: в момент прихода дня i в tops[k − 1] лежит конец цепочки длины k, и он меньше x — иначе двоичный поиск остановился бы раньше. Значит, к той цепочке можно приписать день i, и получится цепочка длины k + 1, которая кончается в день i.
Строгость решает одна буква. bisect_left ставит равный курс на место равного, и цепочка не удлиняется: в первом примере курс 424,32 трижды подряд даёт одну ступеньку, а не три. bisect_right продолжил бы цепочку равным курсом — так считают «не убывающую» подпоследовательность, и на настоящих данных она почти вдвое длиннее: у доллара 269 дней против 151.
4+Решение
5Сложность
O(n log n) времени: на каждый день — двоичный поиск по массиву не длиннее ответа. O(n) памяти на указатели. Таблица из первой подсказки — O(n²), пять миллиардов сравнений при n = 100 000.
6Типичные ошибки
- Квадратичная таблица. Верна, проходит тесты с настоящими курсами (там 1900 дней), но не успевает на ста тысячах.
- bisect_right вместо bisect_left. Получится цепочка, где курс не убывает, — она длиннее и не годится: соседние равные курсы — не рост.
- Вывести содержимое tops. Его длина — ответ, но сами числа в нём обычно не цепочка: в tops[0] может лежать курс последнего дня, а в tops[1] — более ранний. Дни нужно восстанавливать по указателям.