Конкурс для программистов - предгамильтоновы циклы

[Zealint]

Модераторам: форум указан на странице конкурса в качестве информационного спонсора. Прямая индексируемая ссылка сделана

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

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

PS. Прежде чем Вы захотите выразить своё мнение, убедитесь, пожалуйста, что оно не присутствует в FAQ по конкурсам.

Удачи!

[Zealint]

Я опубликовал на Хабре свой подход к решению поставленной задачи.

[Tronix]

Это конечно все хорошо, но я не думаю, что многие здесь обладают мощностями в 64 ядра (2,6 GHz) (судя по предыдущим вашим конкурсам), а значит заведомо проигрывают вам, используя традиционный подход для решения такого типа задач. Даже если придумать что-то сверх-новое и оптимизированное, то все равно вы на 64 ядрах тупо брутфорсом быстрее переберете, чем я скажем на amd athlon xp 1800 со своим мега-алгоритмом

[Zealint]

Вы не совсем правы. Во-первых, мощность ещё не означает, что мой подход будет быстрее, чем подход других участников. Во-вторых, на моём кластере мало памяти, то есть все 64 ядра работать не будут. В-третьих, я не запрещаю остальным пользоваться кластером МГУ, например, который заведомо мощнее. В-четвёртых, я пока лидирую без кластера.

Не вижу здесь ничего нечестного...

Даже если придумать что-то сверх-новое и оптимизированное, то все равно вы на 64 ядрах тупо брутфорсом быстрее переберете, чем я скажем на amd athlon xp 1800 со своим мега-алгоритмом

Ничего подобного. Можете собрать все компьютеры Планеты и попытаться брутфорсом посчитать ответ хотя бы для n=5. До конца конкурса не успеете. Ручная оптимизация такого рода задач допускает ускорение в десятки раз, в прошлом конкурсе тов. alexBlack меня долгое время выигрывал, считая на двух ядрах, пока я считал на 64, потом я написал более совершенный алгоритм, который можно было и на 1 ядре быстро гонять, но я хотел скорее получить ответ...

[Simply-Art]

Только увидел тему. Возник вопрос, данные по n=1...3 верны на 100%?

1. 5
2. 226
3. 255088

[Zealint]

Сообщение от Simply-Art

Только увидел тему. Возник вопрос, данные по n=1...3 верны на 100%?

Да, эти данный были получены 3-мя независимыми людьми. Две мои программы выдали тоже точно такой же результат. Первое число вообще можно вручную проверить.

[Zealint]

Конкурс завершён, с результатами можно ознакомиться на странице результатов.

[Tronix]

Даже не смотря на отрык сcылку, рискну предположить, что победили в этом конкурсе Вы, использовав эндцать процессоров и их память. Ну и ЧТД как говорят математики.

[Zealint]

Иногда бывает такое, что человек не воспринимает логические аргументы. Ну да ладно, это нормально. Еще раз напомню, что победил без использования кластера. С помощью него я только добавил одно число, когда победа уже была за мной. Что-то с моей стороны осталось необъясненным, тов. Tronix?

[Alar]

Zealint, надо вводить было больше чем один приз.