Это проблема с практической сессии Польского студенческого соревнования по программированию 2012 года . Хотя я мог найти решения для основного конкурса, я не могу найти решение этой проблемы где-либо.
Проблема в том, что: учитывая набор из различных положительных целых чисел, не превышающих , найдите размер наименьшего подмножества, у которого нет общего делителя, кроме 1. не более 500, и можно предположить, что решение существует ,10 9 m N
Мне удалось показать, что . Я рассуждаю так: предположим, что существует минимальное подмножество размера с gcd = 1. Тогда все 9-подмножеств должны иметь gcd> 1. Таких подмножеств ровно 10, и их gcds должны быть попарно взаимно просты. Пусть эти gcds будут , где , для i \ neq j . Тогда максимальное число в S равно g_2g_3 ... g_ {10} . Но g_2g_3 ... g_ {10} \ ge 3 \ times5 \ times7 \ times11 \ times ... \ times29 = 3234846615> 10 ^ 9 , противоречие.
Однако даже при этом прямая грубая сила все еще слишком медленная. У кого-нибудь есть другие идеи?
источник
Ответы:
Эта проблема эквивалентна следующей, и тривиально сконструировать сокращение в обоих направлениях.
Учитывая список битовых векторов, найдите их минимальное количество, чтобы0 (∗)
and
все они приводили к битному вектору.Затем мы покажем, что набор обложек уменьшается до . Под набором покрытий я подразумеваю заданный список наборов , найти минимальное количество наборов, которое охватывает их объединение.(∗) S1,…,Sk
Мы упорядочиваем элементы в наборах как . Пусть , где если , 0 в противном случае. Обратите внимание, что эта функция является биекцией, поэтому она имеет обратную.a1,…,an f(S)=(1−χa1(S),…,1−χan(S)) χx(S)=1 x∈S
Теперь, если мы решим для , и решения будут , тогда - решение для укрытия.(∗) f(S1),…,f(Sk) {f(Sb1),…,f(Sbm)} {f−1(Sb1),…,f−1(Sbm)}
Таким образом, я думаю, что эта проблема проверяет способность обрезать пространство поиска.
источник
Это можно решить относительно эффективно путем вычисления всех парных gcd, удаления дубликатов, а затем повторения. Это действие по удалению дубликатов, прежде чем вы начнете повторять, что делает его эффективным.
Я объясню алгоритм более подробно ниже, но сначала он помогает определить бинарный оператор . Если - наборы натуральных чисел, определите⊗ S,T
Обратите внимание, чтои (в вашей задаче); обычно будет даже меньше, чем предполагает любая из этих границ, что помогает сделать алгоритм эффективным. Также обратите внимание, что мы можем вычислить с помощьюОперации gcd простым перечислением.|S⊗T|≤|S|×|T| |S⊗T|≤109 S⊗T S⊗T |S|×|T|
С этим обозначением вот алгоритм. Пусть будет входным набором чисел. Вычислить , затем , затем и так далее. Найдите наименьшее такое, что но . Тогда вы знаете, что размер наименьшего такого подмножества равен . Если вы также хотите вывести конкретный пример такого подмножества, сохраняя обратные указатели, вы можете легко восстановить такой набор.S1 S2=S1⊗S1 S3=S1⊗S2 S4=S1⊗S3 k 1∈Sk 1∉Sk−1 k
Это будет относительно эффективно, так как ни один из промежуточных наборов не увеличится в размерах выше (на самом деле их размер, вероятно, будет намного меньше этого размера), а время выполнения требует около операции gcd.109 500×(|S1|+|S2|+⋯)
Вот оптимизация, которая может повысить эффективность еще больше. В принципе, вы можете использовать повторное удвоение, чтобы найти наименьшее такое, что . В частности, для каждого элемента мы отслеживаем наименьшее подмножество чей gcd равен а размер равен . (Когда вы удаляете дубликаты, вы разрешаете связи в пользу меньшего подмножества.) Теперь вместо того, чтобы вычислять последовательность из девяти наборов , мы вместо этого вычисляем последовательность из пяти наборов , вычисляя , затем , затемk 1∈Sk x∈Si S1 x ≤i S1,S2,S3,S4,…,S9 S1,S2,S4,S8,S9 S2=S1⊗S1 S4=S2⊗S2 S8=S4⊗S4 , затем . На ходу найдите первый такой, что . Как только вы нашли такое, что , вы можете немедленно остановиться: вы можете найти наименьшее подмножество, чей gcd равен , посмотрев на подмножество, связанное с . Таким образом, вы можете остановиться, как только достигнете набора такого, что , что позволяет останавливаться раньше, если вы найдете меньшее подмножество.S9=S1×S8 k∈[1,2,4,8,9] 1∈Sk k 1∈Sk 1 1 Sk 1∈Sk
Это должно быть эффективным с точки зрения времени и пространства. Чтобы сэкономить место, для каждого элемента вам не нужно хранить весь набор: достаточно сохранить два обратных указателя (поэтому два элемента , из которых вы взяли gcd, чтобы получить ) и необязательно размер соответствующего подмножества.x∈Sk Si,Sj x
В принципе, вы можете заменить последовательность на любую другую цепочку добавления . Я не знаю, будет ли какая-то другая цепочка дополнений лучше. Оптимальный выбор может зависеть от распределения правильных ответов и ожидаемых размеров наборов , что мне не ясно, но, вероятно, может быть получено опытным путем с помощью экспериментов.[1,2,4,8,9] Sk
Благодарности: Моя благодарность KWillets за идею сохранения подмножества чисел вместе с каждым элементом , что позволяет рано останавливаться.Si
источник
Возможно, это быстрее, если взглянуть на это по-другому ... наибольшее простое число, меньше равно 31607, для общего числа 3401 простых чисел от 2 до 31607, что не очень большое число. Напишите каждое из чисел, которое вам дано, с полным множителем над простыми числами до 31607: Здесь - 1 или большое простое число. Тогда набор относительно прост, если соответствующие векторы линейно независимы (а их s разные или оба равны 1), и вы ищете ранг матрицы.109−−−√
источник
Если вы можете найти подмножество с gcd (S) = 1, то я всегда могу удалить избыточные элементы из подмножества, пока не останется только 2 элемента, которые имеют gcd (S) = 1. Поэтому я могу утверждать, что либо наименьшее Подмножество будет содержать 2 элемента или не будет существовать.
Теперь мы используем рекурсию для решения этой проблемы. Давайте разделим массив чисел на 2 части, одну с n-1 элементами и одну с 1 элементом (последний элемент). Либо 2 числа будут в первых n-1 элементах, либо один элемент будет в 1-й части в паре с последним элементом. Поэтому мы можем решить эту проблему в
T (n) = T (n-1) + O (n) время. что означает T (n) = O (n ^ 2).
источник