Prime Sums

[Gerbicz]

dimkadimon: (google translation) "Was nice to chat in the forum and read your ideas."

I recommend the "cheat" word.

Congratulations to the contestants who used their OWN brain!

Nataly: "Congratulations to my new colleague and team member Alexei Belysheva!"

In that case why haven't you registered as a team?

[dimkadimon]

Gerbicz I did not cheat. I can show you all my code. Admit it you lost. End of story.

[Nemiroff]

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

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

Such a tragic decision.

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

I recommend the "cheat" word.

Why do you think they are all cheating? I know nothing about your competition, but here there is an opinion that only two person are cheating, not the whole Russian community.

[Vovka17]

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

Итоги по БД:
для "пятёрки" не найдено решение 506; для "шестёрки" не найдено решение 1752; для "семёрки" БД полная.

Решение 1752 для N=6 существует - 100%. Можете считать БД для шестерки тоже полной.
Решения 506 для N=5 не существует с вероятностью $\approx100$%.

[Pavlovsky]

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

задача эта вам не чужда. В своё время вы её решали упорно. Может быть, продолжите?

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

-- Ср янв 02, 2013 11:49:25 --

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

Я что-то не понимаю, меня все в игнор записали что ли?

Поздравляю, индивидуально, Вас и whitefox с успешным выступлением в конкурсе. Наталия, пользуясь случаем, отдельно хочу Вас поблагодарить за популяризацию конкурса среди русскоязычной аудитории. Без вас не было бы этой ветки и предыдущих веток тоже. Большое количество россиян в верхних строках рейтинга тоже ваша заслуга. Напрашивается ассоциация. Вы нейтрон, который удерживает протоны в ядре атома. Без Вас протоны разлетелись бы в разные стороны.

[svb]

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

Даже понравился "международный скандал" - который я надеюсь приведет к написанию строгих правил.

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

А Nataly-Mak я приношу особую признательность за её мужество.

[Pavlovsky]

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

Входными данными для основного алгоритма являются:
1) Схема (2N зачетных линий)
2) Распределение чисел от 1 до N^2 по группам, согласно заданной схеме.
3) Схема и распределение чисел по группам однозначно задают сумму сумм зачетных линий, то есть сумму решения, которое будет получено в результате выполнения алгоритма.
4) Набор 2N простых чисел.

dmd Как подготовить, выше описанные, входные данные, довольно подробно обсуждалось в этой ветке. Тезисно повторю.
1) Для N>=8, нужна схема с оптимальной нижней (верхней) теоретической оценкой. Такие схемы можно получить простым алгоритмом по-координатного спуска. Для N<=7, можно полным перебором сформировать все схемы. Количество рассматриваемых схем можно сильно сократить отбросив изоморфные схемы. Для этого можно воспользоваться статьей Россера, где описана группа автоморфизмов пандиагональных квадратов.
2) Если теоретическая оценка схемы равна сумме решения, которую мы хотим найти, то распределение чисел по группам единственно. Если разность между искомой суммой решения и оценкой схемы небольшая (<=3), то количество распределений небольшое и их все можно перебрать. При большой разнице между искомой суммой решения и оценкой схемы, выбираем распределения, которые эвристически нам больше нравятся. У меня никаких проблем с этим не было.
4) По схеме можно посчитать минимально (максимально) возможную сумму линий. То есть мы можем задать диапазон чисел из которого надо выбирать простые числа. По заданной схеме можно получить и более сложные ограничения на наборы простых чисел.
В теме неоднократно обсуждалась гипотеза: "Лучший набор простых чисел, последний в списке наборов простых чисел упорядоченных в лексикографическом порядке". Все вычислительные эксперименты подтверждают истинность этой гипотезы.

[dmd]

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

1) Для N>=8, нужна схема с оптимальной нижней (верхней) теоретической оценкой. Такие схемы можно получить простым алгоритмом по-координатного спуска.

Вот это место мне осталось не понятно. Что именно Вы получали по-координатным спуском? Числа a0,a1,a2,a3,a4? Только эти числа, соответствующие оптимальной теоретической оценке - это ещё не схема. Схема - это номера 2N зачетных линий из всего набора 4N линий, откуда получаются координаты конкретных ячеек с соответствующим весом 0,1,2,3,4 и соответственно просчитываются числа a0,a1,a2,a3,a4. Или у Вас был способ развернуть схему из голых чисел a0,a1,a2,a3,a4? Или Вы по-координатным спуском получали непосредственно координаты ячеек с соответствующим весом?

[Pavlovsky]

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

Схема - это номера 2N зачетных линий из всего набора 4N линий, откуда получаются координаты конкретных ячеек с соответствующим весом 0,1,2,3,4 и соответственно просчитываются числа a0,a1,a2,a3,a4.

Именно таким определением схемы я пользуюсь. Схема - это набор(множество) из 2N линий. Соответственно задача: "Найти схему". Означает найти набор из 2N линий.
Алгоритм по-координатного спуска я описывал в : post641576.html#p641576

[Gerbicz]

"Gerbicz I did not cheat. I can show you all my code. Admit it you lost. End of story"

I've found on page 8 (on this forum):

"Now due to this forum, a number of other people have found the "right" method. I will be honest with you, because I am one of those people. Without this forum I wouldn't have reached 50, at least not so quickly."

