Al Zimmerman - Delacorte Numbers

[dimkadimon]

Ладно терять уже нечего - выкладываю свою самую лучшую идею! Допустим у нас есть множество $S$, где $gcd(a,b)=k$, для всех $a,b \in S$. То есть для всех пар чисел в множестве их gcd одинаково (равно $k$). Обозначим множеством $L$ расположением всех чисел в $S$ (для какого то решения), то есть $L_a=(x_a,y_a),~a \in S$.

Утверждение: Числа в $S$ можно оптимально раставить в $L$ за время $O(n^3)$, где $n=|S|$.

Для этого можно использовать Венгерский алгоритм решающий задачу о назначениях (https://ru.wikipedia.org/wiki/%D0%92%D0 ... 1%82%D0%BC). Обозначим $n \times n$ матрицу M, где $M_{ab}$ это цена поставки числа $a \in S$ на место $L_b$. Точнее $M_{ab}=\sum_{i \notin S} gcd(a,i)*[(x_b-x_i)^2+(y_b-y_i)^2]$. Важно отметить что для подсчёта $M_{ab}$ нам не надо учитывать как числа в $S$ влияют друг на друга. Это потому что для всех $a,b \in S$ имеем $gcd(a,b)=k$ и любая перестановка в $L$ будет давать одинаковый результат. Венгерский алгоритм даст лучшее назначение рядов к колонкам в $M$, то есть оптимальную растановку чисел в $S$ на места $L$.

Теперь как находить $S$? Есть много вариантов. Например $S_i = C * p^k_i$, где $p_i$ простое число (или 1), $k$ и $C$ положительные константы. Для 6х6 и $k=1$ получаем такие разные $S$:

1 2 3 5 7 11 13 17 19 23 29 31
2 4 6 10 14 22 26 34
3 6 9 15 21 33
4 8 12 20 28
5 10 15 25 35
6 12 18 30
7 14 21 35
8 16 24
9 18 27
10 20 30
11 22 33
12 24 36


А вот результат для $k=2$:

1 4 9 25
2 8 18
3 12 27
4 16 36
5 20
6 24
7 28
8 32
9 36


А также можно объеденить эти $S$ и получить более длиные, например:

1 4 9 25 7 11 13 17 19 23 29 31
2 8 18 10 14 22 26 34
3 12 27 15 21 33
4 16 36 20 28
5 20 15 25 35
6 24 18 30
7 28 21 35
8 32 24
9 36 27

[Pavlovsky]

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

выкладываю свою самую лучшую идею!

Классная идея.

[Pavlovsky]

На яхе https://groups.yahoo.com/neo/groups/AlZ ... opics/6470 опубликована формула:

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

$$\frac{n^4(n^2-1)}6$$

Комментарий:

Цитата:

even though it seem to have little bearing on the current contest.

A245828 Szeged index of the grid graph P_n X P_n

[whitefox]

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

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

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

Но whitefox говорит об использовании специфики задачи при лианеризации. Подождем, может расколется?!

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

Ладно терять уже нечего - выкладываю свою самую лучшую идею!
. . .
Для этого можно использовать Венгерский алгоритм решающий задачу о назначениях

Раскололся, но не я.

[Pavlovsky]

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

[whitefox]

Код собственно "венгерского алгоритма" можно взять здесь: http://e-maxx.ru/algo/assignment_hungary#6

-- 23 дек 2014, 09:20 --

И так как каждую строку матрицы $M$ можно уменьшить на константу, то вместо $M_{ab}$, определённого dimkadimon, можно использовать:

$$M_{ab}=\left((x^2_b+y^2_b)\sum_{k\mid a}\varphi(k)|M_k^*|\right)-2\left(x_b\sum_{k\mid a}\varphi(k)\sum_{i\in M_k^*}x_i\right)-2\left(y_b\sum_{k\mid a}\varphi(k)\sum_{i\in M_k^*}y_i\right)$$

где $\bar S$ дополнение множества $S$ до $\{1,\dots,n^2\}$ и $M_k^*=M_k\cap\bar S$.

[Pavlovsky]

Меня, для начала, больше интересуют теоретические аспекты.

Пусть у нас есть система множеств $\lbrace S_i \rbrace$. Таких что для любых $a,b \in S_i$ $gcd(a,b)=K_i$

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

[whitefox]

Сомневаюсь, что система $\{S_i\}$ имеет какие-то алгебраические свойства.

Саму систему строю так:

1. нахожу все максимальные множества попарно взаимно простых чисел не больших $n^2$;
2. для каждого $2\leqslant K\leqslant\frac{n^2}2$ и каждого множества, найденного на предыдущем шаге, умножаю на $K$ каждый элемент;
3. в полученных множествах удаляю числа большие $n^2$;
4. удаляю из системы не максимальные множества и дубли.

Использование системы $\{S_i\}$ похоже на жадный вариант наискорейшего спуска, только во втором случае выбирается наилучшая транспозиция, а в первом -- наилучшая перестановка множества $S_i$, что даёт надежду выхода из локального оптимума. И так как множества $S_i$ перекрываются, то есть надежда приблизится к глобальному оптимуму.

Разумеется, результат зависит от порядка использования множеств $S_i$. Наверно, лучшим вариантом будет выбирать $S_i$ случайно с некоторым весом (равному, например, сумме весов элементов).

[Pavlovsky]

Множеств $S_i$ очень много. Тут никакого венгерского алгоритма не хватит все их перебрать. А если учесть что результат зависит от порядка оптимизации множеств $S_i$... Нужно как то поделить множества $S_i$ на плохие и хорошие.

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

случайно с некоторым весом (равному, например, сумме весов элементов)

Сразу применять эвристики как то не хочется. Надо хоть немного, для приличия, поскрипеть мозгами.

[dimkadimon]

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

И так как каждую строку матрицы $M$ можно уменьшить на константу, то вместо $M_{ab}$, определённого dimkadimon, можно использовать:

Не понимаю, что это нам дает?

[whitefox]

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

Не понимаю, что это нам дает?

Сокращение времени на вычисление матрицы $M.$

[Pavlovsky]

Провел эксперименты с венгерским алгоритмом по методу Каменцкого. Результаты довольно скромные, расчитывал на гораздо большее.

Конкурс вышел на финишную прямую. Активность лидеров потихоньку спадает.
Вот думаю чем заняться последнюю неделю.
1) Можно запустить все наличные алгоритмы и получить результаты где то в районе 100-го места. 100-е место не вдохновляет.
2) Или похулиганить?! Сосредоточится на одном N и попробовать установить рекорд. Как думает сообщество, для какого N есть большие шансы найти рекордное решение?

