Конкурс на самое быстрое решение целочисленной системы линейных уравнений завершён. Вынужден признать, что это был самый скучный конкурс из всех, которые я проводил. Было довольно много участников, но у половины программы работали неправильно, а у остальных – слишком медленно и не укладывались в 600 с. Как минимум, предполагалось, что кто-то дойдёт то отметки в 5-10 с, но, к сожалению, этого не произошло. Значит я вынужден буду объяснить, как этого добиться. В этом посте подведём итоги, и я выскажу мои мысли по поводу данного мероприятия, а в следующем ждите подробного описания нормального метода решения поставленной задачи.

В честь дня рождения моего блога предлагаю принять участие в очередном любительском конкурсе для программистов-математиков. Я обещал в прошлый раз, что конкурс будет по параллельным вычислениям, однако по техническим причинам его придётся пока отложить на неопределённый срок. Вместо этого будет простой конкурс с простой (с точки зрения теории сложности) задачей.

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

Предлагаю принять участие в новом конкурсе для любителей трудных вычислительных задач. На этот раз призового фонда не будет по причинам, объявленным в итогах предыдущего конкурса. И моего участия тоже не будет, так как предлагаемые задачи я уже решал и знаю ответы для достаточно больших значений входных параметров. В рамках конкурса предлагается решать три задачи, чтобы увеличить число участников. Почему «решать», а не «решить»? Потому что решить их (то есть предложить алгоритм, выдающий ответ для любых значений входных данных) вряд ли получится. Поэтому побеждает тот из участников, который решит частные задачи для как можно большего значения входного параметра. У каждой задачи будет свой победитель.

На этот раз конкурс получится по принципу «кто первым встал, того и тапки». Действительно, тов. alexBlack быстро представил ответы для достаточно больших значений n, практически не оставив шансов другим участникам. А я окончательно лишил их шансов, поскольку пошёл считать на кластере. В этой задаче переход к следующему числу в 20-30 раз усложняет вычисления, поэтому, ухватившись за результат для n=10, я вынудил потенциального соперника придумывать алгоритм, в 20-30 раз эффективнее моего.

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

Это третий конкурс. Призовой фонд 3000 р. (на два призовых места: 2000 р. + 1000 р.). Задача следующая. Имеется квадратная решётка с нечётным числом вершин. Сколько на ней существует простых циклов с максимальной длиной?

Итак, конкурс завершён, мне удалось вывести формулу. Строгое доказательство формулы возможно, если посчитать примерно 144 значения, но на это у меня не хватит вычислительной мощности. Однако формула почти наверное верна, тому есть косвенные доказательства, которые будут представлены в конце. Вместе с формулой были также получены производящая функция и рекуррентное соотношение.

Продолжаю делать конкурсы для программистов-математиков. Это второй конкурс. Предыдущий был посвящён перемножению матриц, и результатами я был очень доволен. Судя по отзывам, некоторые участники тоже. На этот раз задача чуть сложнее, а призовой фонд 3000 р. (на два призовых места). Задача довольно специфическая: сколькими способами можно расположить на шахматной доске размером n×n шесть не бьющих друг друга шахматных ферзей? Предупреждаю, решать эту задачу «в лоб» не получится, конечно, если у Вас нет под рукой мощного кластера. Но если Вы хорошо разбираетесь в переборных задачах, то участвуйте!

Итак, конкурс по перемножению матриц, в котором нужно было перемножить две матрицы размером 5000×5000, завершён. Спасибо всем участникам, благодаря им я узнал много нового: конкурс заставил меня делать такие вещи, в которые я сначала не верил или в которых не разбирался. Здесь я напишу несколько итоговых комментариев и выложу архив с решениями и тестами.

На своем блоге я буду проводить много конкурсов, связанных (прямо или косвенно) с научными задачами. Конкурсы будут как с платным, так и с бесплатным участием. Это первый конкурс, и чтобы не распугать людей, он будет с бесплатным участием, но и призовой фонд будет не слишком большим — 1000 р..