2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 25  След.
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение15.11.2014, 10:53 
Аватара пользователя
Yadryara в сообщении #931213 писал(а):
Стандартом всевозможных конкурсов является обсуждение после их окончания.


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

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

 
 
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение15.11.2014, 12:14 
Аватара пользователя
Так если можно обсуждать min и max, можно выложить мои лучшие значения? Я просто хочу понять насколько они оптимальны.

 
 
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение15.11.2014, 13:04 
Аватара пользователя
Yadryara в сообщении #931213 писал(а):
Я ещё раз перепроверю свои расчёты. Но это будет не быстро.

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

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

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

 
 
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение15.11.2014, 15:05 
Аватара пользователя
dimkadimon в сообщении #931236 писал(а):
Так если можно обсуждать min и max, можно выложить мои лучшие значения?

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

 
 
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение15.11.2014, 15:23 
Аватара пользователя
Хорошо, вот мои лучшие результаты для 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

 
 
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение15.11.2014, 15:46 
Аватара пользователя
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 баллов ниже теоретического максимума. Достигнут ли максимум, не знаю.

 
 
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение15.11.2014, 16:56 
dimkadimon в сообщении #931294 писал(а):
Хорошо, вот мои лучшие результаты ...
У меня десятка чуть больше 238205/593283.

 
 
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение15.11.2014, 18:35 
Аватара пользователя
Yadryara в сообщении #931304 писал(а):
Здесь тоже достигнут минимум. Хоть он и на 12 баллов выше теор. минимума


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

 
 
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение15.11.2014, 18:48 
Аватара пользователя
Pavlovsky в сообщении #931391 писал(а):
Доказать, что 3158 минимально можно даже руками.

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

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

 
 
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение15.11.2014, 19:48 
Аватара пользователя
Yadryara в сообщении #931398 писал(а):
Кстати, на картинке для 264 у Вас пара пробелов потерялась.


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

 
 
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение15.11.2014, 19:50 
Аватара пользователя
И для 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);
}$

 
 
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение15.11.2014, 19:59 
Аватара пользователя
Увы, уже для N=6, организовать перебор, который за реальное время ищет минимум, с доказательством минимальности, я не смог.

 
 
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение16.11.2014, 01:46 
Аватара пользователя
Оказывается Ал поменял правила - теперь нельзя выкладывать баллы. Огромное извинение что я их нарушил. Вот новые правила:
https://groups.yahoo.com/neo/groups/AlZ ... sages/6285

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

 
 
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение16.11.2014, 06:29 
Аватара пользователя
dimkadimon в сообщении #931570 писал(а):
Администраторы, можете убрать мое предыдущее сообщение?

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

 
 
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение16.11.2014, 22:37 
Хотелось бы отметить следующее. Целевая функция $\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, которые можно посчитать заранее.

 
 
 [ Сообщений: 373 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 25  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group