Конкурентное программирование - прохождение всех уровней с минимальными затратами: не прохождение всех тестовых примеров

Я решал проблемы на конкурентном веб-сайте кодирования, когда наткнулся на это. Проблема гласит, что:
В этой игре есть N уровней и M типов доступного оружия. Уровни пронумерованы от 0 до N-1, а оружие пронумеровано от 0 до M-1. Вы можете очистить эти уровни в любом порядке. На каждом уровне требуется некоторое подмножество этого M оружия, чтобы очистить этот уровень. Если на определенном уровне вам нужно купить x новых видов оружия, вы заплатите за это x ^ 2 монет. Также обратите внимание, что вы можете перенести все имеющееся у вас оружие на следующий уровень. Изначально у вас нет оружия. Сможете ли вы узнать минимальное количество монет, необходимое для прохождения всех уровней?

Формат ввода Первая строка ввода содержит 2 целых числа, разделенных пробелами: N = количество уровней в игре M = количество видов оружия

Далее следует N строк. В i-й из этих строк находится двоичная строка длины M. Если j-й символ строки эта строка равна 1, это означает, что нам нужно оружие типа j, чтобы очистить i-й уровень.

Ограничения 1 <= N <= 20 1 <= M <= 20

Выходной формат Выведите единственное целое число, которое и является ответом на проблему.

Пример TestCase 1
Вход
1 4
0101

Выход
4

Объяснение В этой игре всего один уровень. Нам понадобится 2 вида оружия - 1 и 3. Поскольку изначально Бен у него нет оружия, ему придется купить его, что будет стоить ему 2 ^ 2 = 4 монеты.

Пример TestCase 2
Вход
3 3
111
001
010

Выход
3

Объяснение В игре 3 уровня. Для 0-го уровня (111) требуются все 3 вида оружия. 1-й уровень (001) требует только оружия типа 2. Для 2-го уровня требуется только оружие типа 1. Если мы очистим уровни в заданном порядке (0-1-2), общая стоимость = 3 ^ 2 + 0 ^ 2 + 0 ^ 2 = 9 монет. Если мы очистим уровни в порядке 1-2-0, это будет стоить = 1 ^ 2 + 1 ^ 2 + 1 ^ 2 = 3 монеты, что является оптимальным способом.

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

Одним из возможных способов может быть обход массива двоичных строк и вычисление стоимости для каждого уровня, когда массив уже расположен в правильном порядке. Правильный порядок должен быть, когда строки уже отсортированы, то есть 001, 010, 111, как в случае вышеуказанного тестового примера. Обход массивов в таком порядке и суммирование стоимости для каждого уровня дает правильный ответ.

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

Arrays.sort(weapons);

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

К сожалению, я не вижу тестовых примеров, которые не работают. Любая помощь приветствуется.

Можете ли вы также купить оружие, которое вам не понадобится для следующего уровня?

SaiBot 11.04.2018 12:22

Покупая оружие для уровня, вы хотели бы покупать только то оружие, которое необходимо для этого уровня, покупка другого оружия, которое не нужно, увеличит стоимость, так зачем вам это делать?

John Stevens 11.04.2018 12:31

Допустим, у вас есть уровни 0001 и 1111. Если вы покупаете только то оружие, которое вам нужно, у вас будет стоимость 1 * 1 + 3 * 3 = 10, но если вы купите два оружия для первого уровня и два для второго, у вас будет 2 * 2 + 2 * 2 = 8, что явно лучше.

SaiBot 11.04.2018 12:45

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

Thomas Timbul 11.04.2018 12:47

@ThomasTimbul Согласен с вами. Правильный способ - подсчитать количество установленных битов вместо обычной сортировки. Однако даже после сортировки строк по количеству установленных битов все тестовые примеры не проходят.

John Stevens 11.04.2018 12:52

Разве это не относится к CodeReview или другому сайту SE?

Jeremy Grand 11.04.2018 12:57

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

Thomas Timbul 11.04.2018 13:04

Сомневаюсь, что проблему можно свести к простой задаче сортировки.

Ole V.V. 11.04.2018 13:08

Я не понимаю, как можно упростить задачу сортировки, и @SaiBot задает важный вопрос, но фраза «оружие, которое вам нужно» предполагает, что вы не можете покупать дополнительное оружие. Кстати: у второго тестового примера есть два решения для данной стоимости (1-2-0 и 2-1-0).

Hans Olsson 11.04.2018 13:42

@JeremyGrand Не совсем. Пожалуйста, прочтите мета-сообщение это для уточнения.

lexicore 11.04.2018 13:45

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

lexicore 11.04.2018 14:19

@lexicore, так что ни один из них? Насколько этот вопрос может быть интересным, я не думаю, что он здесь, по крайней мере, не в такой форме. Это слишком много для help me with my homework (даже если это не домашнее задание как таковое), чем для how to solve a technical issue.

Jeremy Grand 11.04.2018 19:20

@JeremyGrand С моей точки зрения, это онтопический как «программный алгоритм».

lexicore 11.04.2018 19:24

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

lexicore 11.04.2018 19:26

@JeremyGrand Подводя итог, я лично не голосовал за закрытие. Мне нравится этот вопрос, он показывает интересную проблему. И я хотел бы знать ответ.

lexicore 11.04.2018 19:27
1
15
1 297
3

Ответы 3

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

