Комбинаторный алгоритм

Ответ 1

После разговора с моим профессором я узнал, что это была адаптация open.kattis.com problem.

Эти два почти идентичны, так как любой экземпляр исходной проблемы может быть решён путем вычисления простой факторизации N и обработки каждого простого множителя в виде шара. Например, 900 = 2 ^ 2 * 3 ^ 2 * 5 * 2, поэтому проблема эквивалентных шаров будет равна 2 2 2.

Данные оценки были найдены с использованием максимальной оценки 10 ^ 15. 2 ^ 50 > 10 ^ 15, поэтому никогда не может быть более 50 факторов, и умножение первых 15 простых чисел друг на друга также превышает 10 ^ 15, что означает, что может быть не более 14 групп.

Компромисс между количеством шаров и количеством групп был упущен, и, на мой взгляд, проблема намного проще решить. Например, если есть 14 групп, в каждой группе будет только 1 мяч, тогда как если будет 50 мячей, то все они будут принадлежать одной группе (это связано с ограничениями 10 ^ 15 исходной проблемы)

С этой новой информацией я смог решить проблему. Я факторизую N в список Primes, а также список всех факторов, а затем использовал алгоритм множественного рюкзака (если N имеет X уникальных простых коэффициентов, то рюкзак DP будет X + 1 размерным, где первое измерение равно какой предмет вы рассматриваете, а каждый другой размер представляет собой оставшийся запас определенного основного фактора). Каждый фактор из N будет представлять собой потенциальный предмет, который должен взять в рюкзак, причем его основная факторизация представляет собой вектор стоимости.

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

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

• Если вы можете создавать группы X без использования всех шаров, вы также можете сделать группы X, используя все шары. Это делает решения для ранца, где вы не используете 100% действующей мощности. Это предположение можно доказать, взяв все неиспользованные шары и добавив их в самую большую группу. Это создаст группу, большую, чем любая другая, и, следовательно, она должна быть уникальной. Это оставляет вас с одинаковым количеством групп, но все шары используются.

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

Мое решение имеет время выполнения O (F (N) ^ 2), где F (N) - общее число факторов N.

Ответ 2

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

Вход

Я буду считать, что вход имеет вид:

{K:30, N:6, red:4, green:3, blue:1, cyan:10, magenta:5, yellow:7}  

который также может быть записан как:

rrrr ggg b cccccccccc mmmmm yyyyyyy  

Одно шаровые группы

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

r g gg ggg (ggg) = 4  
  g gg ggg rggg  = 4

r g b bb bbb bbbbbb     = 6
r g b bb bbb bbbb (bb)  = 6
    b bb bbb bbbb rb gb = 6  

Это эффективно превращает ввод с K шарами из N цветов в проблему с шарами K-N с N или меньшим количеством цветов, максимум 49: 1, 48: 2... 36:14. Пример, упомянутый выше, снижен с 30: 6 до 24: 5

rrrr ggg b cccccccccc mmmmm yyyyyyy  
r g b c m y  +  rrr gg ccccccccc mmmm yyyyyy  

Малые и большие группы

Если вы создадите столько S-размерных групп, сколько возможно, прежде чем перейти к размеру S + 1, и вы оставите неиспользованные шары S, они сформируют дублируемую группу S-размера, но если бы был способ избежать этого, у вас будет еще одна S-размерная группа, поэтому это означало бы, что решение для S-размерных групп не было оптимальным в первую очередь.

Если вы создаете как можно больше S-размерных групп, прежде чем перейти к размеру S + 1, и у вас останется больше, чем S неиспользованных шаров, большие группы, которые вы формируете вместе с ними, никогда не будут дублировать группы S-размера.

Заманчиво предположить, что создание односимвольных групп, затем 2-мя шаров, тогда 3-мя шаров... приведет к оптимальному решению. Однако есть примеры, где это не так:

{K:45, N:5, red:3, green:3, blue:3, cyan:3, yellow:33}  
rrr ggg bbb ccc yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

r g b c y                         =  5  
rg bc ry gy by cy yy              =  7  
yyy yyyy yyyyy yyyyyy yyyyyyy (y) =  5
                            TOTAL = 17

r g b c y                         =  5  
      ry gy by cy yy              =  5  
ryy gyy byy cyy                   =  4  
yyy yyyy yyyyy yyyyyy             =  4  
                            TOTAL = 18

Кажется, что именно здесь вступает в игру максимум 50 мячей. Если вы начнете с создания максимально возможного количества 1-мя групп, то 2, 3... возможно, вам придется разбить небольшую группу, чтобы превратить оставшиеся шары (или уникальную группу + оставшиеся шары) в два или более уникальные группы. Однако представляется невозможным улучшить решение без остаточных шаров, по крайней мере, с этим пределом размера ввода.

