Конкурс по обращению матрицы завершён. Победителем объявляется неоднократный участник моих конкурсов alexBlack.

После вынужденного перерыва продолжаем проводить любительские конкурсы по программированию. На этот раз конкурс связан с одним из предыдущих конкурсов, посвященных точному решению целочисленной системы уравнений. Первым шагом при использовании алгоритма, основанного на p-адических аппроксимациях, является обращение исходной матрицы по модулю простого числа P. Требуется максимально ускорить эту операцию. С этой целью и проводится конкурс. В качестве P выбрано число 2³¹-1 (максимальное простое число, которое умещается в 32 бита со знаком).

Конкурс на самое быстрое решение задачи о назначениях завершён. Подведём итоги.

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

Недавно Vaclav Kotesovec написал мне письмо, в котором предложил продолжить его новую последовательность A137432 — число способов расставить максимальное количество (n²) не бьющих друг друга королей на цилиндрической доске 2n×2n.

Конкурс завершён досрочно, поскольку Андрей Халявин предоставил необходимое количество чисел (и даже больше – 81 шт.), которых оказалось достаточно для проверки гипотезы. Здесь я объясню, что из этого всего получилось. Забегая вперед сообщу, что гипотеза о виде рекуррентного соотношения хоть и была правильной, но соотношение имело не минимальный порядок. Минимальный порядок будет 124, а не 142. Так же я объясню, как из 142 получить 78 для этой задачи, благодаря чему и удалось решить её так быстро. Для понимания объяснений читатель должен быть немного знаком с производящими функциями.

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

Меня часто спрашивают о том, как можно вывести огромную формулу в несколько тысяч слагаемых, которая является решением той или иной трудной задачи. Как вообще действовать, чтобы вывести формулы длиной свыше 10000 слагаемых, о которых рассказывается, например, здесь? На самом деле, во-первых, все эти формулы не выводятся, а «угадываются», а во-вторых, в ряде случаев это делается тривиальным образом. Хотя бывают и чрезвычайно сложные ситуации. Здесь я расскажу о самых простых примерах, так сказать, для начала. Речь пойдёт пока только о линейных рекуррентных соотношениях с постоянными коэффициентами.

Конкурс по распараллеливанию алгоритма задачи о подсчёте статистики распределения циклов по длинам завершён. Подведём итоги.

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