Наименьшая длина струны, содержащая все виды бусин

Question

Я где -то прочитал этот вопрос и не мог придумать эффективный ответ.

На каких -то длине на нем закреплены бусины на некоторых заданных произвольных расстояниях друг от друга. В целом на нити есть разные виды бисеров и бисеров $ n $, и каждый бусин присутствует как минимум один раз. Нам нужно найти один последовательный раздел строки, такой, что:

• Этот раздел содержит все разные виды бисеров, по крайней мере, один раз.
• Длина этого раздела максимально невелика, при условии, что первое условие выполняется.

Нам дают позиции каждого шарика на струне или, альтернативно, расстояния между каждой парой последовательных бусин.

Конечно, простой метод грубой силы будет начинаться с каждой бусинки (предположим, что раздел начинается с этой бусинки), и продолжать до тех пор, пока не будет обнаружено, когда все бусины не найдены при отслеживании длины. Повторите для каждой исходной позиции и найдите минимум среди них. Это даст решение $ O (n^2) $, где $ n $ - это количество бус на струне. Я думаю, что динамический подход программирования также, вероятно, будет $ O (n^2) $, но я могу ошибаться. Есть более быстрый алгоритм? Сложность пространства должна быть подквадратичной. Спасибо!

Редактировать: $ k $ может быть $ O (n) $.

Answer 1

С небольшой заботой ваше собственное предложение может быть реализовано в $ O (KN) $, если моя идея верна.

Держите указатели $ k $, по одному на каждый цвет и общий указатель, возможный начало сегмента. В каждый момент каждый из этих цветовых указателей сохраняет следующую позицию своего цвета, которая следует за указателем сегмента. Один из указателей цвета указывает на указатель сегмента. Этот указатель цвета обновляется, когда указатель сегмента перемещается в следующую позицию. Каждый указатель цвета в общей сложности перемещает только позиции $ n $. Для каждой позиции указатель сегмента вычисляет максимальное расстояние до цветовых нажимов, и человек принимает переоцененный минимум этого.

Или, возможно, интуитивно проще, пусть указатели заглядывают в прошлое, а не на будущее. Пусть указатели цвета обозначают расстояние до соответствующих цветов в последний раз. На каждом шаге добавляйте расстояние до последнего шарика к каждому указателю, за исключением того, что текущий цвет, который устанавливается на ноль.

(Редактировать: Ответьте на вопрос) Если $ k $ велик, в порядке $ n $, как предполагалось, тогда можно сохранить указатели $ k $ в максимальной куче. Обновление указателя стоит $ log k $ каждая из шагов $ n $. Мы можем найти Макса (самый дальний цвет, отсюда и длину интервала) в постоянное время, каждый из шагов $ N $. Итак, $ n log k $ total плюс инициализация.

Теперь мы также должны найти Элемент/цвет в куче, который мы должны обновить. Это делается путем сохранения индекса элементов. Каждый раз, когда мы переоцениваем элементы в куче (обычная работа кучи), мы также обменяем позиции, хранящиеся в индексе. Обычно это Doen при вычислении алгоритма Dijkstra с кучей: когда появляется новый край, некоторые расстояния до вершин должны быть уменьшены, и нужно их найти.