Prime Sums

[dimkadimon]

Gerbicz в сообщении #639283 писал(а):

And he has an access to all grids. Very funny, but this was not in my head when written the post. Dmitry is a talented programmer, and has got two first top scores.

Just for the record, I don't have access to any grids. Only Neil has access. I found all the grids myself and I can show you my code to prove it.

-- 03.11.2012, 07:07 --

Gerbicz в сообщении #639206 писал(а):

There are different types of people, some of them can't think even for an hour on a problem and instead of that starts to steal and cheat codes/grids/ideas.

I agree with whitefox about this. In this competition most people are capable of thinking for themselves. People here are not chasing a "quick answer", they are not interested in ranks/ratings/prizes, or stealing codes/grids/ideas. People here enjoy problem solving, they are here to learn and have fun. Please don't compare this competition to others like TopCoder or Codeforces, where people care about rating and so cheating may be beneficial.

[svb]

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

Все просто, но вот, что делать с N=6,7?
Да и случайные решения для N=5 меня не очень радуют.

[Nataly-Mak]

svb в сообщении #639498 писал(а):

Да и случайные решения для N=5 меня не очень радуют.

Меня тоже
Вчера нашла максимум для N=5 - 790.
На минимуме зациклилась, 508 и меньше никак! Прогнала уже несколько десятков тысяч вариантов, и это не совсем тупой перебор, конечно, что-то осмысленное в нём присутствует. Но видимо мало осмысленного Всё мимо пока.
Вот получила в решении 790 такую конфигурацию:

0 0 3 3 2
1 2 3 4 3
2 1 2 1 2
2 2 1 1 2
2 2 3 3 3

Сейчас думаю: может ли эта конфигурация дать минимум?
Если просто распихать числа по множествам:

0 - {24,25}
1 - {23,22,21,20,19}
2 - {18,17,16,15,14,13,12,11,10,9}
3 - {8,7,6,5,4,3,2}
4 - {1}
и написать программу перебора по приведённой схеме...
Даст ли это что-нибудь?

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

Здесь о конфигурациях написано уже достаточно много. Но я пока не реализовала эти идеи. Как составлять оптимальные конфигурации, не знаю, не поняла ещё. Как подбирать множества чисел для этих конфигураций, тоже не знаю.
Надо думать, а много думать вредно - кластер болит

[Pavlovsky]

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

0 0 3 3 2
1 2 3 4 3
2 1 2 1 2
2 2 1 1 2
2 2 3 3 3

Параметры вашей схемы
min 484 max 816

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

0 - {24,25}
1 - {23,22,21,20,19}
2 - {18,17,16,15,14,13,12,11,10,9}
3 - {8,7,6,5,4,3,2}
4 - {1}

Такое распределение чисел по группам даст вам решение 484 (если сможете построить квадрат). Но если верить 20-ти участникам нашедшим решение 502 и не нашедшим решение меньше, такое невозможно. В силу вступают ограничения для маленьких N. Нам ведь нужны не абы какие суммы, а суммы ввиде простых чисел.
Значит числа по группам надо перераспределять. Например такое распределение
0 - {24,25}
1 - {23,22,21,20,19}
2 - {18,17,16,15,14,13,12,11,8,9}
3 - {10,7,6,5,4,3,2}
4 - {1}
Уже даст решение 486. Возникает задача перераспределения чисел по группам. Сергей Беляев об этой задаче уже писал. Правда как ее решить не написал.

-- Сб ноя 03, 2012 12:07:12 --

Для N=5 проанализировал несколько схем (естественно не все). Для всех этих схем набрать 10 простых чисел, сумма которых меньше 500 и отвечающих дополнительным условиям, невозможно.

[svb]

Я до сих пор нахожусь в отладочном режиме, т.е. постоянно модифицирую программы, тестирую - иногда находятся решения.

Начинал для знакомства с N=5. Вручную вписывал числа наборов и проводил перебор. Так как работа шла в интерактивном режиме, то при выборе чисел наборов присутствовал "человеческий фактор". При обобщении от этого пришлось отказаться и я пришел к парадоксальной ситуации: последний вариант с легкостью находит решения при N>7, но достаточно бестолков при меньших N. Необходим механизм модификации наборов, но "умный". "Глупый" я уже опробовал - программа часами работает, а я с грустью смотрю на это безобразие. Даже для N=5 отказывается работать. Меня это удивило и я посмотрел на старые тексты, оказалось, что для того, чтобы получать хоть какие-то результаты я объединял 0 и 1 наборы.

От N=5 у меня осталось стойкое впечатление, возможно ошибочное, что выбор конкретной схемы не критичен. Например, я об этом уже писал, результат 502 я получал для двух различных схем. Если уж для N=5 имеется достаточно большая свобода, то не приходится сомневаться, что для 6 и 7 ограничений еще меньше и новые рекорды еще впереди

[Herbert Kociemba]

I configured my program to find 3086 for N=7 yesterday evening and when I woke up this morning the solution was on the screen . My program for finding solutions for N=5,6,7 is absolutely dumb. No tree pruning, no annealing, just random pair swapping and of course a decision if to keep this swap or to undo it again. After a certain amount of swaps I just start all over again with another random scheme. I really wonder, why this works so well....

