Количество мультимножеств, такое, что каждое число от 1 до может быть однозначно выражено как сумма некоторых элементов мультимножества.

11

Моя проблема. Учитывая , я хочу , чтобы подсчитать число действительных мультимножествами . Мультисеть действительна, еслиS SnSS

  • Сумма элементов является , инSn
  • Каждое число от до может быть выражена однозначно как сумма некоторых элементов .п S1nS

Пример. Например , если , то являются действительными.{ 1 , 1 , 1 , 1 , 1 } , { 1 , 2 , 2 } , { 1 , 1 , 3 }n=5{1,1,1,1,1},{1,2,2},{1,1,3}

Тем не менее, является недопустимым , так как 2 могут быть образованы как и (то есть, 2 может быть выражена как и и ), так что второе условие не выполнено. Аналогично 3 могут быть образованы и .{ 1 , 1 } { 2 } 2 = 1 + 1 2 = 2 { 2 , 1 } { 1 , 1 , 1 }S={1,1,1,2}{1,1}{2}2=1+12=2{2,1}{1,1,1}

1 5 S 5S={1,2,4 } также недопустимо, поскольку все числа от до могут быть выполнены однозначно, но сумма элементов не равна .15S5


Я пытался найти хороший алгоритм для этой проблемы в течение достаточно долгого времени, но не могу решить его. Это из codechef . Я видел некоторые из представленных решений, но все еще не мог понять логику решения проблемы. ПРИМЕЧАНИЕ: ограничение по времени для вопроса составляет 10 секунд иn<109

Для мультимножества я буду использовать обозначение , если , что означает происходит раза в мультинаборе S.a i < a j i < j a i c iS={(a1,c1),(a2,c2)...} ai<aji<jaici

До сих пор я сделал некоторые выводы

  • Первый элемент необходимого отсортированного мультимножества должен быть1
  • Пусть будет множеством, следующим за двумя свойствами, тогдаr < k a r + 1 = a r  или  ( r i = 0 a i ) + 1S={1,a2ak}|a1a2akr<k  ar+1=ar or (i=0rai)+1
  • Пусть , где встречается раз, следует требуемым свойствам, тогда из вышеприведенного вывода можно сказать, что и если . Доказательство:a i c ii a i | n + 1 a i | a j j > i a i + 1 =S={(1,c1),(a2,c2)(ak,ck)}|a1a2akaicii ai|n+1ai|ajj>i
    ai+1=(aici+ai1)+1ai|ai+1
  • Теперь рассмотрим т.е. все последующие числа после 1 будут кратны . Итак, пусть будет числом возможных таких множеств, тогда где я суммирую все возможные числа ( ). Другими словами,д е ( п ) f ( n ) = d | n + 1S={1,11d1,d,dd,dm1,dm1dm1,dm2,dm2dm2,}df(n)1's=d-1f(n-1)=g(n)=d| n,dng(d)f(n)=d|n+1,d1f(n(d1)d)1s=d1f(n1)=g(n)=d|n,dng(d)

Наконец, моя проблема сводится к этому - найти эффективным способом, чтобы он не превышал ограничение по времени.g(n)

Лига Справедливости
источник
2
Вы проверили, уместно ли просить других людей публично публиковать решения и алгоритмы для практических задач? Часто задаваемые вопросы Codechef, кажется, ожидают, что решения не будут опубликованы публично (за исключением некоторых самых основных проблем). Будет ли публикация решения "испортить" проблемы практики для других, или это считается нормальным? Я не знаком с нормами и этикетом сообщества Codechef.
DW
Я не нашел ничего, связанного с тем, чтобы не публиковать вопросы о публичном доступе в faq, и это ограничение касается текущих проблем конкурса, а не проблемы практики.
Лига справедливости
1
@DW Я не думаю, что они будут возражать, если мы будем обсуждать вопросы, не связанные с текущими конкурсами.
Рави Упадхяй,
1
Вы ищете количество разделов входного номера. Я предлагаю вам провести небольшое исследование, используя это модное слово.
Рафаэль
2
@ Рафаэль, я согласен, постер должен прочитать об этих методах. Это не совсем та же проблема - первое условие автора требует, чтобы это был раздел, но второе условие накладывает дополнительные ограничения (для уникальных изменений ) - но может быть возможно применить те же методы, которые используются для подсчета числа разделов, с некоторыми изменениями, чтобы справиться с дополнительным требованием.
DW

