Al Zimmerman - Delacorte Numbers

[Scryer]

You can also get a perfect score on $N=27$ without reaching either the best minimum or maximum that has been found, since you need only have the best difference that's been found so far. It's like swimming away from a hungry shark. You do not have to be faster than the shark -- only faster than your buddy.

The (very good) upper bounds Pavlovsky presented are irrelevant to the discussion of "approaching" a perfect score. There are $N^2!$ permutations of 1 to N-squared, which is finite. One of them gives the lowest Delacorte number, and one gives the highest. If someone finds the pair with the largest difference, they will have exactly one point on that sub-problem, no matter what other players have found or will find.

< Hmm - messed up the LaTeX, and not allowed to delete the message. Oh, well. >

[dimkadimon]

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

Утверждение 2: Если из всех дистанций вычесть 1, тогда можно игнорировать все пары чисел (a,b), которые касаются друг друга. То есть все пары где $|a_x-b_x|+|a_y-b_y|=1$. У таких пар чисел вec тоже будет 0.

Для NxN квадрата таких пар будет $2N(N-1)$.

Нет не работает утверждение :(

-- 14.12.2014, 07:33 --

Цитата:

208 15.00000 Hermann Jurksch & Hugo Pfoertner Recklinghausen & Munich, Germany 14 Dec 2014 08:13

Нашествие продолжается!

[Nataly-Mak]

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

Цитата:

208 15.00000 Hermann Jurksch & Hugo Pfoertner Recklinghausen & Munich, Germany 14 Dec 2014 08:13

Нашествие продолжается!

Ерунда!
Yadryara обещал показать 24.00000

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

24.00000 я попробую показать.

-- Вс дек 14, 2014 07:50:21 --

Yadryara
складываете решения под подушку?

Цитата:

328 3.99699 Anton Nikonov Noginsk, Russia 3 Dec 2014 02:49

-- Вс дек 14, 2014 07:54:11 --

На второе место выходит американец, потеснив канадца (всего на 0.00002):

Цитата:

1 24.99920 Tomas Rokicki Palo Alto, California, United States 14 Dec 2014 01:00
2 24.99909 Arch D. Robison Champaign, Illinois, United States 14 Dec 2014 00:03
3 24.99907 Martin Piotte Montreal, Quebec, Canada 6 Dec 2014 12:35

Борьба за первое место в самом разгаре!

[Yadryara]

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

Yadryara
складываете решения под подушку?

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

[Nataly-Mak]

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

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

О, всенепременнейше буду внимательно следить!
Удачи вам!

Болею за всех наших.
Очень хочется, чтобы повезло alexBlack и удалось прорваться в десятку сильнейших. Это очень трудно сделать!
Удачи вам, alexBlack!
Вы всегда были в первых рядах в конкурсах у AZ и даже брали первое место; правда, этот конкурс проводил не AZ; кажется, это был конкурс с раскрасками.

[Pavlovsky]

Еще немного о теоретическом максимуме.
Не все группы чисел можно разместить в квадрате с нулевым штрафом.
Например для N=7

{23,46} Штраф>=24
{22,44} Штраф>=10
{21,42} Штраф>=12
{18,36} Штраф>=6
{17,34} Штраф>=4
{16,32} Штраф>=16
{15,30,45} Штраф>=16
{14,28,42} Штраф>=30
{13,26,39} Штраф>=12
{12,24,36,48} Штраф>=4

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

PS Похоже это не мой конкурс.

[Nataly-Mak]

Россия опустилась на 15-ое место:

Цитата:

12 178.5 Netherlands 20
13 183 United States 93
14 193 Turkey 1
15 194.5 Russia 34
16 198 Germany 57

Великобритания, имея почти столько же участников, как и Россия, занимает 28-ое место:

Цитата:

28 251 United Kingdom 33

[Pavlovsky]

$$D=\mathrm{TM} - \sum\limits_{m=1}^{n^2}\Phi(m)\left(R(m)-(x_m-\mathrm{med})^2-(y_m-\mathrm{med})^2\right)-\sum\limits_{k=2}^{\frac{n^2}{2}}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor^2\left((\bar x_k-\mathrm{med})^2+(\bar y_k-\mathrm{med})^2\right) $$

Эту формулу можно использовать и для поиска минимума. Получается числа с большим весом надо распологать как можно ближе к середине квадрата. А числа из $M_k$ распологать так чтобы $\bar x_k$ $\bar y_k$ были как можно дальше от середины квадрата.

Неожиданно, надо попробовать.

-- Вт дек 16, 2014 09:56:17 --

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

Цитата:

208 15.00000 Hermann Jurksch & Hugo Pfoertner Recklinghausen & Munich, Germany 14 Dec 2014 08:13

Нашествие продолжается!

Кто то из лидеров испортил идеальную картину

Цитата:

14.99998 Hermann Jurksch & Hugo Pfoertner

[jcmeyrignac]

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

That's a nice method. Alternatively you can plot your results in Excel and fit a line of best fit (eg. exponential). Your worst results are those that are below the line of best fit. Perhaps these two methods are equivalent, because consecutive difference can be used to find a line of best fit.

I just realized that you can replace subtraction with division, and you'll get a better way to find your weak results !

[Yadryara]

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

Если у Tomas Rokicki будет 24.99999, введут шестой знак после запятой

Дело в том, что уточнение может произойти и по другой причине.

Tomas Rokicki и Arch D. Robison уже неоднократно вводили решения, но у обоих по-прежнему равная видимая оценка.

1 24.99915 Arch D. Robison United States 19 Dec 2014 05:47
2 24.99915 Tomas Rokicki United States 19 Dec 2014 05:22

Она меняется, но пока остаётся равной.

[Pavlovsky]

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

Tomas Rokicki и Arch D. Robison уже неоднократно вводили решения, но у обоих по-прежнему равная видимая оценка.

Думаю здесь дело в другом. Когда вводишь новое рекордное решение, то оценки всех других участников уменьшаются. Среди лидеров развернулась настоящая война рекордов. Люди еждневно вводят новые решения, а их оценки только уменьшаются. Ведь еще недавно лидер имел 24.9995 балла.

[Yadryara]

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

Когда вводишь новое рекордное решение, то оценки всех других участников уменьшаются.

Да, и это, похоже, всем понятно Пару дней назад в десятке появился новый персонаж — Albert Graells Rovira.

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

Люди еждневно вводят новые решения, а их оценки только уменьшаются.

Не совсем. Когда лидеры сравнялись, у них было по 24.99914. Затем стало по 24.99913, а после всё-таки побольше — по 24.99915.

[Pavlovsky]

Что то все не очень хорошо. Реализовал алгоритм перебора со штрафами. Алгоритм совершенно законный, все отсечения вариантов перебора основаны на строго доказанных утверждениях. Значительно улучшил свой максимум для N=7. Но до рекорда не хватает 20 делакортиков. Мой алгоритм перебором размещает, за реальное время, где то 30 чисел. Получается перебор надо начинать с квадрата, где уже размещены 10-12 чисел. Вот их отгадать никак не могу.

[Scryer]

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

Что то все не очень хорошо. Реализовал алгоритм перебора со штрафами. Алгоритм совершенно законный, все отсечения вариантов перебора основаны на строго доказанных утверждениях. Значительно улучшил свой максимум для N=7. Но до рекорда не хватает 20 делакортиков. Мой алгоритм перебором размещает, за реальное время, где то 30 чисел. Получается перебор надо начинать с квадрата, где уже размещены 10-12 чисел. Вот их отгадать никак не могу.

Google Translate did not do well with this, but I will guess.

You hypothesized earlier that for the maximum Delacorte, one corner would have $\Phi{\max}$ and the opposite corner would have half of that. My best squares up to $N=9$ obey that heuristic, but $N\geq10$ do not. That is not definitive, though: my maximum for $N=10$ is good, but not as good as Herbert's or JC's.

[Pavlovsky]

Выражение

$$\sum\limits_{m=1}^{n^2}\Phi(m)\left(R(m)-(x_m-\mathrm{med})^2-(y_m-\mathrm{med})^2\right)+\sum\limits_{k=2}^{\frac{n^2}{2}}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor^2\left((\bar x_k-\mathrm{med})^2+(\bar y_k-\mathrm{med})^2\right) $$

Назовем штрафом.
Для N=7, чтобы получить решение со значением 57192, штраф должен быть не больше 57400-57192=208. Если числа 24,48 расположить в углах квадрата, то их вклад в штраф =0. Расположение этих чисел в другие ячейки, то штраф сразу будет >208. То есть для N=7, расположение чисел 24,28 в углах квадрата обязательно.
Для N>7 видать нарушение рекомендаций гипотезы, не приводит к столь фатальным последствиям.