Например: у нас есть данные как 4 3 101-2 бит 010-1 бит 110-2 бит 101-2 бит теперь, поскольку 010 имеет минимальные биты, мы сначала вычисляем стоимость для него, а затем обновляем текущий шаблон (с помощью побитового ИЛИ), поэтому текущий шаблон равен 010 Затем мы находим следующие минимальные установленные биты по отношению к текущему шаблону Я использовал логику, сначала используя XOR для текущего шаблона и данного числа, затем используя AND с текущим числом (A ^ B) & A поэтому биты становятся такими после операции (101 ^ 010) и 101-> 101-2 бит (110 ^ 010) и 110-> 100-1 бит теперь мы знаем, что минимальный бит равен 110, мы выбираем его и вычисляем стоимость, обновляем шаблон и т. д. Этот метод возвращает стоимость строки относительно текущего шаблона.

private static int computeCost(String currPattern, String costString) {
  int a = currPattern.isEmpty()?0:Integer.parseInt(currPattern, 2);
  int b = Integer.parseInt(costString, 2);
  int cost = 0;
  int c = (a ^ b) & b;
  cost = (int) Math.pow(countSetBits(c), 2);
  return cost;
    }

Это тоже неправильно. Учитывайте уровни 11100, 11110, 11111, а также 00011. Решение потребует, чтобы 00011 сначала заплатил 4, после чего ему в любом случае пришлось бы заплатить 9 за первые три бита одновременно, в общей сложности 13. Принимая во внимание, что если мы начнем с оплаты 9 за 11100, мы можем продолжить с 11110, а затем платить 11111. всего 9 + 1 + 1 = 11.

Gassa 11.04.2018 22:42

Это можно решить с помощью динамического программирования.

Состояние будет битовой маской оружия, которым мы сейчас владеем.

Переходы будут состоять в том, чтобы попытаться очистить каждый из возможных уровней n по очереди из текущего состояния, получить дополнительное оружие, которое нам нужно, и заплатить за него. В каждом из результирующих состояний n мы берем минимальную стоимость текущего способа его достижения и всех ранее наблюдаемых способов. Когда у нас уже есть какое-то оружие, некоторые уровни фактически не потребуют покупки дополнительного оружия; такие переходы будут автоматически игнорироваться, поскольку в таком случае мы приходим в то же состояние, заплатив ту же стоимость.

Запускаем на состоянии нулей m, заплатив 0. Конечное состояние - это поразрядное ИЛИ всех заданных уровней, и минимальные затраты на его получение - это ответ.

В псевдокоде:

let mask[1], mask[2], ..., mask[n] be the given bit masks of the n levels
p2m = 2 to the power of m
f[0] = 0
all f[1], f[2], ..., f[p2m-1] = infinity
for state = 0, 1, 2, ..., p2m-1:
    current_cost = f[state]
    current_ones = popcount(state)  // popcount is the number of 1 bits
    for level = 1, 2, ..., n:
        new_state = state | mask[level]  // the operation is bitwise OR
        new_cost = current_cost + square (popcount(new_state) - current_ones)
        f[new_state] = min (f[new_state], new_cost)
mask_total = mask[1] | mask[2] | ... | mask[n]
the answer is f[mask_total]

Сложность заключается в времени O(2^m * n) и памяти O(2^m), что должно быть приемлемо для m <= 20 и n <= 20 в большинстве онлайн-судей.

@SaiBot Все возможные последовательности имеют номер n! и 20! = 2,432,902,008,176,640,000. С другой стороны, 2^20 - это только 1,048,576. Экономия за счет использования динамического программирования заключается в преобразовании n! в 2^n: состояние динамического программирования отбрасывает часть в каком порядке и оставляет только часть куплен или нет.

Gassa 12.04.2018 09:43

Идея динамической оптимизации @Gassa может быть расширена с помощью А *, оценивая минимальную и максимальную оставшуюся стоимость, где

minRemaining(s)=bitCount(maxState-s)
maxRemaining(s)=bitCount(maxState-s)^2

Начните с очереди с приоритетом - и основывайте ее на cost + minRemaining - только с пустым состоянием, а затем замените состояние из этой очереди, которое не достигло maxState, максимум на n новых состояний на основе n уровней:

Следить за bound=min(cost(s)+maxRemaining(s)) в очереди, и инициализируйте все расходы с помощью bitCount(maxState)^2+1

extract state with lowest cost
if state!=maxState
   remove state from queue
   for j in 1..n 
      if (state|level[j]!=state)
        cost(state|level[j])=min(cost(state|level[j]), 
           cost(state)+bitCount(state|level[j]-state)^2
        if cost(state|level[j])+minRemaining(state|level[j])<=bound
           add/replace state|level[j] in queue
else break

Идея состоит в том, чтобы избежать тупиков. Итак, рассмотрим пример из комментария

11100 cost 9 min 2 max 4
11110 cost 16 min 1 max 1
11111 cost 25 min 0 max 0
00011 cost 4 min 3 max 9
bound 13
remove 00011 and replace with 11111 (skipping 00011 since no change)
11111 cost 13 min 0 max 0
11100 cost 9 min 2 max 4
11110 cost 16 min 1 max 1
remove 11100 and replace with 11110 11111 (skipping 11100 since no change):
11111 cost 13 min 0 max 0
11110 cost 10 min 1 max 1
bound 11
remove 11110 and replace with 11111 (skipping 11110 since no change)
11111 cost 11 min 0 max 0
bound 11

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

Другие вопросы по теме