Ответы:

2

Вот что делает самое быстрое решение . Это действительно вычисление вашей функции Учитывая , мы ее разлагаем (см. ниже), а затем вычислить все факторы (см. ниже) в некотором порядке, так что подразумевает (свойство P). Теперь мы вычислим по формуле, пройдя факторы в указанном порядке. Свойство P гарантирует, что когда мы вычисляем , мы уже вычислили для всех нетривиальных множителей of . Также есть оптимизация (см. Ниже).

g(n)=dnd<ng(d),g(1)=1.
f 1 , , f m f i | f j i j g g ( d ) g ( e ) e dnf1,,fmfi|fjijgg(d)g(e)ed

Более подробно мы рассмотрим факторы по порядку, и для каждого фактора мы найдем все его нетривиальные факторы, проверив, какой из делит .f 1 , , f i - 1 f ifif1,,fi1fi

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

Генерация всех факторов: это делается рекурсивно. Предположим, что . Бежим Вложенные циклы , и выход , Вы можете доказать свойство P по индукции. т л 1{ 0 , ... ,n=p1k1ptkttр л 1 1р л т тl1{0,,k1},,lt{0,,kt}p1l1ptlt

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


Если первичная факторизация равна , то зависит только от и фактически только от отсортированной версии этот вектор. Каждое число ниже имеет не более простых факторов (с повторением), и, поскольку , представляется возможным вычислить (или, скорее, ) для всех из них, рекурсивно. Это решение могло бы быть быстрее, если бы было много разных входов; как есть, их максимум .p k 1 1 , , p k t tn+1p1k1,,ptkt( k 1 , , k t ) 10 9 29 p ( 29 ) = 4565 f g 10f(n)(k1,,kt)10929p(29)=4565fg10

Также возможно, что эта функция, отображающая разбиения на соответствующие , имеет явный аналитический вид. Например, , задается A000670 , а задается A005649 или A172109 .g ( p k ) = 2 k - 1 g ( p 1p t ) g ( p 2 1 p 2p t )gg(pk)=2k1g(p1pt)g(p12p2pt)

Юваль Фильмус
источник
1

Итак, у вас есть рекуррентное отношение для (см. Конец вашего вопроса).g()

На данный момент кажется, что естественным подходом было бы записать рекурсивный алгоритм для вычисления и применить запоминание, чтобы вы не вычисляли более одного раза. Другими словами, когда вы вычисляете , вы сохраняете его в хеш-таблице, которая отображает ; если вам нужно узнать снова в будущем, вы можете посмотреть его в хеш-таблице.g ( i ) g ( i ) i g ( i ) g ( i )g(n)g(i)g(i)ig(i)g(i)

Это требует факторинга , но существуют эффективные алгоритмы факторинга когда .n n 10 9nnn109

Вы также можете посмотреть на последовательность в энциклопедии целочисленных последовательностей . Если вы найдете последовательность в их энциклопедии, иногда они будут предоставлять дополнительную полезную информацию (например, эффективные алгоритмы для вычисления последовательности). Это правда , может взять удовольствие от вещей, хотя.g(1),g(2),g(3),g(4),g(5),

DW
источник
0

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

В немного более подробно: Предположим , у вас есть мультимножество . Учитывая число с , как вы можете определить подмножество которое суммируется с ? Как вы можете проверить, является ли этот подмножество уникальным? Попробуйте адаптировать стандартные методы динамического программирования для внесения изменений . (Смотрите также этот вопрос .)Si1inSi

Учитывая мультимножество , как можно проверить, удовлетворяет ли оно второму условию, т. Можно ли однозначно выразить каждое число от 1 до как сумму подмножества (уникальное условие внесения изменений)? Это должно быть довольно легко, если вы решили предыдущий.SnS

пусть обозначает список мультимножеств, которые удовлетворяют обоим вашим условиям. Если вы знали , как вы могли бы использовать эту информацию для построения ? Здесь вы можете адаптировать стандартные методы динамического программирования для перечисления разделов целого числа.P(n)P(1),P(2),,P(n)P(n+1)


Вот подход, который, вероятно, будет лучше.

Предположим, что является мультимножеством, которое удовлетворяет обоим вашим условиям (для ). Как мы можем расширить его, чтобы получить мультимножество которое имеет еще один элемент? Другими словами, как мы можем определить все способы добавить еще один элемент в , чтобы получить новый мультимножество которое удовлетворяет обоим вашим условиям (для некоторого )?SnTSTn

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

Более того, можно перечислить, какие целые числа можно выразить как сумму некоторых элементов , а какие нет, используя динамическое программирование. Вы строите двумерный массив логических значений , где имеет значение true, если есть способ выразить целое число в виде суммы некоторых из первые элементы из (только первые элементы из могут использоваться; где был отсортирован, поэтому и ). Обратите внимание, чтоSA[1|S|,1n]A[i,j]jiSiSSS={s1,s2,,sk}s1s2skA[i,j]можно вычислять, используя значения : в частности, если , или противном случае. Это позволяет определить все числа , которые являются кандидатами для добавления в .A[1i1,1j1]A[i,j]=A[i1,j]A[i1,jsi]j>siA[i,j]=A[i1,j]S

Далее, для каждого возможного расширения для (полученного путем добавления одного элемента к ) мы хотим проверить, удовлетворяет ли обоим условиям. Пусть обозначает сумму элементов и сумма элементов . Нам необходимо проверить , соответствует ли каждое целое число в интервале можно выразить в виде суммы некоторых из элементов . Это тоже можно решить с помощью динамического программирования, используя стандартные алгоритмы для внесения изменений. (На самом деле, если у вас еще есть массивS S T n S n T n + 1 , n + 2 , , n T A A [ 1 |TSSTnSnTn+1,n+2,,nTAупомянутое выше, вы можете легко расширить его, чтобы решить эту проблему: мы делаем его массивом , продолжаем заполнять все дополнительные записи и проверяем, что все верны.) Итак, теперь мы можем перечислить все мультимножества которые расширяют одним элементом, который удовлетворяет обоим условиям.A[1|T|,1n]T SA[|T|,n+1],A[|T|,n+2],,A[|T|,n]TS

Это сразу предлагает алгоритм для перечисления всех мультимножеств которые удовлетворяют вашему условию, для всех вплоть до некоторой границы, скажем, . У нас будет массив , где хранит все мультимножества , сумма которых равна 5, и, как правило, хранит набор всех мультимножеств , сумма которых равна .n n 20 P [ 1 20 ] P [ 5 ] S P [ n ] S nSnn20P[120]P[5]SP[n]Sn

Далее мы можем заполнить итеративно. Начните с установки чтобы он содержал только один мультимножество . Далее, для каждого (считая от 1 до 20), для каждого , перечислим все возможные расширения для (используя методы, описанные выше), пусть обозначает сумму элементов , и вставьте в если его еще нет и если .P [ 1 ] { 1 } n S P [ n ] T S n T T P [ n ] n 20P[n]P[1]{1}nSP[n]TSnTTP[n]n20

Это должно быть довольно выполнимо. Удачи! Повеселись! Работа с деталями будет хорошим обучающим упражнением в динамическом программировании.

DW
источник
Я не могу перечислить все целочисленные разбиения, потому что это будет экспоненциально. Я отредактировал вопрос и включил диапазон и некоторые мои мысли, но все же я застрял. Может быть, вы можете помочь. n
Лига справедливости