Prime Sums

[Vovka17]

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

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

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

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

А еще не понимаю почему ошибка вспомогательных линий 1 когда они равны простому числу? Ведь разрешенно повторять простые числа, а это значит что вспомогательные линии могут быть простыми не нарушая результат. В таком случае ошибка вспомогательных линий вообще не нужна! А вы пробовали убрать ошибку вспомогательных линий, то есть к2=0?

Убирать ошибку вспомогательных линий нельзя, иначе за решение будут приниматься квадраты с избытком простых сумм. Однако в записи формулы я, кажется, что-то напутал (рисунок был верен). Ошибка вспомогательной линий должна быть равна 1 в том случае, если её сумма - простое число не повторяющее использованные простые для основных линий:
б)ошибки значений вспомогательных линий:
$$\xi_i=\begin{cases} 1,&\text{если $(L'_i\in\mathbb{P})$ \textbf { и } $(L'_i\neq P_m$ для всех $m=1,2,\ldots,2N)$;}\\ 0,&\text{для остальных значений $L'_i$;} \end{cases}\quad (i=1,2,\ldots,2N)\eqno(2.2)
где $P_i$ ближайшее к $L_i$ уникальное простое число (отмеченное при определении отклонений зачетных линий).

Вроде так верно.

[dimkadimon]

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

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

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

-- 03.01.2013, 20:46 --

Vovka17 в сообщении #666490 писал(а):

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

Теперь понятно, спасибо.

[Gerbicz]

"Not true. I reached your records on 20/10/2012, just 5 days after you (by the way I wasn't allowed to compete for the first week)."

And what was the reason that you weren't allowed to compete? For those who don't know (from competiton site): "Also thanks to Dmitry Kamenetsky for his continued insights and help beta testing." So you have know the problem for weeks/months before the start, I've first seen the problem on 13/10/2012, when the compettion started.

"7. Third in IMO:" Irrelevant, that is mathematics, not programming. So far in Hungary maybe more than 75 percentage of all IMO contestants had got totally zero informatic lesson in high school.

"5. Second in ACM ICPC:" Good. Then where are Russians on http://uva.onlinejudge.org/ ? This site contains the problems from icpc competitions.

[dimkadimon]

Vovka17 в сообщении #665986 писал(а):

Стоит однако заметить, что, например, из тех шести с лишним миллионов схем потенциально подходящих для топов $N=7$, в которых копался алгоритм, ни разу, за 5-6 попыток, не было перебрано более 1% схем (решение находилось раньше) - то есть фраза довольно равномерно - вполне себе работает!..

А вы не пробовали обработать все 6 миллионов схем? Может там кроются новые рекорды.

-- 03.01.2013, 21:25 --

Gerbicz в сообщении #666600 писал(а):

And what was the reason that you weren't allowed to compete? For those who don't know (from competiton site): "Also thanks to Dmitry Kamenetsky for his continued insights and help beta testing." So you have know the problem for weeks/months before the start, I've first seen the problem on 13/10/2012, when the compettion started.

Yes I was a beta tester and wasn't allowed to compete for the first week. This is why you got most of the records, which I think is fair. So I don't know why you are complaining?

Gerbicz в сообщении #666600 писал(а):

"7. Third in IMO:" Irrelevant, that is mathematics, not programming. So far in Hungary maybe more than 75 percentage of all IMO contestants had got totally zero informatic lesson in high school.

I included it just for fun. But to be honest, there is a high correlation between good mathematical skills and good programming skills. Here are some examples (there are probably many more):

1. http://en.wikipedia.org/wiki/Reid_W._Barton
2. http://www.imo-official.org/participant_r.aspx?id=8473 and http://community.topcoder.com/tc?module ... r=22692969
3. http://www.imo-official.org/participant_r.aspx?id=6650 and http://community.topcoder.com/tc?module ... 65&tab=alg

Gerbicz в сообщении #666600 писал(а):

"5. Second in ACM ICPC:" Good. Then where are Russians on http://uva.onlinejudge.org/ ? This site contains the problems from icpc competitions.

People use UVA mostly for practicing. They don't use it to achieve a high ranking. Also most good ICPC teams practice on other sites other than UVA, some even have their own site. Being highly ranked at UVA does not imply good performance at ICPC, but it definitely helps.

[Gerbicz]

Gerbicz: "But the dry fact that after 10 days of the competition nobody reached my top records for N>7; 10 days is a long time."

dimkadimon "Yes I was a beta tester and wasn't allowed to compete for the first week. This is why you got most of the records, which I think is fair. So I don't know why you are complaining?"

OK, you entered the entires 5 days after me, but it took more than 5 days to reach it, because you could work on this problem much more than me, weeks or months before the real start of competition.

[Vovka17]

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

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

Но у меня нет никакого заданного наперёд набора простых. Какое будет значение каждой зачетной линии при каждой итерации - тоже неизвестно. Каждый раз проводить сортировку значений зачетных линий только для того, чтобы произвести оценку? Зачем тратить время и силы процессора. Я просто по порядку оцениваю отклонения начиная линии №1 и до линии №2N, и всё. Если даже, например, в двух случаях при разном порядке оценки отклонений мы получим разные результаты, не страшно. То, какую из двух оценок мы используем - не важно, ведь у нас одна цель - достичь 0. А если мы достигнем 0, то это будет выполняться при любом порядке.

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

А вы не пробовали обработать все 6 миллионов схем? Может там кроются новые рекорды.

Нет, не пробовал. Максимум, что проходила программа - около 10%. Но вы должны понимать, что даже в 1% уже были исследованы все изоморфные схемы (и не раз). Дальше просто будут идти схемы, котрые изоморфно преобразуются к уже пройденным. Где-то были здесь на форуме результаты по количеству неизоморфных схем для N=5,6,7, лучше искать несколько раз среди этих схем, а не один раз среди 6 миллионов.
То, что больше рекордов нет, подтверждают результаты Pavlovsky и то, что топовые и предтоповые значения находятся программой стабильно в течение единиц часов, а при повышении планки над топами программа стабильно ничего не находит за день-два.

[Gerbicz]

Vovka17: "Somewhere here in the forum were the results on the number of nonisomorphic schemes for N = 5,6,7, it is better to look for some time among these schemes, rather than once of 6 million. "

Have you found that N=6 MIN=890 is optimal? I have proved it. Only the sum=888 would be possible. For all possible patterns of 2N lines (up to symmetry) distribute the numbers from 1-N^2 in such a way that the sum on the 2N lines is 888 (you can do this only 4 ways, because the easy bound is 887) a backtracking code checked all possible grids (for each pattern), and found no solution.

It was an interesting case, since the same code would run much-much longer time on the smaller N=5 value, because there we are far from the easy upper/lower bounds.

[dimkadimon]

Gerbicz в сообщении #666647 писал(а):

OK, you entered the entires 5 days after me, but it took more than 5 days to reach it, because you could work on this problem much more than me, weeks or months before the real start of competition.

Indeed I could. However, once I realized how to do it, it took me a single day to code and find the solutions for N>7.

[Pavlovsky]

Для базы данных всех решений.
7-3080
49,8,37,43,29,20,7,21,35,26,44,25,6,40,46,9,48,30,3,41,2,22,39,27,42,32,11,38,47,5,36,45,23,24,1,4,17,31,33,15,12,18,10,19,28,34,13,16,14
7-1804
3,4,32,1,45,46,42,13,14,2,31,27,47,33,22,7,9,12,36,10,17,5,20,24,8,6,18,16,21,40,43,30,19,39,34,41,23,28,25,48,15,38,26,29,11,44,37,49,35
7-1810
2,10,6,15,18,17,33,32,5,11,9,45,42,13,3,31,4,12,46,30,47,25,1,29,8,7,41,20,21,48,26,24,37,16,49,39,44,23,19,35,43,14,27,28,40,22,34,36,38

-- Пт янв 04, 2013 10:58:58 --

Vovka17 в сообщении #666490 писал(а):

Убирать ошибку вспомогательных линий нельзя, иначе за решение будут приниматься квадраты с избытком простых сумм.

Мой основной алгоритм не учитывает, что во вспомогательных линиях могут появиться паразитные суммы равные простому числу. Для удаления паразитных простых сумм, использовал специальную завершающую процедуру. Специфика задачи такова, что избавится от паразитных простых сумм получалось почти всегда. Только для N=5, возникали проблемы. В этом случае я просто снова запускал основной алгоритм, пока не полуил решение без паразитных сумм.

[Pavlovsky]

Неизоморфные схемы порядков 5,6,7
http://narod.ru/disk/65099422001.67964d ... 7.rar.html

Схема это набор 2N линий. Линии пронумерованы так: строки от 1 до N, колонки от N+1 до 2N, диагонали (угол 45 градусов) от 2N+1 до 3N, обратные диагонали (угол 135 градусов) от 3N+1 до 4N.
Пример записи схемы:

1,2,3,4,8,10,11,12,15,17,18,22,23,26

Еще напомню. Мой алгоритм генерации неизоморфных схем имеет ошибку. Поэтому список неизоморфных схем меньше чем у whitefox.

[whitefox]

Поздравляю всех с наступившим Новым годом.
А победителей ещё и с достойной победой.

mertz в сообщении #665685 писал(а):

The configuration is what you are call a scheme in this forum. For N=6, if I set the threshold to 900, the schemes are: 887/1777 (4,10,9,8,5), 887/1777 (5,8,9,10,4), 891/1773 (3,12,9,6,6) and 891/1773 (6,6,9,12,3). Reading this forum tells me there is another level of detail I am missing. How many unique schemes are there for 887/1777? The Selected Configuration is just a text representation of the scheme. The Sets box lists the numbers in each group once the grid has been filled. Let me know of any other changes then I will release a new version.

В этой теме Pavlovsky дал определение "схемы" как множества зачётных линий. Приведённые Вами наборы числа весов (4,10,9,8,5) и т.д. здесь были названы "структурами", хотя последний термин и не совсем удачен.

Для N=6 и оценки не более 900 существуют следующие уникальные схемы:

887/1777 (4,10,9,8,5)
1,2,3,7,8,9,14,16,18,20,22,24
1,2,3,7,8,10,13,15,17,19,21,23
1,2,4,7,8,10,14,16,18,20,22,24

887/1777 (5,8,9,10,4)
1,2,3,7,8,9,13,15,17,19,21,23
1,2,3,7,8,10,14,16,18,20,22,24
1,2,4,7,8,10,13,15,17,19,21,23

891/1773 (3,12,9,6,6)
1,2,3,7,9,11,14,16,18,20,22,24
1,2,4,7,9,11,13,15,17,19,21,23

891/1773 (6,6,9,12,3)
1,2,3,7,9,11,13,15,17,19,21,23
1,2,4,7,9,11,14,16,18,20,22,24

896/1768 (4,10,8,10,4)
1,2,3,4,7,8,13,15,17,19,21,23
1,2,3,4,7,9,13,15,17,19,21,23
1,2,3,4,7,10,13,15,17,19,21,23
1,2,3,5,7,8,13,15,17,19,21,23
1,2,3,5,7,10,13,15,17,19,21,23
1,2,4,5,7,8,13,15,17,19,21,23
1,2,4,5,7,9,13,15,17,19,21,23
1,2,4,5,7,10,13,15,17,19,21,23

Здесь строки занумерованы числами от 1 до 6, столбцы -- числами от 7 до 12, прямые диагонали (идущие слева вниз) -- числами от 13 до 18, обратные диагонали (идущие слева вверх) -- числами от 19 до 24.

Структура (4,10,9,8,5) означает, что схема имеет 4 элемента веса 4, 10 элементов веса 10, и т.д.

Эти канонические схемы были выбраны как наименьшие в лексикографическом порядке среди всех схем одного класса изоморфизма (по Россеру).

-- 04 янв 2013, 12:28 --

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

Вот результаты, полученные whitefox:

(Оффтоп)

887/1777
4,10,9,8,5#0,2,0,3,1,3,2,0,2,1,3,1,0,2,0,3,1,3,3,1,3,2,4,2,1,3,1,4,2,4,3,1,3,2,4,2
5,8,9,10,4#0,2,0,3,1,3,2,0,2,1,3,1,1,3,1,4,2,4,2,0,2,1,3,1,1,3,1,4,2,4,3,1,3,2,4,2
4,10,9,8,5#0,2,0,3,1,3,2,0,2,1,3,1,1,3,1,4,2,4,3,1,3,2,4,2,0,2,0,3,1,3,3,1,3,2,4,2
5,8,9,10,4#0,2,0,3,1,3,2,0,2,1,3,1,1,3,1,4,2,4,3,1,3,2,4,2,1,3,1,4,2,4,2,0,2,1,3,1
4,10,9,8,5#0,2,1,2,1,3,2,0,3,0,3,1,1,3,2,3,2,4,2,0,3,0,3,1,1,3,2,3,2,4,3,1,4,1,4,2
5,8,9,10,4#0,2,1,2,1,3,2,0,3,0,3,1,1,3,2,3,2,4,3,1,4,1,4,2,0,2,1,2,1,3,3,1,4,1,4,2
#6

891/1773
3,12,9,6,6#0,2,0,3,1,3,3,1,3,2,4,2,0,2,0,3,1,3,3,1,3,2,4,2,0,2,0,3,1,3,3,1,3,2,4,2
6,6,9,12,3#0,2,1,2,1,3,3,1,4,1,4,2,0,2,1,2,1,3,3,1,4,1,4,2,0,2,1,2,1,3,3,1,4,1,4,2
3,12,9,6,6#0,2,1,3,0,3,3,1,4,2,3,2,0,2,1,3,0,3,3,1,4,2,3,2,0,2,1,3,0,3,3,1,4,2,3,2
6,6,9,12,3#0,2,1,3,1,2,3,1,4,2,4,1,0,2,1,3,1,2,3,1,4,2,4,1,0,2,1,3,1,2,3,1,4,2,4,1
#4

896/1768
4,10,8,10,4#0,2,0,2,1,3,2,0,2,0,3,1,1,3,1,3,2,4,3,1,3,1,4,2,1,3,1,3,2,4,3,1,3,1,4,2
4,10,8,10,4#0,2,0,2,1,3,3,1,3,1,4,2,0,2,0,2,1,3,3,1,3,1,4,2,1,3,1,3,2,4,3,1,3,1,4,2
4,10,8,10,4#0,2,0,2,1,3,3,1,3,1,4,2,1,3,1,3,2,4,2,0,2,0,3,1,1,3,1,3,2,4,3,1,3,1,4,2
4,10,8,10,4#0,2,0,3,0,3,2,0,2,1,2,1,1,3,1,4,1,4,3,1,3,2,3,2,1,3,1,4,1,4,3,1,3,2,3,2
4,10,8,10,4#0,2,0,3,0,3,3,1,3,2,3,2,1,3,1,4,1,4,2,0,2,1,2,1,1,3,1,4,1,4,3,1,3,2,3,2
4,10,8,10,4#0,2,1,2,0,3,2,0,3,0,2,1,1,3,2,3,1,4,3,1,4,1,3,2,1,3,2,3,1,4,3,1,4,1,3,2
4,10,8,10,4#0,2,1,2,0,3,3,1,4,1,3,2,0,2,1,2,0,3,3,1,4,1,3,2,1,3,2,3,1,4,3,1,4,1,3,2
4,10,8,10,4#0,2,1,2,0,3,3,1,4,1,3,2,1,3,2,3,1,4,2,0,3,0,2,1,1,3,2,3,1,4,3,1,4,1,3,2
#8

904/1760
2,14,8,6,6#0,2,0,3,0,3,3,1,3,2,3,2,0,2,0,3,0,3,3,1,3,2,3,2,1,3,1,4,1,4,3,1,3,2,3,2
6,6,8,14,2#0,2,1,2,1,2,3,1,4,1,4,1,0,2,1,2,1,2,3,1,4,1,4,1,1,3,2,3,2,3,3,1,4,1,4,1
#2

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

-- 04 янв 2013, 12:32 --

mertz в сообщении #665790 писал(а):

How do you put into standard form to find duplicates?

Каноническая форма выбрана как наименьшая в лексикографическом порядке среди всех схем одного класса изоморфизма.

-- 04 янв 2013, 12:35 --

mertz в сообщении #665909 писал(а):

I can only reduce to 13.

Скорее всего, Вы выполнили не все изоморфные преобразования по Россеру.

-- 04 янв 2013, 12:45 --

Pavlovsky
Для своих уникальных схем Вы использовали каноническую форму отличную от моей.

Как Вы её определили?

-- 04 янв 2013, 12:50 --

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

диагонали (угол 45 градусов)

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

обратные диагонали (угол 135 градусов)

Углы Вы измеряете против хода часовой стрелки?

Если да, то наши определения прямых и обратных диагоналей различаются.

[Pavlovsky]

Немного о платформе "1С Предприятие 7.7", на ней были написаны все мои программы. Платформа "1С Предприятие 7.7" предназначенна для быстрого создания бизнес-приложений. И для решения текущих конкурсных задач малопригодна. Программы написанные в ней работают как минимум в 100 раз медленнее чем програмы написанные на транслируемых языках. Во первых "1С Предприятие 7.7" это интерпритатор. Во вторых, в ней всего два общих типа данных. "Число", причем длинное число. Для типа "число" используется арифметика длинных чисел. Использовать в программе умножение длинных чисел это не позволительная роскошь! И строка символов неопределенной длины. Все массивы организуются как массив ссылок. Заполнение массива, скажем нулями, это уже очень длительная процедура.

Мне совсем не жалко, могу предоставить базу созданную на платформе "1С Предприятие 7.7" всем жеалющим. Всем кто знает что такое "1С Предприятие 7.7".
На картинке представлен типичный интерфейс платформы:

Видны диалоговые окошки запуска процедур: "Формирование входных данных схема+распределение чисел по группам"," поиск наборов простых чисел","Основной алгоритм заполнения квадрата".

-- Пт янв 04, 2013 14:01:22 --

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

Углы Вы измеряете против хода часовой стрелки?

Углы я взял из описания задачи:

Цитата:

Each NxN grid has N rows, N columns, N broken diagonals at 45 degrees, and N broken diagonals at 135 degrees.

[whitefox]

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

-- 04 янв 2013, 13:09 --

В приведённой Вами цитате нет определения прямой и обратной диагонали.

Я просто хочу уточнить -- одинаково ли мы понимаем эти термины.

[Pavlovsky]

(Оффтоп)

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

Для своих уникальных схем Вы использовали каноническую форму отличную от моей.

Ну русские они же коварные. Постянно запутывают и усложняют задачу для идейных борцов с читерством.

-- Пт янв 04, 2013 14:12:27 --

Прямая диагональ - идет вниз слева направо.
Обратная диагональ - идет вниз справа налево.

[whitefox]

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

Прямая диагональ - идет вниз слева направо.
Обратная диагональ - идет вниз справа налево.

Значит наши определения совпадают.

-- 04 янв 2013, 13:24 --

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

Структура (4,10,9,8,5) означает, что схема имеет 4 элемента веса 4, 10 элементов веса 10, и т.д.

Досадная опечатка.

Читать так:
Структура (4,10,9,8,5) означает, что схема имеет 4 элемента веса 4, 10 элементов веса 3, и т.д.

-- 04 янв 2013, 13:32 --

dimkadimon
Вы обещали объяснить, что за подсказка в картинке.

-- 04 янв 2013, 13:51 --

Pavlovsky

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

Pavlovsky
Для своих уникальных схем Вы использовали каноническую форму отличную от моей.

Как Вы её определили?

Вспомнил, Вы уже писали об этом.

В Вашей канонической форме обязательно должны присутствовать числа 1, N+1, 2N+1, 3N+1.

Это форма не универсальна. Если в схеме отсутствуют элементы веса 4, то её не удастся привести к этой форме.