Prime Sums

[tolstopuz]

Nataly-Mak в сообщении #631848 писал(а):

tolstopuz, это вы?

Да. Решил слегка почесать свой кластер, но серьезно заниматься задачей вряд ли буду.

[Pavlovsky]

Получить результат 498 для N=5, по представленной выше схеме невозможно. Делаем небольшое отступление. Будем искать минимум равный 500.

[Nataly-Mak]

Ищите сразу минимум 502
Это вернее всего. Я почти уверена, что для N=5 502 является минимумом.
Для кластера квадрат 5х5 не проблема, полный перебор сделает за 5 минут.

[dimkadimon]

Nataly-Mak в сообщении #631925 писал(а):

Для кластера квадрат 5х5 не проблема, полный перебор сделает за 5 минут.

Не правда. Полный перебор ето 25! - огромное число, которое никакой кластер не возьмет!

[Pavlovsky]

Результат пока не важен. Ищу критерии возможности (невозможности) заполнить квадрат, по заданным заранее свойствам.



Утверждение. Минимально возможная сумма линии равна 1+2+3+9+10=25.
Утверждение. Максимально возможная сумма линии равна 7+8+19+20+21=75.

Все допустимые варианты суммы 498.
29,31,37,41,43,47,59,67,71,73 = 498
29,31,37,41,43,53,59,61,71,73 = 498
29,31,37,41,47,53,59,61,67,73 = 498
29,31,37,43,47,53,59,61,67,71 = 498

Заполнить две линии числами, по схеме, возможно с максимальной суммой 142. 142>67+71=138.
Заполнить три линии числами, по схеме, возможно с максимальной суммой 199. 199>=61+67+71=199.
Заполнить четыре линии числами, по схеме, возможно с максимальной суммой 256. 256<59+61+67+71=258.

[Nataly-Mak]

dimkadimon в сообщении #631932 писал(а):

Не правда. Полный перебор ето 25! - огромное число, которое никакой кластер не возьмет!

Ну так ведь не совсем же тупой перебор Оптимизации-то должны быть в любом переборе. Есть критерии отсечения заведомо неперспективных вариантов.

Так что, кластер возьмёт не только 5х5, он вон у венгра уже до N=29 взял
Конечно, не все у него точно максимумы и минимумы, но зато все рекорды.

[tolstopuz]

Nataly-Mak в сообщении #631938 писал(а):

Так что, кластер возьмёт не только 5х5, он вон у венгра уже до N=29 взял

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

-- Ср окт 17, 2012 13:11:16 --

Nataly-Mak в сообщении #631938 писал(а):

Конечно, не все у него точно максимумы и минимумы, но зато все рекорды.

Кстати, у него нет максимума для 6 и минимума для 7. Кластер дал сбой? :)

[dimkadimon]

Nataly-Mak в сообщении #631938 писал(а):

Конечно, не все у него точно максимумы и минимумы, но зато все рекорды.

Ето дело времени - многие его рекорды побиваемые. Тут дело не только в кластере. Кластер помогает, но не до такой степени. Нужна хорошая идея. Пока только у Pavlovsky есть хорошие идеи.

[Nataly-Mak]

tolstopuz в сообщении #631972 писал(а):

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

Не поняла - это вы о чём?
Я недавно решала задачу, в которой такой комбинаторный взрыв: 5^50 вариантов.
Ну и что? Умело составленная программа (правда, не мной), и задача решена на обычном домашнем компьютере всего за 269 часов.

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

Американцы ещё в прошлом веке нашли все классические магические квадраты 5-го порядка всего за 100 часов. Они разве не сделали полный перебор? Конечно, перебор должен быть оптимизирован; и в данной конкурсной задаче тоже, я же не говорю, что на кластер надо загрузить программу тупого перебора.

-- Ср окт 17, 2012 14:27:13 --

dimkadimon в сообщении #631974 писал(а):

Ето дело времени - многие его рекорды побиваемые. Тут дело не только в кластере. Кластер помогает, но не до такой степени. Нужна хорошая идея. Пока только у Pavlovsky есть хорошие идеи.

Ой, ну не смешите, пожалуйста, мои тапочки.
Кластер помогает именно до такой степени!
Найти рекорды почти для всех N за три дня. Это он на обычном домашнем компьютере нашёл, да?
Не спорю, что у него есть хорошие идеи. У меня они тоже есть (если я их не выкладываю, это не значит, что у меня их нет). Ну и что? Вот у меня программа крутится для N=6, постоянно выдаёт улучшения:
max: 1308,1340, 1348, 1380, 1388
min: 1302, 1280, 1200, 1160

Давайте поставим мою программу на кластер. Наверное, улучшения будут появляться побыстрее. Нет?
Дело времени? Разумеется! Только время будет очень разное на моём компьютере и на кластере.

-- Ср окт 17, 2012 14:35:31 --

tolstopuz в сообщении #631972 писал(а):

Кстати, у него нет максимума для 6 и минимума для 7. Кластер дал сбой? :)

Идея для данных N подкачала

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

26  5  1  32  36  30 
 11  7  14  18  22  25 
 29  31  35  2  6  10 
 13  17  33  23  8  19 
 12  3  20  24  15  27 
 16  28  9  4  34  21

При этом я реализовала в программе далеко не все свои идеи, написала её на скорую руку, так - тяп-ляп Потому что задача мне не интересна.

[tolstopuz]

Nataly-Mak в сообщении #631617 писал(а):

