Минимальное количество дней, необходимое для решения списка вопросов

Question

Существует N задач с номерами 1..N, которые необходимо выполнить. Вы упорядочили задачи в порядке возрастания сложности, и i-я задача оценила уровень сложности i. Вы также присвоили рейтинг vi каждой проблеме. Проблемы с похожими значениями vi имеют схожий характер. Каждый день вы будете выбирать подмножество проблем и решать их. Вы решили, что каждая последующая задача, решенная в этот день, должна быть сложнее, чем предыдущая задача, которую вы решили в этот день. Кроме того, чтобы не скучно, последовательные проблемы, которые вы решаете, должны отличаться по их рейтингу vi как минимум на K. Какое наименьшее количество дней, в течение которых вы можете решить все проблемы?

Входные данные: Первая строка содержит количество тестовых случаев T. T тестовых примеров следуют. Каждый случай содержит целые числа N и K в первой строке, за которыми следуют целые числа v1,...,vn во второй строке.

Выходные данные: Выведите T строк, по одной на каждый тестовый пример, содержащих минимальное количество дней, в течение которых можно решить все проблемы.

Ограничения:
1 <= T <= 100
1 <= N <= 300
1 <= vi <= 1000
1 <= K <= 1000

Пример ввода:
2
3 2
5 4 7
5 1
5 3 4 5 6

Пример вывода:
2
1

Это один из вызовов интервью.
Ниже мой подход
Начните с 1-го вопроса и выясните максимально возможное количество вопросов, которые можно решить, и удалите эти вопросы из списка вопросов. Теперь снова начните с первого элемента оставшегося списка и делайте это до сих пор, размер списка вопросов равен 0. Я получаю неправильный ответ от этого метода, поэтому ищет какой-то алгоритм для решения этой проблемы.

Answer 1

Построить DAG из проблем следующим образом. Пусть p_i и p_j - две разные проблемы. Затем мы нарисуем направленное ребро от p_i до p_j тогда и только тогда, когда p_j может быть решена непосредственно после p_i в тот же день, последовательно. А именно, должны быть выполнены следующие условия:

1. я , потому что вы должны решить менее сложную проблему раньше.
2. |v_i - v_j| > = K (требование к рейтингу).

Теперь обратите внимание, что каждое подмножество проблем, которое будет решено в один прекрасный день, соответствует направленному пути в этой DAG. Вы выбираете свою первую задачу и затем шаг за шагом следуете за ребрами, каждое ребро в пути соответствует паре проблем, которые были последовательно решены в один и тот же день. Кроме того, каждая проблема может быть решена только один раз, поэтому любой узел в нашей группе обеспечения доступности баз данных может появляться только по одному пути. И вам нужно решить все проблемы, поэтому эти пути должны охватывать все DAG.

Теперь у нас есть следующая проблема: учитывая группу DAG из n узлов, найдите минимальное количество непересекающихся направленных путей, которые полностью покрывают эту группу DAG. Это хорошо известная проблема под названием Path cover. Вообще говоря, это NP-хард. Тем не менее, наш ориентированный граф является ациклическим, и для ациклических графов его можно решить за полиномиальное время, используя приведение к задаче сопоставления. Задача максимального соответствия, в свою очередь, может быть решена, например, с помощью алгоритма Хопкрофта-Карпа. Точный метод сокращения прост и может быть прочитан, скажем, в Википедии. Для каждого направленного ребра (u, v) исходного DAG следует добавить неориентированный ребро (a_u, b_v) к двудольному графу, где {a_i} и {b_i} - две части размера n.

Количество узлов в каждой части результирующего двудольного графа равно количеству узлов в исходной группе DAG, n. Мы знаем, что алгоритм Хопкрофта-Карпа работает в O (n^2,5) в худшем случае и 300^2,5 ≈ 1 558 845. Для 100 тестов этот алгоритм должен занять в общей сложности менее 1 секунды.

Answer 2

Алгоритм прост. Сначала рассортируйте проблемы по v_iзатем для каждой задачи найдите число задач в интервале (v_i-K, v_i], Максимум этих чисел является результатом. Второй этап может быть сделан в O(n)Таким образом, самой дорогой операцией является сортировка, что делает весь алгоритм O(n log n), Посмотрите здесь для демонстрации работы алгоритма на ваших данных и K=35 в электронной таблице.

Почему это работает

