Al Zimmerman - Delacorte Numbers

[Toucan]

Nataly-Mak, замечание за множественный оффтопик.

-- Сб 29.11.14 21:32:52 --

Замечание за множественный оффтопик
post938018.html#p938018

[dimkadimon]

Он живой! http://trdb.org/

[Yadryara]

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

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

Есть гипотеза, что 28 простых чисел (1; 149 — 283) для достижения максимума должны стоять максимально плотно в самом центре.

Четвёртый круг?

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

Все эти круги очень точно описываются весовой функцией

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

Nataly-Mak
Вот Ваша расстановка в квадрате 17-го порядка всех тех чисел, над которыми даже гравитация не властна:
$\tikz[scale=.04]{ \draw(0,0)--(0,170)--(170,170)--(170,0)--(0,0); \draw(0,10)--(170,10); \draw(0,20)--(170,20); \draw(0,30)--(170,30); \draw(0,40)--(170,40); \draw(0,50)--(170,50); \draw(0,60)--(170,60); \draw(0,70)--(170,70); \draw(0,80)--(170,80); \draw(0,90)--(170,90); \draw(0,100)--(170,100); \draw(0,110)--(170,110); \draw(0,120)--(170,120); \draw(0,130)--(170,130); \draw(0,140)--(170,140); \draw(0,150)--(170,150); \draw(0,160)--(170,160); \draw(10,0)--(10,170); \draw(20,0)--(20,170); \draw(30,0)--(30,170); \draw(40,0)--(40,170); \draw(50,0)--(50,170); \draw(60,0)--(60,170); \draw(70,0)--(70,170); \draw(80,0)--(80,170); \draw(90,0)--(90,170); \draw(100,0)--(100,170); \draw(110,0)--(110,170); \draw(120,0)--(120,170); \draw(130,0)--(130,170); \draw(140,0)--(140,170); \draw(150,0)--(150,170); \draw(160,0)--(160,170); \fill[red!60!blue] (70,110)--(70,120)--(80,120)--(80,110)--(70,110); \fill[red!60!blue] (100,100)--(100,110)--(110,110)--(110,100)--(100,100); \fill[red!60!blue] (60,90)--(60,100)--(70,100)--(70,90)--(60,90); \fill[red!60!blue] (70,90)--(70,100)--(80,100)--(80,90)--(70,90); \fill[red!60!blue] (80,90)--(80,100)--(90,100)--(90,90)--(80,90); \fill[red!60!blue] (50,80)--(50,90)--(60,90)--(60,80)--(50,80); \fill[red!60!blue] (60,80)--(60,90)--(70,90)--(70,80)--(60,80); \fill[red!60!blue] (70,80)--(70,90)--(80,90)--(80,80)--(70,80); \fill[red!60!blue] (80,80)--(80,90)--(90,90)--(90,80)--(80,80); \fill[red!60!blue] (90,80)--(90,90)--(100,90)--(100,80)--(90,80); \fill[red!60!blue] (120,80)--(120,90)--(130,90)--(130,80)--(120,80); \fill[red!60!blue] (50,70)--(50,80)--(60,80)--(60,70)--(50,70); \fill[red!60!blue] (70,70)--(70,80)--(130,80)--(130,70)--(70,70); \fill[red!60!blue] (50,60)--(50,70)--(100,70)--(100,60)--(50,60); \fill[red!60!blue] (70,50)--(70,60)--(110,60)--(110,50)--(70,50); \fill[red!60!blue] (120,50)--(120,60)--(130,60)--(130,50)--(120,50); }}$

А какая, на Ваш взгляд, оптимальная расстановка?

[Yadryara]

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

Кстати если весовую функцию немного изменить, то получится

$$\Phi(m)=\sum\limits_{k\mid m}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor$$

из второго пакета формул от whitefox
[...]
Весовая функция для N=4
После модификации
12 30
8 24
16 24
6 22
[...]
9 10
2 8
11 0
13 0

Здесь Вы, видимо, считаете весовую функцию так:

$$Ves(m)=\sum\limits_{k\mid m}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor - n^2$$

Иными словами, попросту ведёте суммирование $\sum\limits_{k\mid m}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor$ по всем делителям $m$, кроме единицы. То есть $k>1$.

[Pavlovsky]

Вот так будет самое точное определение весовой функции:

$$Ves(m)=\sum\limits_{k\mid m,2\le k \le \frac{N^2}{2}}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor$$

-- Пн дек 01, 2014 11:10:05 --

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

Есть гипотеза, что 28 простых чисел (1; 149 — 283) для достижения максимума должны стоять максимально плотно в самом центре.

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

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