Вот этим и плоха данная задача, что решается она, в основном, не умом, а машиной.

Nataly-Mak в сообщении #631980 писал(а):

Умело составленная программа (правда, не мной), и задача решена на обычном домашнем компьютере всего за 269 часов.

Американцы ещё в прошлом веке нашли все классические магические квадраты 5-го порядка всего за 100 часов. Они разве не сделали полный перебор? Конечно, перебор должен быть оптимизирован

Вот этим и хороши данные задачи, что решаются они в основном не машиной, а умом. Если хорошим алгоритмом удалось сократить время выполнения, скажем, на 20 порядков (посчитайте сами размер тупого перебора $5^{50}$, скажем, по микросекунде на вариант), а кластером из 1000 машин еще на 3 порядка, то вы легко можете оценить, какой тут вклад сделан умом, а какой кластером.

[Nataly-Mak]

tolstopuz
вы говорите совсем о другом, я не понимаю, в чём вы меня хотите убедить.

Давайте так:
представим, что конкурсант №1 и конкурсант №2 имеют одинаковый ум. Оба они могут написать хорошую программу с замечательными идеями и блестящей реализацией (для одной и той же задачи). Представили такой вариант?

Далее: конкурсант №1 будет крутить свою программу на обычном домашнем компьютере (ну, вот как у меня, 2.4 Ггц, два ядра), а конкурсант №2 будет крутить свою программу на кластере.

Теперь скажите: кто из этих двоих конкурсантов получит больше результатов за меньшее время?

Понятная задачка?

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

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

-- Ср окт 17, 2012 15:32:24 --

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

dimkadimon в сообщении #631096 писал(а):

Пока что я вижу только один метод для её решения и он не очень интересный.

[dimkadimon]

Nataly-Mak в сообщении #632001 писал(а):

Теперь скажите: кто из этих двоих конкурсантов получит больше результатов за меньшее время?

Не забывайте что кроме Венгра есть еще 43 человека, которые коллективно могли бы взять больше рекордов. Кстати у других тоже могут быть кластеры. Факт что в основном рекорды принадлежат ему мне говорит о том что у него действительно лучше алгоритмы. Достаточно одной хорошой идеи чтобы ускорить метод во много десятков раз. Например мне недавно пришла идея которая позволила находить результат за 2 часа, когда раньше для него требовалось 3 полных дня!

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

[tolstopuz]

Nataly-Mak в сообщении #632001 писал(а):

Давайте так:
представим, что конкурсант №1 и конкурсант №2 имеют одинаковый ум. Оба они могут написать хорошую программу с замечательными идеями и блестящей реализацией (для одной и той же задачи). Представили такой вариант?

Не могу представить. Я четыре раза занимал первое место в Project Euler, хотя пишу на Python, который примерно в 100 раз медленнее C++. А много раз не занимал, потому что меня обгоняли другие люди, используя самые разные языки и самое разное железо. Из этого я делаю вывод, что все люди разные и в такого типа задачах разница в умственных усилиях важнее разницы в вычислительной мощности.

(Оффтоп)

Вон, скажем, задача 251. Не помню, когда именно задача была объявлена, но я отправил сообщение с решением в 9:03, Robert Gerbicz в 9:24, а следующий в 13:32.
Или задача 256. Я - 1:37, Loks - 1:57, Robert Gerbicz - 2:18, следующий - 3:37.
Или задача 295. Первые два места - Java, третье - C++, четвертое и пятое - Python. Время у всех от 3 до 4 с небольшим часов. А языки программирования отличаются по скорости в 100 раз!

[Nataly-Mak]

dimkadimon в сообщении #632008 писал(а):

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

Во-первых, у меня есть не только метод случайной генерации, это было в самом начале, и уже для N=5 я следом написала вторую программу, которая намного эффективнее случайной генерации.

Во-вторых, вы же сами писали (только что выше процитировала), что не видите в этой задаче интересных методов решения.

-- Ср окт 17, 2012 16:07:57 --

tolstopuz в сообщении #632009 писал(а):

Не могу представить.

Ну почему же? Я не говорю о всех людях сразу, а говорю только о двух конкурсантах.
И это представить вполне реально. Я могу назвать вам кандидатов с умом не хуже того венгра. Например, тот же А. Чернов, который победил в прошлом конкурсе.
Вот вам и два конкурсанта с одинаковым умом, то есть в такой степени одинаковым, что они способны сделать отличную программу. И что же мы видим: венгр на первом месте, а А. Чернов только на 5-ом. В чём же причина? И почему вы это не можете представить?

Давайте поставим программу А. Чернова на кластер (мою не будем ставить, она, конечно, плохая ). И на такой же точно кластер поставим программу венгра.
Прогоним обе программы. Помотрим на результаты!
Это тоже не можете представить?

А вот в прошлом конкурсе Чернову не нужен был кластер; как он писал в теме, у него вообще не было переборных алгоритмов. Вот тут были только умственные усилия, и он взял первое место! Без всяких кластеров, на обычном домашнем компьютере.

Кстати, у меня в прошлом конкурсе было 8-ое место, а в этом будет сорокпоследнее. А ум всё тот же

[Pavlovsky]

Что такое компьютер? Железяка. Интеллекта у него как у молотка. Думать за человека он не может!

tolstopuz в сообщении #631849 писал(а):

Решил слегка почесать свой кластер

Кластеры они не в туалетах. Кластеры они в головах. (С) профессор Преображенский.