Давайте переформулируем проблему в проблему раскраски графов. Мы создаем граф G следующим образом: вершинами будут проблемы, и между двумя проблемами будет грань, если |v_i - v_j| < K,

На таком графике независимые множества точно соответствуют наборам задач, выполнимых в один и тот же день. (<=) Если набор может быть сделан в день, это, безусловно, независимый набор. (=>) Если в наборе нет двух задач, не удовлетворяющих критерию K-разности, вы можете просто отсортировать их по сложности и решить в следующем порядке. Оба условия будут выполнены таким образом.

Отсюда легко следует, что раскраски графа G точно соответствуют графикам задач в разные дни, причем каждый цвет соответствует одному дню.

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

Графики интервалов - это графики интервалов на реальной линии, ребра - между интервалами, которые пересекаются. Наш график, как легко увидеть, представляет собой интервальный граф (для каждой задачи назначьте интервал (v_i-K, v_i], Легко видеть, что ребра этого интервального графа в точности совпадают с ребрами нашего графа).

Лемма 1. В интервальном графе существует вершина, соседи которой образуют клику.

Доказательство легко. Вы просто берете интервал с самой низкой верхней границей (или самой высокой нижней границей) из всех. Любые интервалы, пересекающие его, имеют верхнюю границу выше, поэтому верхняя граница первого интервала содержится в пересечении их всех. Поэтому они пересекаются друг с другом и образуют клику. QED

Лемма 2: В семействе графов, замкнутых на индуцированных подграфах и обладающих свойством из леммы 1 (существование вершины, соседи которой образуют клику), следующий алгоритм дает минимальную раскраску:

1. Найдите вершину x, соседи которой образуют клику.
2. Удалите x из графа, сделав его подграф G'.
3. Color G'рекурсивно
4. Цвет x по наименьшему цвету не найден у его соседей

Доказательство. В (3) алгоритм дает оптимальную раскраску подграфа G'по предположению индукции + близость нашего семейства на индуцированных подграфах. В (4) алгоритм выбирает только новый цвет n если есть клика размера n-1 на соседей х. Это означает, что с х, есть клика размера n в G, поэтому его цветность должна быть не менее n, Поэтому цвет, заданный алгоритмом для вершины, всегда <= chromaticity(G), что означает, что окраска является оптимальной. (Очевидно, алгоритм выдает правильную раскраску). QED

Следствие: интервальные графики идеальны (идеальная <=> цветность == последовательность)

Так что нам просто нужно найти последовательность G. Это просто для интервальных графов: вы просто обрабатываете отрезки реальной линии, не содержащие границ интервалов, и подсчитываете количество пересекающихся там интервалов, что еще проще в вашем случае, где интервалы имеют одинаковую длину. Это приводит к алгоритму, изложенному в начале этого поста.

Answer 3

Нам действительно нужно идти к дорожке? Разве мы не можем просто следовать той же стратегии, что и ЛИС.

Ввод в порядке возрастания сложности. Мы просто должны поддерживать кучу очередей для задач, которые будут выполняться каждый день. Каждый элемент на входе будет назначен на день, сравнивая последние элементы всех очередей. Везде, где мы находим разницу "k", мы добавляем задачу в этот список.

Например: 5 3 4 5 6

1) Ввод -> 5 (пустые списки, поэтому начинайте новый)

5

2) 3 (только список 5 & abs (5-3) равен 2 (k), поэтому добавьте 3)

5 -> 3

3) 4 (только список с последними vi, 3 и abs (3-4)

5 -> 3

4

4) снова 5 (abs (3-5) = k append)

5 ->3-> 5

4

5) снова 6 (abs(5-6)

5 ->3-> 5

4 ->6

Нам просто нужно поддерживать массив с последними элементами каждого списка. Поскольку порядок дней (когда задачи должны быть выполнены, не важен), мы можем поддерживать отсортированный список последних задач, поэтому, поиск места для вставки новой задачи просто ищет значение abs (vi-k), которое можно сделать через бинарный поиск.

Сложность:

Цикл работает для N элементов. В худшем случае мы можем запросить значение ceil, используя бинарный поиск (log i) для многих входных данных [i].

Следовательно, T(n)

Answer 4

Минимальное количество требуемых дней будет таким же, как длина самого длинного пути в дополнительном (ненаправленном) графике G (DAG). Это можно решить с помощью теоремы Дилворта.