Решение: Максимальное произведение показаний
По каналу связи передаётся последовательность натуральных чисел — показания прибора. В течение $N$ минут прибор ежеминутно регистрирует значение напряжения в электрической сети и передаёт его на сервер. Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее $K$ минут, а произведение этих трёх чисел было максимально возможным. Даны два входных файла: файл $A$ и файл $B$. В первой строке каждого файла содержится натуральное число $K$, во второй — количество переданных показаний $N$ ($1 \leq N \leq 10\,000\,000$, $N>K$). В следующих $N$ строках записаны натуральные числа, не превышающие $10\,000\,000$. Запишите сначала значение искомой величины для файла $A$, затем для файла $B$. Для обработки файла $B$ нельзя использовать перебор всех возможных троек.
Решение по шагам
5 шаговПронумеруем показания от $1$ до $N$. Если выбран элемент на позиции $i$, следующий выбранный элемент может находиться только на позиции не ранее $i+K$.
Будем поддерживать лучшие произведения для выбора одного, двух и трёх допустимых показаний среди обработанных позиций.
При добавлении показания $a_i$ значение для одного элемента обновляется как максимум из прежнего значения и $a_i$.
Для двух элементов к $a_i$ можно присоединять лучший одиночный выбор среди позиций не позднее $i-K$. Аналогично для трёх элементов используется лучшее произведение двух элементов среди позиций не позднее $i-K$.
Такой алгоритм обрабатывает файл за $O(N)$ времени и использует $O(N)$ памяти либо $O(K)$ памяти при хранении необходимого окна. Однако приложенные входные файлы A и B с конкретными последовательностями показаний не представлены, поэтому численные значения ответов вычислить невозможно.
Численные ответы зависят от содержимого файлов A и B; сами файлы не приложены.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Перебирать все тройки показаний, что имеет кубическую сложность.
Проверять расстояние только между соседними выбранными позициями, не обеспечивая ограничение для любых двух позиций.
Использовать позицию $i-K+1$ вместо последней допустимой позиции $i-K$.
Переполнить 32-битный тип: произведение может достигать порядка $(10^7)^3$.