Al Zimmerman - Delacorte Numbers

[sevir]

Разве для $ a = 1$ эти значения должны меняться:

$$\Psi'_x(a)=\Psi_x(a)+(x_b-x_a)a$$

$$\Psi'_y(a)=\Psi_y(a)+(y_b-y_a)a$$

[Yadryara]

Именно в эту формулу я не вникал. whitefox появится — надеюсь, расскажет

[whitefox]

Уточняю:

$$\Psi'_x(m)=\Psi_x(m)+(x_b-x_a)(\gcd(m,a)-\gcd(m,b))$$

$$\Psi'_y(m)=\Psi_y(m)+(y_b-y_a)(\gcd(m,a)-\gcd(m,b))$$

Для всех $m$ таких, что $\gcd(m,a)\ne\gcd(m,b).$

Также должно быть:

$$B=\left((x_b-x_a)^2+(y_b-y_a)^2\right)(a+b-2\gcd(a,b))$$

Ради удобства внёс исправления в исходный пост.

[sevir]

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

Уточняю:

$$\Psi'_x(a)=\Psi_x(a)+(x_b-x_a)(a-\gcd(a,b))$$

Другие формулы изменяются аналогично.

Теперь претензий нет: спасибо.

[Herbert Kociemba]

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

Сложность такого рассчета $O(1)$, что существенно меньше $O(n^4)$ при первом методе и $O(n^2)$ при втором.

I am not sure if this is true. The reason is that I think it is not sufficient to update only \Psi_x() and \Psi_y() for a and b but also you have to update it for all divisors of a and b. So I think it is still O(Log(n)).

[dmd]

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

Рассмотрим простейший пример:

$\tikz[scale=.06]{ \draw(0,0)--(0,50)--(50,50)--(50,0)--(0,0); \draw(0,10)--(50,10); \draw(0,20)--(50,20); \draw(0,30)--(50,30); \draw(0,40)--(50,40); \draw(10,0)--(10,50); \draw(20,0)--(20,50); \draw(30,0)--(30,50); \draw(40,0)--(40,50); \draw[very thick][green!40!brown!200](43,48)--(47,48)(47,48)--(44,42); \draw[very thick][green!40!brown!200](12,36)--(14,38)--(14,32)(16,36)--(18,38)--(18,32); \node at (15,4){\large \textbf{14 21 22}}; }}$

Если нам необходимо поменять местами числа 7 и 11, то изменение числа Делакорта $\Delta D$ можно посчитать так:

$$\Delta D = 2(x_7(x_7 + w_x) - x_{11}(x_{11} + w_x) + y_7(y_7 + w_y) - y_{11}(y_{11} + w_y))$$

Здесь обозначения $w$ даны в честь whitefox'a:

$$w_x = 10x_{22} - 6x_{14} - 6x_{21} $$

$$w_y = 10y_{22} - 6y_{14} - 6y_{21} $$

Можно чуть подробнее объяснить как считаются $w_x$ и $w_y$?

[sevir]

А в формуле

$$B=\left((x_b-x_a)^2+(y_b-y_a)^2\right)(a+b)$$

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

[whitefox]

sevir в сообщении #934667 писал(а):

$$B=\left((x_b-x_a)^2+(y_b-y_a)^2\right)(a+b)$$

Эту формулу уточнил:

$$B=\left((x_b-x_a)^2+(y_b-y_a)^2\right)(a+b-2\gcd(a,b))$$

[Yadryara]

dmd в сообщении #934662 писал(а):

Можно чуть подробнее объяснить как считаются $w_x$ и $w_y$?

Объяснение не очень простое. Вот формула имени whitefox:

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

$$D'=\sum\limits_{k=2}^{\frac{n^2}2}\varphi(k)\cdot D_k$$

Вычислять $D_k$ удобнее по следующей формуле:

$$D_k=\left\lfloor\frac{n^2}k\right\rfloor\sum\limits_{i\in M_k}\left(x^2(i)+y^2(i)\right)-\left(\left(\sum\limits_{i\in M_k}x(i)\right)^2+\left(\sum\limits_{i\in M_k}y(i)\right)^2\right)$$

Я подсчитал конкретные значения для 5-го порядка, но даже после сокращения в формуле для $D'$ оказалось $242$ члена. Формула делится на две симметричные половины по координатам $x$ и $y$. Вот одна половина этой формулы:

