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

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

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

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

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

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

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

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

Конкурс про баян завершён и я, как обычно, позволю себе высказать собственные соображения о том, что происходило. Для начала хочу прояснить один момент: в некоторых местах я пишу, что задачи сложные (и что их с наскока не решить), а в других местах я много раз указывал, что задачи 1 и 3 являются халявой, при этом сложной я называл только задачу 2. Казалось бы, что я сам себе противоречу. А на самом деле имеется в виду следующее (на примере задачи 3): решить задачу 3 сложно в том смысле, что для неё сложно отыскать решение для достаточно большого входного параметра k. А простая она в том смысле, что для многих начальных значений k=5,6,7 (с которых предлагалось начать) и даже, наверное, k=8 эта задача решается тривиально. То есть принять участие в конкурсе мог любой человек, кто понял смысл прошлого конкурса — про решение целочисленных систем линейных уравнений. Теперь давайте по порядку.

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