[Nataly-Mak]

Перестановка в группе лидеров:

Цитата:

2 Robert Gerbicz 49.995600 10-23-2012 @ 22:11:05
3 Wes Sampson 49.995600 11-02-2012 @ 03:40:31
4 Herbert Kociemba 49.995600 11-03-2012 @ 13:09:12
5 Serg Belyaev 49.994300 10-31-2012 @ 22:12:29
6 Alex Chernov 49.980700 11-03-2012 @ 12:00:59

Новая группа джентльменов с результатом 49,9956.
Как я понимаю, им не хватает минимума для N=7 (1808), который недавно нашёл dimkadimon. Кто первый найдёт?

Нашим, похоже, не хватает и минимума, и максимума
Ничего, всё ещё будет!

[Nataly-Mak]

Pavlovsky в сообщении #639528 писал(а):

Возникает задача перераспределения чисел по группам.

Ага, задача вполне понятная
Перераспределила числа по множествам так, чтобы можно было теоретически получить результат 502. Написала программу, программа мгновенно нашла результаты 510 и 508! А меньше опять нету
При этом программа выполнилась до конца, то есть она сделала полный перебор. Невероятно, но факт! Перебор с возвратом делает своё дело. 22 вложенных цикла!
Переменные циклов пробегают разное количество значений в зависимости от веса элемента, соответствующего этой переменной.
Всё прозрачно и понятно. Непонятно только: как составить оптимальную схему и как правильно распределить числа по множествам.

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

[Nataly-Mak]

Уф! Всё-таки я эту схему добила
Выжала из неё минимум 502. Стала 21 участником, нашедшим этот результат. А максимум есть уже у 22 участников.
Теперь у меня есть две единички - максимум и минимум для N=5.
Ну и хватит, пожалуй, единичек. Хорошего понемножку

[Gerbicz]

"Выжала из неё минимум 502. Стала 21 участником, нашедшим этот результат. А максимум есть уже у 22 участников."

That took very long time! Found it with paper and pencil, or with excel?

[Nataly-Mak]

Gerbicz в сообщении #639754 писал(а):

That took very long time! Found it with paper and pencil, or with excel?

Я не умею так быстро, как вы
"Я не гений, я только учусь"

[Nataly-Mak]

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

Кто будет первым джентльменом, набравшим 50 баллов при текущих рекордах?

Цитата:

2 Alex Chernov 50.000000 11-04-2012 @ 20:18:58

Алексей, весь мир видит ещё одну вашу победу!
Я очень надеюсь, что вы удержите её до конца конкурса. Удачи!

dimkadimon
вы всё ещё готовы поспорить?

По задаче такой вопрос: когда я искала минимум для N=5, у меня было очень много решений 508 и 510, но не было ни одного случая решений 504 и 506. Возможны ли такие результаты? Эмпирически я пришла к выводу, что невозможны, но это может быть ошибочный вывод.

-- Пн ноя 05, 2012 06:37:43 --

Gerbicz в сообщении #639754 писал(а):

Found it with paper and pencil, or with excel?

Забыла ответить на вопрос...
Я нашла минимум для N=5 с помощью бумаги, карандаша и Бейсика (пишу программы на QBASIC).

[dimkadimon]

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

вы всё ещё готовы поспорить?

А о чём спор? То что будет несколько 50.0 я уже не сомневаюсь. То что будет меньше 10ти людей с 50.0 я ещё готов поспорить ради интереса.

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

По задаче такой вопрос: когда я искала минимум для N=5, у меня было очень много решений 508 и 510, но не было ни одного случая решений 504 и 506. Возможны ли такие результаты?

504 есть, а вот 506 не видел.

-- 05.11.2012, 11:24 --

У меня есть интересный результат: 790 где 11 простых линий, но 10 уникальных как положено.

[Nataly-Mak]

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

А о чём спор? То что будет несколько 50.0 я уже не сомневаюсь. То что меньше 10ти людей с 50.0 я ещё готов поспорить ради интереса.

Ага, раньше вы писали, что конкурсантов с 50 баллами может быть даже меньше 5. Теперь уже 5 отпадает?
Я думаю, что и 10 таких конкурсантов вполне возможны, но утверждать это не буду.

-- Пн ноя 05, 2012 06:44:08 --

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

У меня есть интересный результат: 790 где 11 простых линий, но 10 уникальных как положено.

Вы уже об этом сообщали.
Повторение простых сумм - дело обычное, во многих решениях это имеется.

-- Пн ноя 05, 2012 07:01:31 --

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

504 есть, а вот 506 не видел.

У кого-нибудь есть решение 506 для N=5?

Интересный вопрос: является ли ряд решений 502, 504, 506, ...,786, 788, 790 для N=5 полным, или в нём есть отсутствующие элементы?
Решения 786, 788 у меня есть.

[dimkadimon]

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

Вы уже об этом сообщали.
Повторение простых сумм - дело обычное, во многих решениях это имеется.

Это редкость в оптимальном решении