Al Zimmerman - Delacorte Numbers

[Pavlovsky]

Yadryara в сообщении #931213 писал(а):

Стандартом всевозможных конкурсов является обсуждение после их окончания.

Большинство конкурсов программистов имеют очень жесткие сроки. То есть это конкурсы на скоростное программирование. Конкурс Al Zimmerman, единственный мне известный, где упор делается на исследование задачи.

На dxdy есть много тем посвященных задачам Al Zimmerman. Иногда обсуждение бывало весьма бурным. Организаторам конкурса известно про обсуждения на dxdy. Я так понял, мнение организаторов, обсуждение балансирует на грани запрещено/разрешено. Но в целом все в рамках правил.

[dimkadimon]

Так если можно обсуждать min и max, можно выложить мои лучшие значения? Я просто хочу понять насколько они оптимальны.

[Yadryara]

Yadryara в сообщении #931213 писал(а):

Я ещё раз перепроверю свои расчёты. Но это будет не быстро.

Да, ошибся. Скобки не там поставил. Всё здорово работает!

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

Так если можно обсуждать min и max, можно выложить мои лучшие значения? Я просто хочу понять насколько они оптимальны.

Это будет уже на грани дозволенного, как я понимаю.

[whitefox]

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

Так если можно обсуждать min и max, можно выложить мои лучшие значения?

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

[dimkadimon]

Хорошо, вот мои лучшие результаты для N<=10, надеюсь они другим помогут:

N=3, MIN=126
N=3, MAX=180
N=4, MIN=802
N=4, MAX=1392
N=5, MIN=3158
N=5, MAX=6149
N=6, MIN=10040
N=6, MAX=21350
N=7, MIN=25464
N=7, MAX=57192
N=8, MIN=58837
N=8, MAX=137617
N=9, MIN=123422
N=9, MAX=298833
N=10, MIN=238203
N=10, MAX=593249

[Yadryara]

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

Хорошо, вот мои лучшие результаты для N<=10, надеюсь они другим помогут:

До $n=5$ совпадают с моими выкладками. Выше пока лезть не тороплюсь. То есть вообще пока не исследовал.

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

N=3, MIN=126
[...]
N=4, MIN=802

Теоретический минимум имени Pavlovsky достигнут в обоих случаях.

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

N=5, MIN=3158

Здесь тоже достигнут минимум. Хоть он и на 12 баллов выше теор. минимума Pavlovsky.

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

N=5, MAX=6149

А этот результат на 935 баллов ниже теоретического максимума. Достигнут ли максимум, не знаю.

[alexBlack]

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

Хорошо, вот мои лучшие результаты ...

У меня десятка чуть больше 238205/593283.

[Pavlovsky]

Yadryara в сообщении #931304 писал(а):

Здесь тоже достигнут минимум. Хоть он и на 12 баллов выше теор. минимума

Доказать, что 3158 минимально можно даже руками.
Существует всего 3 расстановки четных чисел, которые могут обеспечить результат 3158 или меньше.

Цитата:

264
ХХ
ХХХХ
ХХХХ
ХХ
275
ХХХ
ХХХХ
ХХХХ
Х
276
ХХХХ
ХХХХ
ХХХХ

[Yadryara]

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

Доказать, что 3158 минимально можно даже руками.

Да, и это я уже проделал.

Кстати, на картинке для 264 у Вас пара пробелов потерялась.

[Pavlovsky]

Yadryara в сообщении #931398 писал(а):

Кстати, на картинке для 264 у Вас пара пробелов потерялась.

Это не у меня. Это форумный движок их съел.

[Yadryara]

И для 275 один пробел потерян. Да, особенности вёрстки текста.

Полагаю, так попонятней будет. Сумма квадратов дистанций:

$ 264 \qquad\qquad\qquad\qquad\qquad 275 \qquad\qquad\qquad\qquad\qquad 276 $$

$\tikz[scale=.4]{\draw(1,0)--(1,1)--(0,1)--(0,3)--(1,3)--(1,4)--(3,4)--(3,3)--(4,3)--(4,1)--(3,1)--(3,0)--(1,0); \draw(1,3)--(3,3); \draw(0,2)--(4,2); \draw(1,1)--(3,1); \draw(1,3)--(1,1); \draw(2,4)--(2,0); \draw(3,3)--(3,1); \draw(11,0)--(11,1)--(10,1)--(10,4)--(13,4)--(13,3)--(14,3)--(14,1)--(12,1)--(12,0)--(11,0); \draw(10,3)--(13,3); \draw(10,2)--(14,2); \draw(11,1)--(12,1); \draw(11,4)--(11,1); \draw(12,4)--(12,1); \draw(13,3)--(13,1); \draw(20,1)--(20,4)--(24,4)--(24,1)--(20,1); \draw(20,3)--(24,3); \draw(20,2)--(24,2); \draw(21,4)--(21,1); \draw(22,4)--(22,1); \draw(23,4)--(23,1); }$

[Pavlovsky]

Увы, уже для N=6, организовать перебор, который за реальное время ищет минимум, с доказательством минимальности, я не смог.

[dimkadimon]

Оказывается Ал поменял правила - теперь нельзя выкладывать баллы. Огромное извинение что я их нарушил. Вот новые правила:
https://groups.yahoo.com/neo/groups/AlZ ... sages/6285

Администраторы, можете убрать мое предыдущее сообщение?

[Yadryara]

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

Администраторы, можете убрать мое предыдущее сообщение?

Администраторы, конечно, могут. Может быть, лучше даже не полностью удалять, а скрыть до окончания конкурса. Это касается также ровно 4-х сообщений после Вашего. До http://dxdy.ru/post931398.html#p931398 включительно.

[dmd]

Хотелось бы отметить следующее. Целевая функция $\sum gcd(x_i,x_j)\cdot dist$ - "рваная" нелинейная из-за gcd. Но ведь можно перейти в другую систему координат, сделав неизвестным аргументом саму матрицу gcd:

$\sum g_{i,j}\cdot dist$

где $dist$ - матрица фиксированных коэффициентов (квадрат дистанций между ячейками квадрата)
$g$ - матрица неизвестных gcd, дающих искомый оптимум суммы

Тогда целевая функция становится чисто линейной, и задача превращается в линейное программирование с ограничениями, одно из которых $g_{i,j} = gcd(x_i,x_j)$ и учёт которого можно отложить на второй шаг. Для первого шага соорудить более простые ограничения, например количества двоек, троек, четвёрток и т.д. в таблице gcd, которые можно посчитать заранее.