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

Итоговые таблицы участников

Задача 1

Победитель — Ivan Krasilnikov — поделился исходниками своего решения этой задачи.

  1. Ivan Krasilnikov :: n = 14 :: 400 ядер (2.83 GHz) :: 30 м.
  2. santeri :: n = 7 :: 1 ядро (2.26 GHz) :: 1 м. 45 с.

Задача 2

Хотя задача была снята с конкурса, победителем объявляется участник kobra, отыскавший наиболее быстрое решение (которое не является формулой). Он пользовался материалами этой статьи.

  1. kobra :: n = 25 :: 1 ядро (2.40GHz) :: 15 с.
  2. Ivan Krasilnikov :: n = 14 :: 1 ядро Xeon E5620 @ 2.40GHz :: 8 ч.
  3. ijrandom :: n = 7 :: 1 ядро (2 GHz) :: 23 с.
  4. Vitaliy Pronkin :: n = 4 :: 1 ядро (2.16 GHz) :: 10 с.

Задача 3

Победителем снова оказался Ivan Krasilnikov. Можете ознакомиться с его решением.

  1. Ivan Krasilnikov :: n = 15 :: 21 ядро E5620 :: 4238 с.
  2. prima :: n = 7 :: 1 ядро Core2Duo @ 2.66 GHz :: 104 м.

Некоторые рассуждения с позиции организатора

Задача 1. 3n

Большая часть участников (если судить по комментариям на странице конкурса и на страницах, где я оставлял объявления) пытались решить именно её. Причем, по-видимому, никто не реализовал какой-либо метод, который был бы более эффективным, чем простой перебор. По правде говоря, я даже не пытался этим заниматься, а сама задача для меня интереса не представляет. Не знаю, оказалась ли она для кого-либо из участников полезной, но я предложил её в конкурсе лишь по одной причине – чтобы увеличить число желающих участвовать. Я хочу найти некую, если можно так выразиться, «формулу» проведения конкурсов, после которой можно будет делать данное мероприятие массовым и широко известным. Поэтому пока в ход идут любые задачи, ответы к которым я в сети не находил.

Обратите внимание, что в этой задаче требовалось искать «не меньше» n нулей. Поэтому последовательность ответов будет (не строго) монотонной. В энциклопедии похожие задачи требуют искать «ровно» n цифр (например, n восьмерок), поэтому последовательность ответов в этом случае не обязательно будет монотонной.

Несколько расстроило то, что был всего один (явный) участник на CUDA. Но видеокарта у его ноутбука была не такая сильная, как на почти любой персоналке. Вообще, с CUDA очень странная ситуация, особенно на фоне разного рода заявлений в сети типа «GPU = смерть CPU» и прочей ерунды. Да, было дело, что число расстановок 26 ферзей на доске 26×26 (это пока мировой рекорд) посчитали на GPU, но можете быть уверенными, что она все равно не переплюнет обычный 4-12 ядерный процессор. Ну, это ИМХО. В любом случае, мне лично не удавалось сделать так, чтобы одна видеокарта из 128 ядер считала быстрее 4 ядер CPU. А чем дорогую видеокарту покупать, дешевле еще пару настольных ПК найти. Пусть даже и БУ. Да и сейчас, в принципе, доступ к игрушечному кластеру для многих открыт, многие университеты начинают закупать такие машины. Хм… а может конкурс по CUDA потом сделать?

Задача 2. Димеры на цилиндре

Участники конкурса имеют полное право обвинить меня в незнании классических результатов из области перечислительной комбинаторики. Я, конечно, знал, что задача допускает аналитическое решение, но не потрудился проверить, действительно ли оно уже было найдено. Оказывается, было… почти 40 лет назад. И подвело меня то, что я слишком доверился энциклопеции OEIS, где этой последовательности нет. «Ну нет и нет», — подумал я — и ошибся.

Сначала я было решил, что участник kobra нашел эту формулу и воспользовался ею, однако он решал задачу с помощью решения, ссылка на которое дана выше в итоговой таблице. Поскольку цилиндр с чётным периметром будет двудольным графом, можно свести задачу к подсчёту паросочетаний в нём. Затем задача сводится к отысканию определителя (точнее, квадратного корня из него).

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

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

Задача 3. Статистика циклов на квадратной решетке

С такого рода задачами я хорошо знаком. До начала конкурса я даже не потрудился начать считать ответы, так как был уверен, что успею в любом случае. В общем, так и получилось. Даже ответ для решетки 16×16 получить было не слишком сложно и 4 Гб памяти для этого за глаза хватило. Я считал на кластере, но результат для n=15 можно было получить на персоналке за 36 часов, потратив меньше 0.5 Гб памяти. То есть я не могу согласиться с теми участниками, которые могут поспешить обвинить меня в том, что задача без кластера не решается. Причём я даже сразу могу сказать, что моя реализация не самая аккуратная. То есть, как минимум в 3 раза ускорить можно, но мне не хочется этим заниматься.

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

Ответы до n=16 можно посмотреть в файле GridResults.txt

Что дальше?

Как я уже сказал выше, я хочу отыскать «формулу» для проведения такого рода конкурсов по труднорешаемым задачам. Разные подходы вызывают разные реакции. Приходят замечания участников о том, что им бы хотелось видеть по-другому. И правда, с одной стороны хорошо было бы отображать полное название процессора участников, с другой, это не нужно, когда разница между временем работы составляет несколько минут (или часов), как в других конкурсах. В следующий раз я попробую провести конкурс на одной машине. Причём конкурс будет по параллельным алгоритмам, но пока не знаю, делать его на CUDA или на кластере. В следующем конкурсе все программы участников будут компилироваться и запускаться на одной и той же архитектуре. Конечно, это сильно ограничит круг возможных компиляторов и способов написания кода. Со временем, когда будет найден оптимальный способ проведения таких конкурсов, я сделаю отдельный ресурс. А пока все будет на этом блоге.

Всем спасибо за явное и неявное участие. Приходите ещё. Подписывайтесь на RSS или на рассылку по почте, чтобы не пропустить очередной конкурс. Я далеко не всегда буду давать объявления на форумах и блогах, так как очень надоедает война с хомяками, троллями и прочей живностью, которая думает, что я только ради пиара этим занимаюсь или курсовую сдать хочу, получив программы участников. В общем, воевать надоедает. Даже FAQ помогает не так хорошо, как хотелось бы.

До следующего конкурса! Когда? Не раньше Нового Года.

Обсуждение конкурса на форуме в этой теме.