I would call this cheat. Not only on a serious competition but on a simple university course you would fail:
"An exhaustive list of Honor Code violations would be impossible to present here, but
among other things, each of the following is a flagrant violation of the Virginia Tech
Honor Code, and violations will be dealt with severely (Honor Court):
Working with another student to derive a common program or solution to a
problem. There are no group projects in this course.
• Discussing the details required to solve a programming assignment. You may not
share solutions.
..."

I reached all of my results with my own brain. Furthermore I don't think that the competition decided on N=5-7, because that is only 6 values (MIN-MAX) and if you are nowhere on N>7 then you are totally lost. And you were nowhere (not only Russians).

And I don't think I'm lost, if you see the record table. From azspcs.net: "(Problems for which the best solution was found during the first 48 hours of the contest are omitted.)" For almost all of my records this is true, so found in less than 2 days. I've lost only my interest.

[Pavlovsky]

(Оффтоп)

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

I've lost only my interest.

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

[Nemiroff]

(Оффтоп)

Цитата:

Плохому танцору всегда яйца мешают.

Такое нужно переводить на английский самостоятельно. Потому что Google выдает на редкость бессмысленную фразу.

[dimkadimon]

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

"Now due to this forum, a number of other people have found the "right" method. I will be honest with you, because I am one of those people. Without this forum I wouldn't have reached 50, at least not so quickly."

I would call this cheat. Not only on a serious competition but on a simple university course you would fail:

Again it depends on the rules of the organization. In this competition it was allowed to talk about the problem openly. Hence I did nothing wrong and others did nothing wrong. So all your accusations are pointless.

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

I reached all of my results with my own brain. Furthermore I don't think that the competition decided on N=5-7, because that is only 6 values (MIN-MAX) and if you are nowhere on N>7 then you are totally lost. And you were nowhere (not only Russians).

In the end it was decided on N=5 to 7, because everyone in the top 10 had optimals for N>7. I would have got N>7 without this forum, albeit it would take more time. This your biggest misconception. For some reason you think others are not as smart as you. But you are wrong. Given sufficient time, many people can and will find the same ideas. This was already pointed out to you many times.

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

And I don't think I'm lost, if you see the record table. From azspcs.net: "(Problems for which the best solution was found during the first 48 hours of the contest are omitted.)" For almost all of my records this is true, so found in less than 2 days. I've lost only my interest.

Once again this is not AZ. This is an entirely new competition. The records are great, but overall ranking is more important. This is a marathon rather than a race for the records. So you lost.

-- 03.01.2013, 07:08 --

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

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

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

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

ошибки значений вспомогательных линий:

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

-- 03.01.2013, 07:13 --

svb в сообщении #666088 писал(а):

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

Организаторы конкурса ето один человек (Нейл), которому если честно не до етих глупых скандалов, у него и так работы завались. К тому же как можно кого то удалять когда нет конкретных правил? Удалять конкурсантов ето огромное решение которое может привести к потере новых участников. Тут нельзя действовать на одних емоциях, а надо глубоко подумать. Сначало надо написать точные правила, а потом уже наказывать нарушителей етих правил. У всех есть доступ к написанию правил.

[Gerbicz]

"Once again this is not AZ. This is an entirely new competition. The records are great, but overall ranking is more important. This is a marathon rather than a race for the records. So you lost."

In this case you are also lost, am I right? I think that we have really different valuation, it seems that you count only gols medals, however on olympic games even the 6-th place gets olympic point. No problem, in Hungary also lots of people count only gold medals.

"everyone in the top 10 had optimals for N>7. I would have got N>7 without this forum, albeit it would take more time. This your biggest misconception"

And we will never know who is right. 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. Moreover I clearly see the effect of this forum on the ranklist, 6 Russians (including Nataly and her colleague) finished in the top 10. Yes, Russians are good in programming, but on other competitons I haven't seen such overwhelming results from them. See only spoj.pl, on the top 100 there are only 2 Russians.

[dimkadimon]

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

In this case you are also lost, am I right? I think that we have really different valuation, it seems that you count only gols medals, however on olympic games even the 6-th place gets olympic point. No problem, in Hungary also lots of people count only gold medals.

Yes I also lost, but not as much as you

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

And we will never know who is right. 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. Moreover I clearly see the effect of this forum on the ranklist, 6 Russians (including Nataly and her colleague) finished in the top 10. Yes, Russians are good in programming, but on other competitons I haven't seen such overwhelming results from them. See only spoj.pl, on the top 100 there are only 2 Russians.

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). Spoj is not a representative example of Russia's dominance in programming competitions. See these:

1. Best on TopCoder: http://community.topcoder.com/stat?c=country_avg_rating
2. Best on Codeforces: http://codeforces.com/ratings/countries
3. Best in Google AI Challenge: http://aichallenge.org/country_profile.php?country=8 and http://planetwars.aichallenge.org/count ... untry_id=8
4. Best in Google Code Jam: http://www.go-hero.net/jam/12/regions, http://www.go-hero.net/jam/11/regions
5. Second in ACM ICPC: http://en.wikipedia.org/wiki/ACM_Intern ... st#Winners. Probably first if you don't count the early years (<1990) when only US+Canada competed.
6. Second in IOI: http://ioi.eduardische.com/countries/?sort=medals_desc
7. Third in IMO: http://www.imo-official.org/results_cou ... order=desc