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

Результаты

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

Таблица участников

  1. Zealint :: 18.10 :: n = 10 :: 8 ядер (2.67 GHz) :: 6 д. 7 ч. 27 мин.
  2. alexBlack :: 06.10 :: n = 8 :: 1 ядро (2.9 GHz) :: 200 мин.
  3. Silent :: 04.10 :: n = 3 :: 1 ядро (2 GHz) :: 20-40 мин.

Таблица значений

Таблица значений n и количества циклов длиной (2n+1)2-1 на решётке размером (2n+1)×(2n+1).

  1. 5
  2. 226
  3. 255088
  4. 6663430912
  5. 3916162476483538
  6. 51249820944023435573470
  7. 14870957102232406137455708164254
  8. 95494789899510664733921727510895952184006
  9. 13559554600804304977439766815372028940021573343275526
  10. 42557777273614434293884765869188518513149602332875710275078966598

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

Проблемы

Проводя конкурсы, я сталкиваюсь с некоторыми проблемами общего характера.

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

Задачи, которые я предлагаю, носят весьма специфический характер (кроме первого конкурса). Нужно получить некий ответ, который гарантированно нельзя отыскать в интернете и при этом мне не важно, как участники этот ответ получили. Задачу я стараюсь выбирать так, чтобы гарантировать, что ответ смогу проверить на правильность с высокой вероятностью. Почему так приходится делать? Чтобы не ограничивать участников операционной системой, средой программирования, языком программирования и всем остальным. В первом конкурсе, например, все были сильно ограничены условиями. Мне поступали многочисленные жалобы от любителей Linux, от специалистов по параллельным вычислениям, которым так сильно хотелось задействовать два ядра вместо одного, от программистов на CUDA, которым покоя не давало желание погонять видеокарту и т. д. Всем не угодишь. А теперь проблема решена, считайте хоть на самом быстром в мире суперкомпьютере, если у вас есть к нему доступ. Думаете это нечестно? Честно, так как это КОНКУРС, и если у программиста есть некий мега-инструмент и в жизни он может им пользоваться, то почему не может на конкурсе? Никаких ограничений быть не должно, кроме самых естественных.

Ещё одна проблема носит очень яркий характер. К сожалению, далеко не все программисты (даже с высшим образованием) в состоянии понять формулировку такой труднорешаемой задачи. Даже не они в этом виноваты, а виновато то обстоятельство, что математические дисциплины совершенно урезали там, где они раньше были. Теперь при подготовке IT специалиста, программиста или кого-то похожего во многих университетах уже не проходят фундаментальные математические дисциплины, а заменяют их беглым пролистыванием учебника. Даже элементарная комбинаторика находится на грани понимания такими специалистами. К сожалению. Вот поэтому я вынужден везде делать предупреждение о том, что задачи сложные, что участвовать рекомендую только тем, кто математику изучал. Кого интересует именно программирование, для тех существуют огромные архивы задач для программистов (хотя и там попадаются очень тяжелые задачи), например, acm.sgu.ru или acm.timus.ru.

Когда следующий конкурс?

Следующий конкурс я попытаюсь сделать на основе более простых задач. Возможно, их будет несколько. Но приза не будет. Проверим, сколько людей захотят участвовать. Задачи, разумеется, тоже будут очень узкоспециализированными. Но состоится это мероприятие не раньше 15 ноября 2010 года. А скорее всего даже позже.

Что будет дальше?

Дальше будет хуже. Для меня. На бесплатных конкурсах далеко не уйти, не думаю, что это станет сильно популярным. Нужны деньги и нужно много. У меня есть задачи, за решение которых на Западе выдают солидные гранты, а в России только шиш. При этом сильные программисты в России оказываются гораздо умнее тех, что на западе (хотя тоже не всегда, есть примеры и того и другого). Поэтому давать людям сверхтяжелые задачи и говорить, что они решают их только для себя как-то неправильно. Особенно это неправильно, когда получаемые на конкурсе результаты превосходят результаты западных учёных, печатающихся в солидных журналах, рейтинг которых больше суммарного рейтинга всех более-меннее престижных журналов России.

Поэтому надо искать деньги, а искать я их будут в Интернете. Кое-какие знания по этому вопросу у меня имеются, поэтому несколько ближайших постов будут посвящены именно этой теме – зарабатывание в интернете. Если повезёт, то к началу следующего учебного года я смогу увеличить призовой фонд до тысячи долларов. Уже вроде бы привлекательно, да?

Всем спасибо за участие (явное и неявное), ждите середины-конца ноября или начала декабря. Как-то так.

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