Prime Sums

[Gerbicz]

Herbert Kociemba писал(а):

If I could see any help for finding solutions just by posting the number for the different weights I would not have posted these numbers. You think just with these numbers you can find a solution without coding? Or even find *better* solutions than you already have found?

So that were not the configurations, only the weights (that's why we see 5 integers). But that could still cut off the search space to find the known best configurations. (my code would be also faster).

ps. Maybe sent a pm also. For me it is not very easy to navigate on a Russian forum.

[dimkadimon]

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

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

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

-- 26.10.2012, 23:04 --

Herbert Kociemba в сообщении #636100 писал(а):

If I could see any help for finding solutions just by posting the number for the different weights I would not have posted these numbers. You think just with these numbers you can find a solution without coding? Or even find *better* solutions than you already have found?

Herbert, just because you don't see how this can be useful it doesn't mean that other contestants can't see its usefulness. I am sure when Pavlovsky described his idea for even N he didn't think it would be useful for anyone. Yet it was very useful for me and it was the key to solving the rest of the problem, including odd N (at least for me). My personal opinion is that there should be a set of rules describing what is and isn't allowed. However, I am not in a position to introduce this. The only person who can make any changes is Neil. So I think it will be a good idea to raise these issues on the site's forum and see what he says.

[Nataly-Mak]

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

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

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

[svb]

Конечно Gerbicz, возможно, и прав. Но хочу заметить, что полностью регламентировать поведение конкурсантов сложно и уж тем более невозможно регламентировать поведение участников обсуждения, которые не участвуют в конкурсе. Приходится полагаться на здравый смысл. Например, я не выкладываю найденных мною решений для N=5 со значениями 502-790 здесь на форуме, это было бы некорректно по отношению к участникам конкурса и его организаторам.

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

Теперь о частной нерешенной проблеме. Для схемы (N=5,482,818) удалось найти около 10 различных решений (502,790), но ни одного решения 500. Я попробовал выбрать другую схему (N=5,488,812), 502 нашел, а меньше нет. Полного перебора не было.

[dimkadimon]

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

В таком случае вы не можете здесь декларировать какие-то запреты.

Я ничего не декларировал.

[whitefox]

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

Конечно Gerbicz, возможно, и прав.

Возможно прав, а возможно и не прав.
Всё зависит от цели конкурса.

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

[Pavlovsky]

whitefox в сообщении #636317 писал(а):

Если цель -- выстроить всех конкурсантов по ранжиру

Если говорить о спортивной стороне конкурса, полагаю цель конкурса определить трех лучших. А дальше какая разница займу я 10-е место или 20-е?! Обсуждение базовых, очевидных идей не может сильно повлиять на распределение мест в призовой тройке. Для победы нужны очень не тривиальные идеи.
Обсуждение предыдущей задачи было весьма бурным. Наверняка Алексей Чернов его читал. Но первое место он занял, потому что придумал высококлассный алгоритм для C=15,21. Ни у кого даже близко ничего подобного не было.

PS Идея использовать для решения текущей задачи схемы (конфигурации) лежит прямо на поверхности. Поэтому поптыки засекретить этот подход выглядят абсурдными. Кстати похожий подход я использовал в конкурсе Зимерманна "Магические квадраты как емкости для воды".

[whitefox]

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

Если говорить о спортивной стороне конкурса, полагаю цель конкурса определить трех лучших.

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

[Pavlovsky]

whitefox в сообщении #636323 писал(а):

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

Ну дык он то все равно останется первым. Чтобы его обогнать, надо искать рекорды для N=6,7. А это задача не для средних мозгов!

К тому же народ не очень любит копаться в чужих идеях. Прочитав ветку, посвященную предыдущему конкурсу, можно было лекго найти решения второго класса. То есть набрать 19,6971 балла. Реально этот рубеж преодолело всего 10 человек.

[whitefox]

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

Ну дык он то все равно останется первым.

А может он не знает, что первое место не делится?

-- 27 окт 2012, 08:43 --

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

Поэтому поптыки засекретить этот подход выглядят абсурдными.

Забавная очепятка.
Именно поптыки, по иному не скажешь.

(Оффтоп)

Полагаю, что поптыки это тычки по "мягкому месту"

-- 27 окт 2012, 08:51 --

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

К тому же народ не очень любит копаться в чужих идеях.

Во-во. Я тоже поначалу пропустил Вашу идею, пока Gerbicz
не привлёк к ней внимание.

[Pavlovsky]

Появилась вот такая задачка.
Дано: Натуральное четное число N=2K и натуральные числа A и B.
Необходимо: Разбить числа от 1 до N на два подмножества по K чисел в каждом, так чтобы сумма чисел в первом подножестве равнялась A, а во втором B.
A и B подобраны так, что разбиение всегда возможно. То есть A+B равно сумме чисел от 1 до N. Нименьшее из A,B больше или равно сумме чисел от 1 до K. Этого вроде достаточно?

Если A=B задача становится тривиальной. Помещаем в первое подмножество числа 1 и N. Во второе 2 и N-1. И так далее.

А существует ли простое решение задачи для A<>B??

Усложненный вариант задачи
Дано: Натуральное число N=K*m. И массив чисел A1,A2,...Am
Необходимо: Разбить множество чисел от 1 до N на m подмножеств по K чисел в каждом множестве. Так чтобы сумма чисел в i подмножестве равнялось Ai.

1) Является ли усложненная задача NP-полной?
2) Каким условиям должны удовлетворять числа A1,A2,...Am, чтобы искомое разбиение было возможным?