Об этом действительно уже говорили. Я даже делал попытку доказать это утверждение. Лично я не сомневаюсь в истинности этого утверждения. И при поиске максимума, "невесомые" простые числа всегда размещаю в центр квадрата.

[whitefox]

Пусть $\pi$ произвольная перестановка порядка $n^2$, и пусть $S(\pi)=\operatorname{supp}\pi$ означает носитель перестановки $\pi$, то есть множество чисел которые перестановка $\pi$ не оставляет на месте. Для чисел $m$ и $k$, принадлежащих $\operatorname{supp}\pi$, определим функцию $\operatorname{gcd}_{\pi}(m,k)$ по правилу:

$$\operatorname{gcd}_{\pi}(m,k)=\gcd(m,k)-\gcd(\pi(m),k)-\gcd(m,\pi(k))+\gcd(\pi(m),\pi(k))$$

Тогда $\Delta D$ для перестановки $\pi$ вычисляется по формуле:

$$\Delta D=A-B-2C_x-2C_y$$

$$A=\sum_{m\in S(\pi)}(x_m^2+y_m^2)(\Phi(\pi(m))-\Phi(m))$$

$$B=\sum_{m\in S(\pi)}\sum_{k\in S(\pi)}(x_mx_k+y_my_k)\operatorname{gcd}_{\pi}(m,k)$$

$$C_x=\sum_{m\in S(\pi)}x_m(\Psi_x(\pi(m))-\Psi_x(m))$$

$$C_y=\sum_{m\in S(\pi)}y_m(\Psi_y(\pi(m))-\Psi_y(m))$$

Пересчёт $\Psi_x,\Psi_y$ выполняется по формулам:

$$\Psi'_x(m)=\Psi_x(m)+\sum_{k\in S(\pi)}x_k(\gcd(m,\pi(k))-\gcd(m,k))$$

$$\Psi'_y(m)=\Psi_y(m)+\sum_{k\in S(\pi)}y_k(\gcd(m,\pi(k))-\gcd(m,k))$$

Если вместо $\Psi_x,\Psi_y$ хранить $X_k,Y_k,$ то их пересчёт выполняется по формулам:

$$X'_k=X_k+\sum_{m\in S(\pi)}x_m\bigl( [k\mid \pi(m)]-[k\mid m] \bigr)$$

$$Y'_k=Y_k+\sum_{m\in S(\pi)}y_m\bigl( [k\mid\pi(m)]-[k\mid m] \bigr)$$

Здесь $\left[P\right]$ нотация Айверсона.

[dimkadimon]

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

Пусть $\pi$ произвольная перестановка порядка $n^2$, а $\pi'$ обратная к ней перестановка, и пусть $S(\pi)=\operatorname{supp}\pi$ означает носитель перестановки $\pi$, то есть множество чисел которые перестановка $\pi$ не оставляет на месте. Для чисел $m$ и $k$, принадлежащих $\operatorname{supp}\pi$, определим функцию $\operatorname{gcd}_{\pi}(m,k)$ по правилу:

Получается можно оптимально переставить n чисел в $O(n^2)$ операций? Вот это круто! До этого я мог только переставлять n чисел в $O(n^3)$ и то не любые n чисел.

[dimkadimon]

jcmeyrignac в сообщении #937841 писал(а):

No, the pattern are different.
Focus on circles. Edit: there are 5 circles, than can be subdivided.

I thought a lot about these 5 circles. I think I found them, but not sure if I found the correct ones. Here are the circles I found for N=27 MAX:

(Оффтоп)

555555555445454544555555555
555555445444444444555555555
555554444444434444444555555
555544444334333433445445555
555544443433333343434444555
555444343333333333334444455
554443333333333333333344445
544433333332222333333434445
544443333322222222333334445
544433333222111222233333444
444433332211111122233333445
444333332211111112223333444
443333322111111111223333345
544333322111111111323333344
443433322111111111223334344
544333322211111112223333444
444333332221111122233334445
444333333222111222233334445
544433333222222223333344445
544443333332222233333444455
555444433333333333333344445
555444433333333333343444455
555444433433333333434444555
555444544343343333444445555
555555445444333444444455555
555555544444444444444555555
555555555545444444555555555

Here is N=27 MIN:

(Оффтоп)

