Управляющее резюме
С учетом вводом k
, найти разбиение чисел 1
на n
в k
свободных от сумм , подмножеств крупнейшего n
вы можете в течение 10 минут.
Фон: числа Шура
Множество A
является свободным от суммы, если его самосумма A + A = { x + y | x, y in A}
не имеет общих с ним элементов.
Для каждого положительного целого числа k
существует наибольшее целое число S(k)
, так что набор {1, 2, ..., S(k)}
может быть разбит на k
подмножества без суммы. Это число называется к - й номер Щур (OEIS A045652 ).
Например, S(2) = 4
. Мы можем разделить {1, 2, 3, 4}
как {1, 4}, {2, 3}
, и это уникальное разделение на два подмножества без суммы, но мы не можем теперь добавить ни 5
к одной из частей.
Вызов
Напишите детерминированную программу, которая выполняет следующее:
- Возьмите положительное целое число в
k
качестве входных данных - Записать текущую метку времени Unix в стандартный вывод
- Выводит последовательность разбиений
1
ton
вk
подмножества без суммы для увеличенияn
, следуя каждой последовательности с текущей временной меткой Unix.
Победителем станет программа, которая распечатает самый большой раздел в n
течение 10 минут на моем компьютере при наличии ввода 5
. Связи будут разорваны в самое быстрое время, чтобы найти раздел для самого большого n
, усредненного за три запуска: поэтому выходные данные должны включать временные метки.
Важные детали:
- У меня Ubuntu Precise, поэтому, если ваш язык не поддерживается, я не смогу его оценить.
- У меня есть процессор Intel Core2 Quad, поэтому, если вы хотите использовать многопоточность, нет смысла использовать более 4 потоков.
- Если вы хотите, чтобы я использовал какие-либо конкретные флаги или реализацию компилятора, запишите это в своем ответе.
- Вы не должны использовать специальный код для обработки ввода
5
. - Вы не обязаны выводить каждое улучшение, которое найдете. Например, для ввода
2
вы можете вывести только разделn = 4
. Тем не менее, если вы ничего не выводите в первые 10 минут, я оцениваю это какn = 0
.
источник
n=59
, а сортировка по наибольшему количеству разрешенных чисел меньше, чемnextN
даетn=64
. Сортировка по длине списка запрещенных номеров (который может иметь повторы) очень быстро приводит к элегантномуn=30
шаблону.Tue Nov 10 00:44:25 2015
), но я виделn=92
менее чем за 2 секунды.ctime
более ,time
потому что выход был симпатичнее , когдаtime
было именно то , что я должен выбрал.n=121
. oOPython 3, 121, <0,001 с
Улучшенная эвристика благодаря Мартину Буттнеру означает, что нам даже не нужна случайность.
Выход:
Код:
Питон 3, 112
Сортировать по сумме первых 2 элементов + перекос
Я скопировал структуру данных El'endia Starman, которая состоит из списка пар, где первый элемент пары - это элементы этого сегмента, а второй - суммы этого сегмента.
Я начинаю с того же подхода «отслеживать, какие суммы имеются». Моя эвристика сортировки - это просто сумма наименьших двух элементов в данном списке. Я также добавляю небольшой случайный перекос, чтобы попробовать разные возможности.
Каждая итерация просто помещает каждое новое число в первую доступную корзину, подобно случайному жадному алгоритму. Как только это не удается, он просто перезапускается.
источник
Java 8, n =
142144Последний вывод:
Выполняет случайный поиск с разбивкой по четырем потокам. Когда он не может найти подходящий раздел,
n
он пытается освободить место дляn
одного раздела за один раз, выгружая как можно больше из него в другие разделы.редактировать: подправлен алгоритм освобождения места для
n
, также добавлена возможность вернуться к предыдущему выбору и выбрать снова.примечание: выходные данные не являются строго детерминированными, поскольку в них задействовано несколько потоков, и они могут в конечном итоге обновить лучшее из
n
найденных на данный момент в беспорядочном порядке; окончательная оценка 144 является детерминированной и достигается довольно быстро: 30 секунд на моем компьютере.Код является:
источник
C, Случайный Жадный, n = 91
Просто чтобы обеспечить базовое решение, он выполняет итерацию
n
, отслеживая ячейки и их суммы и добавляетn
к случайной ячейке, где она еще не отображается как сумма. Он завершается, как толькоn
появляется во всехk
суммах, и если результатn
был лучше, чем любая предыдущая попытка, печатает его в STDOUT.Ввод
k
осуществляется через аргумент командной строки. Максимально возможное значениеk
в настоящее время жестко задано равным 10, потому что мне было лень добавлять динамическое выделение памяти, но это можно было легко исправить.Я думаю, я мог бы сейчас пойти на охоту за лучшим семенем, но этот ответ, вероятно, в любом случае не особенно конкурентоспособен, так что
Вот раздел для
n = 91
:И, наконец, вот код:
источник
n=91
, найдено за 138 секунд. Если это необходимо для разрыва связи, я сделаю время заново, чтобы избежать больших ошибок из-за разной загрузки процессора.С ++, 135
Добавляет следующие n к случайно выбранному подмножеству. Если это невозможно, он удаляет случайные числа из подмножеств и добавляет их к другим в надежде, что это позволит добавить n где-нибудь.
Я прототипировал его в awk, и, поскольку он выглядел многообещающе, я перевел его на C ++, чтобы ускорить его. Использование
std::set
должно даже ускорить его больше.Вывод для n = 135 (примерно через 230 секунд на моей [старой] машине)
Я не перепроверил действительность, но все должно быть в порядке.
источник
Python 3, случайный жадный, n = 61
Последний вывод:
Это эффективно использует тот же алгоритм, что и у Мартина Бюттнера , но я разработал его независимо.
Есть
k
корзины, в которых есть как числа, так и числа, которые больше не могут быть в нем. На каждой глубине итерации (это, в основном, поиск по глубине), порядокnextN
бинов перемешивается, а следующее число ( ) (последовательно) помещается в бункеры, которые могут его принять, а затем идет на один шаг глубже. Если их нет, он возвращается, резервируя один шаг.источник
Python, n = 31
Хорошо, так что это, конечно, не победитель, но я чувствовал, что все равно здесь. Я взял на себя смелость не включать временные метки, так как они заканчиваются мгновенно, и поскольку это не настоящий претендент.
Во-первых, обратите внимание, что сумма любых двух нечетных чисел четна, поэтому мы можем вывести все нечетные числа в первом блоке. Затем, поскольку все оставшиеся числа четные, мы можем разделить их на 2. Еще раз, мы можем бросить все результирующие нечетные числа во втором блоке (после повторного умножения их на 2), разделить оставшиеся числа на 2 (т.е. , на 4 в целом), выбросить нечетные в третьем блоке (после повторного умножения их на 4) и так далее ... Или, чтобы выразить словами, которые вы, ребята, понимаете, мы ставим все числа, чей наименее значимый набор бит - это первый бит в первом блоке, все числа, младший значащий бит которого установлен во втором бите во втором блоке и т. д.
Для k блоков мы сталкиваемся с проблемой, как только мы достигаем n = 2 k , поскольку младший значащий установленный бит n является
( k + 1) -м битом, который не соответствует ни одному блоку. Другими словами, эта схема работает до
с п = 2 к - 1. Итак, в то время как для к = 5 мы только получаем мизерный п = 31 , это число растет экспоненциально с ростом к . Также установлено, что S ( k ) ≥ 2 k - 1 (но мы можем действительно найти лучший нижний предел, чем это довольно легко.)
Для справки вот результат для k = 5:
источник
[1], [2,3], [4,5,6,7], ...
, что, вероятно, проще, только с обратным битом и порядком блоков. Легко увидеть, как это можно расширить.