[Nataly-Mak]

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

whitefox в сообщении #634639 писал(а):

Вот никак не могу понять, почему Pavlovsky
не имеет права обсуждать эту задачу?

По правилам конкурса он имеет полное право обсуждать задачу.

dimkadimon
Здесь вы говорите о "правилах конкурса". Где эти Правила?

То, что Neil приветствует обсуждение конкурсной задачи даже и во время конкурса, а не только после его окончания, совершенно очевидно хотя бы по прошедшему конкурсу, когда на форуме конкурса было очень активное обсуждение (о чём уже написала выше).

Так что все претензии к Pavlovsky считаю абсурдными.

Кстати, он совершенно прав, говоря, что народ не любит копаться в чужих идеях. Это верно. Я, к примеру, его идеи читала очень внимательно, однако вникать в них не стала. Иду своим путём и вполне довольна своими результатами. Пусть не 50, а всего 40 баллов, зато это мой путь, мой алгоритм, мой труд.

[whitefox]

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

Появилась вот такая задачка.
Дано: Натуральное четное число N=2K и натуральные числа A и B.
Необходимо: Разбить числа от 1 до N на два подмножества по K чисел в каждом, так чтобы сумма чисел в первом подножестве равнялась A, а во втором B.
A и B подобраны так, что разбиение всегда возможно. То есть A+B равно сумме чисел от 1 до N. Нименьшее из A,B больше или равно сумме чисел от 1 до K. Этого вроде достаточно?

Если A=B задача становится тривиальной. Помещаем в первое подмножество числа 1 и N. Во второе 2 и N-1. И так далее.

А существует ли простое решение задачи для A<>B??

А что, жадный подход не сработает?

Достаточно искать множество АА, а в множество ВВ поместим все оставшиеся числа.

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

-- 27 окт 2012, 11:25 --

Пардон, не обратил внимание, что в каждом множестве должно быть ровно К чисел.

-- 27 окт 2012, 12:04 --

Пусть $A$ меньшее из чисел.
Включим в множество $AA$ все числа от $1$ до $K$.
Пусть $A$ больше суммы этих чисел, и пусть избыток равен $D$.
Представим $D$ в виде: $D=N\cdot K+M$, где $0\leqslant M < K$.
Заменим в множестве $AA$ число $L=K+1-M$ числом $K+1$.
Выберем $N$ чисел в множестве $AA$, отличных от $L$ и $1$, и заменим каждое из них числом большим на $K$.

[Nataly-Mak]

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

Кстати похожий подход я использовал в конкурсе Зимерманна "Магические квадраты как емкости для воды".

(Оффтоп)