$D'(x) =53a^2 - 2a(11b + 5c + 3d + 5e + 7f + g + 7h + 3i + 2j + k + 2l + 2m + n + o + 2p) + 45b^2 - 2b(5c + 3d + 5e + 3f + g + 3h + 3i + 2j + k + 2l + 2m + n + o + 2p) + 37c^2 - 2c(d + 5e + f + g + h + i + 8j + k + 2l + 2m + n + o + 2p) + 41d^2 - 2d(e + 3f + 9g + 3h + 3i + k + 4l + n + o + 4q + 4t) + 31e^2 - 2e(f + g + h + i + 2j + k + 2l + 2m + n + o + 2p) + 29f^2 - 2f(g + 7h + 3i + k + n + o) + 31g^2 - 2g(h + i + k + 4l + n + o + 4q + 4t) + 29h^2 - 2h(3i + k + n + o) + 21i^2 - 2i(k + n + o) + 20j^2 - 2j(2l + 2m + 2p) + 23k^2 - 2k(6m + n + o + 6r) + 30l^2 - 2l(2m + 2p + 4q + 4t) + 26m^2 - 2m(2p + 6r) + 21n^2 - 2n(o + 10s) + 11o^2 + 14p^2 + 16q^2 - 2q * 4t + 12r^2 + 10s^2 + 16t^2$

Обозначения:

1. Обозначил координату $x$ для числа $24$ через $a$. У этого числа 6 нужных(2-12) делителей: 2, 3, 4, 6, 8, 12.
2. Обозначил координату $x$ для числа $12$ через $b$. У этого числа 5 нужных делителей: 2, 3, 4, 6, 12.
3. Обозначил координату $x$ для числа $18$ через $c$. У этого числа 4 нужных делителя: 2, 3, 6, 9.
4. Обозначил координату $x$ для числа $20$ через $d$. У этого числа 4 нужных делителя: 2, 4, 5, 10.
5. Обозначил координату $x$ для числа $6$ через $e$. У этого числа 3 нужных делителя: 2, 3, 6.
6. Обозначил координату $x$ для числа $8$ через $f$. У этого числа 3 нужных делителя: 2, 4, 8.
7. Обозначил координату $x$ для числа $10$ через $g$. У этого числа 3 нужных делителя: 2, 5, 10.
8. Обозначил координату $x$ для числа $16$ через $h$. У этого числа 3 нужных делителя: 2, 4, 8.
9. Обозначил координату $x$ для числа $4$ через $i$. У этого числа 2 нужных делителя: 2, 4.
10. Обозначил координату $x$ для числа $9$ через $j$. У этого числа 2 нужных делителя: 3, 9.
11. Обозначил координату $x$ для числа $14$ через $k$. У этого числа 2 нужных делителя: 2, 7.
12. Обозначил координату $x$ для числа $15$ через $l$. У этого числа 2 нужных делителя: 3, 5.
13. Обозначил координату $x$ для числа $21$ через $m$. У этого числа 2 нужных делителя: 3, 7.
14. Обозначил координату $x$ для числа $22$ через $n$. У этого числа 2 нужных делителя: 2, 11.
15. Обозначил координату $x$ для числа $2$ через $o$. У этого числа 1 нужный делитель: 2.
16. Обозначил координату $x$ для числа $3$ через $p$. У этого числа 1 нужный делитель: 3.
17. Обозначил координату $x$ для числа $5$ через $q$. У этого числа 1 нужный делитель: 5.
18. Обозначил координату $x$ для числа $7$ через $r$. У этого числа 1 нужный делитель: 7.
19. Обозначил координату $x$ для числа $11$ через $s$. У этого числа 1 нужный делитель: 11.
20. Обозначил координату $x$ для числа $25$ через $t$. У этого числа 1 нужный делитель: 5.

Всего играют 20 чисел из 25. Не играющие числа указал в теме чуть выше.

Дальше я взял из формулы все члены, содержащие $r$ и $s$, и выполнил нехитрые вычисления.

[sevir]

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

sevir в сообщении #934667 писал(а):

$$B=\left((x_b-x_a)^2+(y_b-y_a)^2\right)(a+b)$$

Эту формулу уточнил:

$$B=\left((x_b-x_a)^2+(y_b-y_a)^2\right)(a+b-2\gcd(a,b))$$

В свете прошлого Вашего замечания это очевидно, но не привык лезть поперек батьки в пекло: спасибо.

[dmd]

