Решение проблемы ACM 2010: замки

Question

Опубликуйте свои лучшие решения! Вы можете найти полное описание проблемы и примеры здесь: Проблемы ACM 2010 (pdf)

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

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

Answer 1

Я бы решил это так:

Bruteforce все стартовые замки (максимум 100) Для каждого начального замка: заполнить массив

потребность [i] и стоимость [i] означает, что когда вы переходите от выбранной начальной точки к i и пытаетесь получить поддерево, начиная с i, вам понадобятся как минимум [i] припои, а стоимостные [i] припои умереть. * * 1005

min_solder_to_attack_castle [i] выходит из входного файла.

Очевидно, что значения Need [] и Cost [] очевидны для «терминальных» замков. Затем для каждого замка, для которого известны значения потребности [] и стоимости [] для всех «детей», вы рассчитываете потребность и стоимость для этого замка следующим образом:

стоимость [i] = сумма (стоимость [childs])

Получение потребности [i] - сложная часть: мы знаем, что она находится где-то между max (min_solder_to_attack_castle [all childs]) и max (min_solder_to_attack_castle [all childs]) + max (cost [all childs]). Попытка всех вариантов обойдется нам (number_of_childs)! и, возможно, будет n !, и, возможно, здесь помогут оптимизации, вот где я остановился.

Answer 2

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

Второе, что нужно понять, это то, что если вы спуститесь по ветке дерева, вы должны завершить всю ветку для возвращения. Это позволяет нам сократить всю ветвь до единого «мегамолка» с необходимыми потерянными солдатами.

Итак, предполагая, что мы можем вычислить стоимость веток, у нас остаются две проблемы: с чего начать и как выбрать, какую ветку спустить первой. Я просто собираюсь форсировать стартовую позицию, но, возможно, будет лучше. Выбор ветви для спуска немного сложнее. Количество погибших солдат тривиально, а необходимое количество - нет. Нет! возможности, поэтому мы не можем просто попробовать их все.

Вместо того, чтобы думать о том, сколько солдат потеряно / требуется в каждом замке, я собираюсь вернуться назад. Начните с 0 солдат и добавляйте их, когда вы нападаете на замок, чтобы у нас было как минимум необходимое количество. Есть два случая: либо есть замок, для которого мы выполняем требование, либо нет. Если есть, (не) сделать этот замок (это оптимально, потому что мы использовали минимальное количество солдат). Если нет, добавьте еще одного солдата и попробуйте снова (это оптимально, потому что мы должны добавить солдата, чтобы продолжить). Теперь это должно стать очевидным: мы хотим (не) делать замок с требованиями, ближайшими к числу, потерянному первым. Просто отсортируйте (требуется минус потерян), и это ваш заказ.

Итак, окончательный алгоритм выглядит так:

• Грубая сила, отправная точка
• Рекурсивно уменьшать ветви в замки с заполнителями (запомните этот результат для других начальных точек)
• Посещение веток в порядке убывания (обязательно за вычетом потерь).

Время выполнения - O (n * c ^ 2 * lg (c)), где n - количество замков, а c - максимальное соединение любого отдельного замка. Это еще хуже, потому что существует не более n c 'ветвей', а узлу требуется не более c lg (c) времени для оценки после оценки его ветвей. [Ветви и узлы вычисляются не более одного раза благодаря запоминанию]

Я думаю, что можно добиться большего успеха, но я не уверен, как.

Answer 3

Я бы решил эту проблему в обратном порядке - вы хотите, чтобы несколько мужчин "впустую" после взятия последнего замка, насколько это возможно. Поскольку мы не можем пройти через замок, не взяв его, мы, очевидно, закончим в «листовом» замке.

Легко пройти назад из всех листовых замков, чтобы определить общее количество людей, "потраченных впустую" на каждом поддереве - тогда это просто вопрос обхода поддеревьев в правильном порядке.

Элементарно, мой дорогой Ватсон.