О! Это был классный конкурс. Это был наш первый конкурс, "наш", так как мы участвовали командой. Это были мои любимые магические квадраты. И была хорошая тема, посвящённая конкурсу (на другом форуме). И в теме мы обсуждали всё! Даже выкладывали готовые решения. А что? Решений готовых на моём сайте вагон и маленькая тележка Бери любой магический квадрат - и готово решение, хотя и не самое-самое, но какое-никакое. Я тогда перелопатила все свои магические квадраты. А потом да - начала тоже искать оптимальные конфигурации. Кстати, была выложена статья одного из участников, в которой был подробно изложен его алгоритм. И вроде даже не одну статью мы нашли.
В общем, это был интереснейший конкурс.
Кстати, ситуация с баллами была очень похожа на текущий конкурс: у многих участников было 24 балла с хвостиком (тогда максимум был 25 баллов).
При этом мы начали участвовать в конкурсе очень поздно, примерно чуть больше месяца от его начала. И всё же заняли 18-ое место (тоже набрали 24 балла с хвостиком), что было очень неплохо. В конкурсе принимали участие более 100 человек!
(сейчас заглянула на сайт Зиммерманна, открыла таблицу этого конкурса, 143 участника было; магические квадраты, оказывается, популярны во всём мире )

А недавно Нил выложил на сайте интереснейшее решение задачи того конкурса. Я это решение показала в теме "Магические квадраты". Сейчас и здесь покажу. 500-летию магического квадрата Дюрера посвящается! Красивейшее решение.

Вот оно (ссылка на оригинал приведена в теме "Магические квадраты")

-- Сб окт 27, 2012 16:16:45 --

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

Конкурс будет продолжаться до самого конца как планировалось. Возможно еще остались новые рекорды для N=6 и 7. Как организатор конкурса я не имею право получать призы (я решил так будет справедливо). Поетому 2ое и 3ие места еще свободны.

По-моему, не совсем верное высказывание.
2-е и 3-е места и сейчас заняты конкурсантами, находящимися на 3 и 4 позиции соответственно, но всё ещё может измениться.
Далее, никто не гарантировал, что 1-ое место уже точно занято
Любой из конкурсантов ещё вполне может занять это место.
Сейчас уже 13 конкурсантов имеют 49 баллов с хвостиком. Ничто не мешает им найти новые рекорды.

dimkadimon
вы ведь сами писали, что все рекорды побиваемы
Или Gerbicz уже нашёл все непобиваемые рекорды? Я что-то пропустила этот момент.

(Оффтоп)

Цитата:

1 Robert Gerbicz 50.000000 10-23-2012 @ 22:11:05
2 Dmitry Kamenetsky 50.000000 10-25-2012 @ 11:29:22
3 Wes Sampson 49.981700 10-27-2012 @ 10:55:50
4 Kendrick Boyd 49.964300 10-26-2012 @ 16:13:37
5 Michael Steinau 49.932000 10-26-2012 @ 21:11:14
6 Marcin Mucha 49.925300 10-21-2012 @ 23:08:58
7 Andrews 49.870600 10-26-2012 @ 19:00:24
8 Mark Mammel 49.865400 10-20-2012 @ 02:33:25
9 Marcos Donnantuoni 49.761800 10-27-2012 @ 15:41:11
10 Walter Schneider 49.605100 10-26-2012 @ 14:19:45
11 Rick Hennig 49.603400 10-27-2012 @ 07:12:37
12 Alex Chernov 49.520200 10-16-2012 @ 21:45:46
13 Nick Gardner 49.431100 10-20-2012 @ 19:37:28
14 Rob Garretson 49.415300 10-27-2012 @ 07:01:05
15 Wladimir Leite 49.074400 10-22-2012 @ 19:32:09

[Nataly-Mak]

Завершила первый круг (нашла все 25 решений)
Это было интересно, использовала свой алгоритм "свободных электронов".
У меня нет ни одного максимума (минимума), но все решения на уровне 0,8 балла (есть и выше).
Я не стремилась искать максимумы (минимумы).
Заметила тенденцию: квадраты нечётного порядка имеют более высокие результаты, нежели квадраты чётного порядка.

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

Сейчас надо бы вернуться к книге о прошлом конкурсе. Не написаны ещё, по крайней мере, 3 главы (написано 7 глав).