[Scryer]

Perhaps the maximum for N=16. The best estimate I've seen seems furthest away from the curve of Pavlovsky upper bounds.

[yae9911]

Or try to find Max12. The corresponding record seems to be held by not too many participants.

[Pavlovsky]

Scryer в сообщении #951648 писал(а):

for N=16

yae9911 в сообщении #951655 писал(а):

find Max12

В этой теме уже высказывалось удивление, что новые рекорды до сих пор находят для относительно небольших N. И даже давалось этому объяснение. Но все таки, найти новый рекорд для N=12 это наверно перебор.

-- Чт дек 25, 2014 09:40:39 --

$$\frac{n^4(n^2-1)}6$$

whitefox не привел доказательство этой формулы и никто у него не поинтересовался как он это сделал. Поэтому привожу свой вывод формулы.

1) Посчитать сумму квадратов расстояний между ячейками в квадрате NxN, можно отдельно по координатам x и y.

2) Количество ячеек для которых $|x_i-x_j|=k$ равно

$$N^2(N-k)$$

3) Получается такая формула для суммы квадратов расстояний между ячейками.

$$2N^2 \sum_{k=1}^{N-1}(N-k)k^2$$

4) Далее воспользуемся формулами расчета суммы натуральных чисел в степени k (k=2,3) и получим исходную формулу.