Конкурсы

Бессмыслица — искать решение,
если оно и так есть.
Речь идет о том, как поступать с задачей,
которая решения не имеет.

А. и Б. Стругацкие,
«Понедельник начинается в субботу».

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

Список конкурсов

Список уже проведённых и текущих конкурсов, к которым я имею отношение.

  1. Быстрое перемножение матриц [ 08.02.2010 – 22.02.2010 ]. Итоги.
  2. 6 ферзей [ 12.04.2010 – 10.05.2010 ]. Итоги.
  3. Предгамильтоновы циклы на решётке [ 01.10.2010 – 31.10.2010 ]. Итоги.
  4. Три в степени n, димеры на цилиндре и статистика циклов [ 21.11.2010 – 07.12.2010 ]. Итоги.
  5. Решение целочисленной системы линейных уравнений [ 01.02.2011 – 10.02.2011 ]. Итоги.
  6. Максимальный поток, баян и блуждания на прямой [ 01.03.2011 – 14.03.2011 ]. Итоги.
  7. Статистика распределения циклов [ 10.04.2011 – 24.04.2011 ]. Итоги.
  8. 6 ферзей на тороидальной доске [ 09.06.2011 – 21.06.2011 ]. Итоги.
  9. Задача о назначениях [ 01.10.2011 – 15.10.2011 ]. Итоги.
  10. Обратная по модулю матрица [ 04.04.2012 – 18.04.2012 ]. Итоги.

FAQ

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

  1. Что за тупой конкурс? Ответом на этот и подобные вопросы будет «идите нафиг».
  2. Это «баян». В Интернете полно исходников, мы в школе ещё эту задачу делали. Ответ: Нет, в Интернете нет исходников, которые хоть сколько-нибудь приемлемо решают данную задачу. Вы ошибаетесь и путаете мою задачу с какой-то другой.
  3. Это «замануха». Автор раскручивает свой сайт, задача тупая, а денег мало. Ответ: нет, это самый настоящий конкурс, если бы я хотел раскручивать сайт, то на те же деньги больше толку было бы от купленных баннеров и ссылок. Если задача Вам кажется тупой, значит она не для Вас и Вы не понимаете её смысла. Денег мало, но сколько есть.
  4. Вы правда думаете, что за такие деньги люди сразу побегут к вам писать программы? Ответ: не нравится — не участвуйте. Конкурс не для всех, а для тех, кому интересно решать трудные задачи. Мне думается, что промышленные программисты и web-программисты не должны тратить на это время.
  5. Автору просто нужно защитить курсовую, вот он и ищет дешёвую рабочую силу. Ответ: во-первых, мне не нужно защищать курсовые, коль скоро я уже несколько лет как преподаватель университета. Во-вторых, рабочая сила тех, кто высказывает подобные соображения, как правило, и так дешёвая во всех смыслах этого слова. Обратите внимание на то, что я стараюсь организовывать конкурсы максимально правильно, чего совершенно не наблюдается в случае поиска халявы.
  6. Я 5 (10, 50, 100, 800) лет работаю программистом и понятия не имею как решать эту задачу. Ответ: программисты бывают разными, например, web-программисты и т. д. Конечно же, если Вы не понимаете в чем состоит задача и почему в ней надо думать — это конкурс не для Вас. Это для тех, кто умеет писать оптимальный код для вычислительных задач, то есть для тех, кто на этом специализируется. Конечно же этим конкурсом я не хочу обидеть остальных программистов, которые сильны в какой-то своей области. Это просто не для них и всё.
  7. Как Вы собираетесь проверять ответы на задачи, которые ещё никто, включая Вас, не решил? Ответ: из общих соображений. В таких задачах всегда существуют косвенные методы проверки. По крайней мере, с большой вероятностью можно сказать приближённый ответ, учитывая специфику задачи. Если повезёт, ответ предсказывается с точностью до тысячных долей процента.