Поиск оптимального количества двухразмерных групп означает заполнение 2D-таблицы следующим образом:

   r  g  b  c  m  y
r  +
g  +  -
b  +  -  +
c  -  +  -  -
m  +  +  -  +  +
y  -  +  +  -  -  +

Есть 1 + 2 +... + N возможных групп, но это не значит, что есть 2 ^ (1 + 2 +... + N) варианты для рассмотрения. С одной стороны, мы ищем оптимальное решение, поэтому нет смысла рассматривать решения только с несколькими группами, а с другой стороны, после создания 1-мя шариковых групп остается максимум K-N мячей создавать группы. Там также тот факт, что некоторые цвета могут не иметь шаров N + 1, поэтому не все комбинации с этим цветом могут быть сделаны одновременно; на самом деле становится невозможным создать все комбинации из 2 мячей при использовании более 6 цветов:

 N   K-N   pairs  combi

 1    49    24      1
 2    48    24      3
 3    47    23      6
 4    46    23     10
 5    45    22     15
 6    44    22     21
 7    43    21     28
 8    42    21     36
 9    41    20     45
10    40    20     55
11    39    19     66
12    38    19     78
13    37    18     91
14    36    18    105

Ответ 3

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

• Чем больше результат выигрывает (например, две группы, которые объединяются с новой отдельной группой над двумя группами, которые объединяются с уже известным)
• Получается меньший результат (например, двухэлементные группы над группами из трех элементов)
• Наиболее распространенные группы для удаления

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

Примеры (каждая строка упорядочена по количеству вхождений):

b  g-g-g  r-r-r-r  m-m-m-m-m  y-y-y-y-y-y-y  c-c-c-c-c-c-c-c-c-c
b  cc  g-g-g  r-r-r-r  m-m-m-m-m  y-y-y-y-y-y-y  c-c-c-c-c-c-c-c
b  cc  cy  g-g-g  r-r-r-r  m-m-m-m-m  y-y-y-y-y-y  c-c-c-c-c-c-c
b  cc  cy  cm  g-g-g  r-r-r-r  m-m-m-m  y-y-y-y-y-y  c-c-c-c-c-c
b  cc  cy  cm  yy  g-g-g  r-r-r-r  m-m-m-m  y-y-y-y  c-c-c-c-c-c
b  cc  cy  cm  yy  cr  g-g-g  r-r-r  m-m-m-m  y-y-y-y  c-c-c-c-c
b  cc  cy  cm  yy  cr  cg  g-g  r-r-r  m-m-m-m  y-y-y-y  c-c-c-c
b  cc  cy  cm  yy  cr  cg  my  g-g  r-r-r  m-m-m  y-y-y  c-c-c-c
b  cc  cy  cm  yy  cr  cg  my  rm  g-g  r-r  m-m  y-y-y  c-c-c-c
b  cc  cy  cm  yy  cr  cg  my  rm  g  yg  r-r  m-m  y-y  c-c-c-c
b  cc  cy  cm  yy  cr  cg  my  rm  g  yg  r  y  ry  m-m  c-c-c-c
b  cy  cm  yy  cr  cg  my  rm  g  yg  r  y  ry  m-m  cc-cc  c-c
b  cy  cm  yy  cr  cg  my  rm  g  yg  r  y  ry  m  cc  mcc  c-c
cy  cm  yy  cr  cg  my  rm  g  yg  r  y  ry  m  cc  mcc  c  cb

g-g-g  r-r-r-r-r  b-b-b-b-b
rb  g-g-g  r-r-r-r  b-b-b-b
rb  rg  g-g  r-r-r  b-b-b-b
rb  rg  br  g  r-r-r  b-b-b
rb  rg  br  g  r  rr  b-b-b
rb  rg  br  g  r  rr  b  bb

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

• выберите наиболее распространенную группу и удалите ее, затем выберите (сейчас) наиболее распространенную группу и удалите ее.
• посмотрите, что они вместе не имеют больше элементов, чем то, что может быть достигнуто с менее распространенными группами.
• Посмотрите, что они объединяются с неизвестной группой.
• Если да, возьмите их, если нет, то повторите с шага 1 со следующими общими группами

Это в основном задает вопросы

• Насколько распространена эта группа (комбинация элементов)/каково ее количество вхождения?
• Возможны ли все возможные комбинации с элементами из этой группы ниже определенного размера?
• Возможны ли комбинации с элементами этой группы и элементами из уже сгенерированных следующих групп?

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