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

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

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

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

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

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

В первой части статьи речь шла о том, как учёные пудрят мозг обычным людям. На самом деле, целенаправленных методов введения в заблуждение в науке существует очень и очень много. Но в статье речь шла о несознательных заблуждениях, то есть когда ученые, подверженные материалистическим представлениям (считая, что абсолютно всё в мире происходит по объективным, не зависящим от сознания законам) и не желающие учиться думать более широко, просто делают свою работу. А желающая новых «знаний» и «объяснений» всех в Мире проблем публика проглатывает результат творчества ученых не задумываясь. Когда к этому примешивается еще и нежелание самой публики включать мозг, получается ещё более вульгарный материализм (ВМ). Вот об этой публике теперь пойдёт речь. Какое отражение вульгарный материализм находит в повседневной жизни? В основном, здесь будут собраны типичные примеры ВМ, многие из которых любой найдёт в своей жизни. Дальше воинствующим сторонникам «научных» материалистических представлений читать запрещается.

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

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

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

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