111111222323333333322111111
111112333333333343333331111
111223333344444344433332111
122333343444344444443333311
223333334444544444444443321
223334344444555544544543331
233343444454555555544443331
233334445545445554544443332
233434444455555555454444433
333444444555554555455444433
334344555555555555554544434
234334345555555555554443433
233344345555555555544444433
233344445555555555555544433
333344445555554555455544443
234444454555555555554445333
233344454545555555544544432
233434444455555555554444333
233334434445555454554443433
233334443354455444444443332
233334433444445555553433331
223333444444445444444333321
222333333334344343334333211
222333334444434433333333211
122223333333343323333322111
112222323333333333333221111
111122222223223322222211111

[Pavlovsky]

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

I thought a lot about these 5 circles.

Для поиска максимума, 5 кругов это слишком грубое разбиение.

Круги для N=7

Цитата:

9 8 7 6 7 8 9
8 5 4 3 4 5 8
7 4 2 1 2 4 7
6 3 1 0 1 3 6
7 4 2 1 2 4 7
8 5 4 3 4 5 8
9 8 7 6 7 8 9

N=7 число, вес, рекомендуемый круг.
Число может находиться в рекомендуемом круге +-1

Цитата:

48 176 9
42 156 9
36 154 9
24 152 9
30 148 8
40 140 8
45 122 8
20 116 8
18 114 8
12 112 8
44 108 8
28 108 8
21 98 7
16 96 7
32 96 7
15 92 7
22 84 7
14 84 7
35 78 7
10 76 7
8 72 6
6 72 6
33 72 6
39 68 6
46 68 5
9 62 5
27 62 5
38 60 5
26 60 4
34 56 4
4 48 4
23 44 4
49 42 4
7 42 4
11 40 4
25 36 4
19 36 3
13 36 3
5 36 3
17 32 3
3 32 2
2 24 2

Мои эксперименты с весовой функцией показывают, что каждое число, в соответствии с весом, может находиться в трех кругах с последовательными номерами. Причем три круга это с большим запасом. Например числа 48,42,36 могут находиться в кругах 9,8 (хотя у меня нет примеров хороших решений, где эти числа находятся в круге 8). То есть нахождение числа не в рекомендуемом круге это достаточно редкое исключение.

-- Пт дек 05, 2014 10:40:08 --

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

Here is N=27 MIN:

Применение кругов для поиска минимума, разве оправдано? В моих минимальных решениях, нет ярко выраженной центральной симметрии. Например болшие простые числа (больше N^2/2) совсем не обязательно находятся в углах квадрата. По большим простым числам явно прослеживается закономерность, они находятся там, где другие числа стоят не хотят.

[Pavlovsky]

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

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

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

В группе на яхе идет дисскуссия по этому поводу.

Конкурсную заджачу относят к классу Quadratic Assignment Problem (QAP)
http://en.wikipedia.org/wiki/Quadratic_ ... nt_problem
И предлагают решать алгоритмом "ветвей и границ". Хм, кто то копал в этом направлении?

[whitefox]

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

И предлагают решать алгоритмом "ветвей и границ". Хм, кто то копал в этом направлении?

Метод "ветвей и границ" это точный метод, а так как QAP является NP-трудной, то за приемлемое время найти решение вряд ли получится. Высказывалось мнение, что при $N > 30$ точные методы решения QAP работают слишком долго, поэтому нужно применять эвристические методы. В конкурсной задаче максимальное $N=27^2=729,$ что существенно превышает верхний порог применимости точных методов.

Впрочем, конкурсная задача довольно специфична и легко сводится к почти линейной задаче о назначениях.

[Pavlovsky]

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

Метод "ветвей и границ" это точный метод

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

В связи с этим, возникла такая задача.

Есть частично заполненный квадрат, в котором есть занятые ячейки и свободные. Заданы K занятых яччеек, к которым необходимо добавить еще S ячеек из числа свободных.
Найти S свободных ячеек, таких что сумма квадратов расстояний между K+S ячейками максимально возможная.

Можно ли эту задачу решить за полиномиальное время?

[Yadryara]

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

В конкурсной задаче максимальное $N=27^2=729,$ что существенно превышает нижний порог применимости точных методов.

Возможно, всё-таки превышает верхний, а не нижний порог?

[whitefox]

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

Возможно, всё-таки превышает верхний, а не нижний порог?

Конечно же верхний.
Исправил.

[dmd]

Я тоже пришёл к выводу, что задача в некотором смысле линейная. Две входные двумерные таблицы GCD и квадратов расстояний можно объединить в одну четырёх-мерную "таблицу" размером $N\times N\times N\times N$, где $N=n^2$ для квадрата $n\times n$. Тогда минимизировать/максимизировать нужно линейную сумму некоторых элементов этой 4-хмерной "таблицы".