Как то не понятно получается. Допустим у нас есть случайный стартовый квадрат и мы для него посчитали две стартовые же таблицы $\Psi_x$ и $\Psi_y$ по формулам

$\Psi_x(m)=\sum\limits_{k\mid m}\varphi(k)X_k$

$\Psi_y(m)=\sum\limits_{k\mid m}\varphi(k)Y_k$

$X_k=\sum\limits_{i\in M_k}x_i$

$Y_k=\sum\limits_{i\in M_k}y_i$

Видно, что это достаточно тяжёлый расчет.



Почему при перестановке двух чисел в квадрате оказалось не нужным полностью пересчитать таблицы $\Psi_x$ и $\Psi_y$, а достаточно только в них пересчитать по паре чисел формулами

$\Psi'_x(a)=\Psi_x(a)+(x_b-x_a)(a-\gcd(a,b))$

$\Psi'_y(a)=\Psi_y(a)+(y_b-y_a)(a-\gcd(a,b))$

$\Psi'_x(b)=\Psi_x(b)+(x_a-x_b)(b-\gcd(a,b))$

$\Psi'_y(b)=\Psi_y(b)+(y_a-y_b)(b-\gcd(a,b))$


Ну т.е. хорошо если это так. Но на первый взгляд выглядит неправдоподобно легко.

[Pavlovsky]

sevir в сообщении #934565 писал(а):

Но не в этом суть: Herbert Kociemba пишет, что от всего этого мало толку.

Кажется понял о чем вы. Для конкурсной задачи, где $N \le 27$. Алгоритм с оценкой O(1) может оказаться даже хуже алгоритма с оценкой $O(\log N^2)$. По крайней мере выигрыш будет незначительным.

[sevir]

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

Если поменять местами числа $a$ и $b$, то изменение числа Делакорта вычисляется по формуле: ...

Во всех формулах, приведенных Вами, координаты переставляемых чисел относятся к дообменной стадии? Скорее всего, вопрос относится к последним 4-м формулам.

[Herbert Kociemba]

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

sevir в сообщении #934565 писал(а):

Но не в этом суть: Herbert Kociemba пишет, что от всего этого мало толку.

Кажется понял о чем вы. Для конкурсной задачи, где $N \le 27$. Алгоритм с оценкой O(1) может оказаться даже хуже алгоритма с оценкой $O(\log N^2)$. По крайней мере выигрыш будет незначительным.

No. For n=27 the program runs 50x faster than before. So the the algorithm of whitefox is really a big progress. But I did not get better solutions.
But I claim that the algorithm of whitefox is not O(1) but O(Log(N))=O(Log(N^2)) as I wrote before.

[jcmeyrignac]

Herbert Kociemba писал(а):

No. For n=27 the program runs 50x faster than before. So the the algorithm of whitefox is really a big progress. But I did not get better solutions.
But I claim that the algorithm of whitefox is not O(1) but O(Log(N))=O(Log(N^2)) as I wrote before.

In fact, Whitefox' algorithm is O(1) for computing the score of swapping a pair.

But the swapping requires to update at most 29+23 products, for example when swapping 720 and 672 on a 27x27 grid.
So the algorithm is indeed O(1+log(n))

Here are the worst values to swap:
(23)360: 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360
(23)420: 2 3 4 5 6 7 10 12 14 15 20 21 28 30 35 42 60 70 84 105 140 210 420
(23)480: 2 3 4 5 6 8 10 12 15 16 20 24 30 32 40 48 60 80 96 120 160 240 480
(23)504: 2 3 4 6 7 8 9 12 14 18 21 24 28 36 42 56 63 72 84 126 168 252 504
(23)540: 2 3 4 5 6 9 10 12 15 18 20 27 30 36 45 54 60 90 108 135 180 270 540
(23)600: 2 3 4 5 6 8 10 12 15 20 24 25 30 40 50 60 75 100 120 150 200 300 600
(23)630: 2 3 5 6 7 9 10 14 15 18 21 30 35 42 45 63 70 90 105 126 210 315 630
(23)660: 2 3 4 5 6 10 11 12 15 20 22 30 33 44 55 60 66 110 132 165 220 330 660
(23)672: 2 3 4 6 7 8 12 14 16 21 24 28 32 42 48 56 84 96 112 168 224 336 672
(29)720: 2 3 4 5 6 8 9 10 12 15 16 18 20 24 30 36 40 45 48 60 72 80 90 120 144 180 240 360 720

Also, Herbert, the algorithm you use is called "Threshold Accepting".