Конкурс Зиммерманна о перекладывании карт

[maxal]

Morales и Sudborough недавно доказали квадратичную нижнюю оценку для A000375. Правда, для данной задачи она не поможет - получаются слишком мелкие значения.
Но препринт тут, если что: http://faculty.tamu-commerce.edu/lmoral ... ic2006.pdf

[Nataly-Mak]

dvorkin_sacha в сообщении #377098 писал(а):

Каждый волен сам выбирать стратегию поведения: вот Вы, например, ни словом не обмолвились по поводу n = 17.

Почему не обмолвилась? Вот, например:

Цитата:

Для $n = 2, 3, 5, 7, 11, 13, 17$ максимумы известны.

Если вы читали тему, то должны были видеть, откуда они известны.
Вас интересует, взяла ли я последовательность для n=17 из OEIS?
Да, взяла. А что, это запрещено правилами конкурса?

Зачем бить диски и мозги для получения уже известного результата?

В прошлом конкурсе один из участников (а может быть, и не один?) взял все магические квадраты с моего сайта. При этом на сайте не оказалось квадрата порядка 26. Так я его специально построила и выложила на форуме (тема о конкурсе на форуме Портала ЕН, называется "Магические квадраты как ёмкости для воды").
После того, как он ввёл все 25 моих квадратов (предварительно поработав с ними, то есть сделал в некоторых квадратах различные преобразования, чтобы увеличить ёмкость квадрата), стал думать об алгоритмах для улучшения полученных результатов. При этом алгоритмы активно обсуждались в указанной теме.

12d3
у меня по-прежнему команда в том же составе, что была на педыдущем конкурсе. Так что все полученные мной результаты уже улучшены оним из участников команды (svb). До того, как ко мне подключился svb, у меня было всего 9,75 балла. Однако замечу, что это всё же больше, чем 3 балла за первые три простенькие задачки плюс один балл за последовательность для n=17. Я уже сделала программы до n=47 и получила свои результаты, которые были улучшены svb.
Например, полученный по моей программе результат для $n=19$:

18  12  5  17  8  4  10  11  9  15  13  2  19  3  1  6  7  14  16 
 143

Получив этот результат, я его сразу же ввела и таким образом посчитала максимум (по той доле балла, которую мне начислили за этот результат).
Конечно, я сразу поняла, что этот результат далеко не 100%, потому что для $n=17$ имеем 159. А все результаты, разумеется, растут с ростом $n$.
По правилам конкурса можно вводить несколько результатов для одного и того же $n$.

Вот наши текущие результаты:

19 218 180
23 350 258
29 669 388
31 728 432
37 1063 638
41 1218 720
43 1431 757
47 1927 838
53 2347 1000
59 3013 1164
61 3242 1225
67 4200 1375
71 4655 1474
73 4986 1528
79 6317 1732
83 6448 1887
89 8375 2130
97 10629 2508

В первой колонке $n$, во второй посчитанный мной максимум (который, однако, всё время меняется), в третьей наши результаты.

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

[Nataly-Mak]

Выкладываю решения, полученные по моим программам:

n=2: 2, 1
n=3: 2, 3, 1
. . .

Для $n=11$ программа выдала несколько решений с результатом 47, а максимум 51 так и не нашла.
Вот ещё решение с 47 перекладываниями:

2, 6, 1 . . . .

Для следующих $n$ программы ещё не писала.

Повторю, все мои результаты улучшены svb, кроме первых 4-х, которые уже были максимальными.

-- Пт ноя 19, 2010 09:26:35 --

Jarek
Поздравляю!! Вы уже в десятке лучших.
Я буду за вас болеть

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

[dvorkin_sacha]

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

dvorkin_sacha в сообщении #377098 писал(а):

Каждый волен сам выбирать стратегию поведения: вот Вы, например, ни словом не обмолвились по поводу n = 17.

Почему не обмолвилась? Вот, например:

Цитата:

Для $n = 2, 3, 5, 7, 11, 13, 17$ максимумы известны.

Если вы читали тему, то должны были видеть, откуда они известны.
Вас интересует, взяла ли я последовательность для n=17 из OEIS?
Да, взяла. А что, это запрещено правилами конкурса?

Я имел в виду нечто другое: Вы сравниваете свои результаты для n = 11, 13, хотя для этих n максимальные результаты можно получить не напрягаясь на любомом маломощном компе, избегая сравнения для n = 17.

[Nataly-Mak]

Да я хорошо поняла, что вы имели в виду.
И дала ответ на ваш вопрос. Я писала о своих результатах для тех $n$, с которыми в тот момент работала. С последовательностью для $n=17$ я не работала, поэтому ничего для неё и не сравнивала.
Далее могу сравнить свои результаты с максимальными вплоть до $n=47$, для которых, как я уже сказала выше, написала программы и получила свои результаты. Собственно, уже и сделала это, приведя таблицу посчитанных мной максимумов.

Насчёт того, что можно получить, не напрягаясь, это зависит от способностей каждого. Одни уже, не напрягаясь, получили по 18-24 балла, а другие, напрягаясь, и 10 не получили.
"Тут кто как умеет..."

Вот ещё подтверждение, что я сравнивала свои результаты с максимальными не только для $n=11$ и $n=13$:

Цитата:

Так, например, по моим расчётам такие максимумы:

n=19   218
n=23   350
n=29   669
n=31   728

У кого есть более точные значения?

Ах, да, результаты свои не привела.
Вот они:

n=2 1
n=3 2
n=5 7
n=7 16
n=11 47
n=13 68
n=19 143
n=23 165
n=29 234
n=31 335
n=37 319
n=41 402
n=43 517
n=47 453

Эти результаты я получила с ходу, покрутив написанную программу для каждого $n$ минут 10-15. Дальше уже надо напрягаться.

Для сравнения: первое улучшение svb:

n=11 51
n=13 80
n=19 157
n=23 178
n=29 267
n=31 398
n=37 400
n=41 484
n=43 646
n=47 578

Потом он получил ещё несколько улучшений.

[Nataly-Mak]

Jarek
Браво! Уже первое место. Теперь главное удержаться.
Не зря я за вас болела

[Jarek]

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

Браво! Уже первое место. Теперь главное удержаться.

It will be hard, but I will do my best

Unfortunately, early lead, like in a marathon, doesn't guarantee a good overall performance

Anyway, I am unlikely to improve my findings in November, as I will be very busy those days. So it is quite likely that I will loose the lead. But I hope to be ready to fight it back in December

Also I will keep my fingers crossed for you and your team to improve over your 18th place in the last contest.

[Nataly-Mak]

Jarek в сообщении #377741 писал(а):

Also I will keep my fingers crossed for you and your team to improve over your 18th place in the last contest.

Спасибо

[dvorkin_sacha]

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

С последовательностью для $n=17$ я не работала, поэтому ничего для неё и не сравнивала.

Вот это я и хотел услышать, и не более того. А ведь $n=17$ интересно тем, что для него известен точный результат, который за разумное время в лоб на одном компе не посчитаешь (лет 20 уйдет для неплохого компа). У меня расчет в лоб для $n=13$ занял порядка одной минуты, а оптимизированный - доли секунды.

[Nataly-Mak]

dvorkin_sacha в сообщении #377878 писал(а):

А ведь $n=17$ интересно тем, что для него известен точный результат, который за разумное время в лоб на одном компе не посчитаешь (лет 20 уйдет для неплохого компа). У меня расчет в лоб для $n=13$ занял порядка одной минуты, а оптимизированный - доли секунды.

Что для $n=17$ результат известен, давным-давно написал EtCetera, приведя ссылку на последовательность в OEIS. И что для $n=11$ и $n=13$ он быстро получил максимальный результат, тоже написал. Надо внимательно читать тему.

А для $n>17$ разве можно быстро получить максимумы? О расчётах в лоб никто и не говорит, все прекрасно понимают, что такой расчёт быстро заткнётся. Надо искать оригинальные алгоритмы, но в этом и интерес задачи.

Вот вчера мне удалось придумать один алгоритм. Попробовала для $n=19$, большого улучшения не получила, было у нас 180, получила 184. Но надо ещё пробовать, с другими последовательностями. А также для других $n$ надо пробовать, ведь с ростом $n$ результаты всё хуже. Такая вот закономерность.

Кстати, вот за такое улучшение (184 вместо 180) дали всего 0,02 балла.
Но, по-моему, дело совсем не в баллах, а в том удовольствии, которое получаешь от решения задачи. Каждая новая находка - большая радость.

Надеюсь, что лидер конкурса Jarek по окончании конкурса расскажет нам, какими алгоритмами он пользовался при решении задачи. Мне, например, это очень интересно.

И в прошлом конкурсе, кстати, у него были очень интересные алгоритмы и замечательные результаты.

Позволю себе сравнение с магическими квадратами.
Я сейчас конкурс провожу "Нетрадиционные пандиагональные квадраты".
Так вот, $n=17$ интересно тем, что для данного порядка ещё не найден пандиагональный квадрат из простых чисел. И в одной из конкурсных задач его надо найти.
А для порядков 11 и 13 я решила эту задачу. И, конечно же, не в лоб Потому что, как вы верно заметили, в лоб эту задачу можно и за 20 лет не решить.

[dvorkin_sacha]

Nataly-Mak

$n=17$ интересно именно тем, что для него известен точный результат, т.е известно, к чему стремиться. Про $n=19$ уже этого точно не скажешь.

[Nataly-Mak]

Вам не кажется, что вы зациклились на $n=17$?

Мне остаётся повторить:

Цитата:

Для $n = 2, 3, 5, 7, 11, 13, 17$ максимумы известны.

И далее замечу, что предполагаемые максимумы для всех $n$ мной посчитаны и выложены здесь.
Это, конечно, не окончательные максимумы, потому что они постоянно меняются. Но к чему надо стремиться, известно уже.
А если вы получили результат больше посчитанного мной максимума, это просто значит, что он изменился - участники конкурса получили новый максимальный результат.

[dvorkin_sacha]

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

Вам не кажется, что вы зациклились на $n=17$?

... И далее замечу, что предполагаемые максимумы для всех $n$ мной посчитаны и выложены здесь.

Никуда я не зацикливался: в случае $n=17$ мы, как Вы выражаетесь, не предполагаем, а располагаем. А это несколько разные вещи. А за то, что выложили информацию, спасибо.

[Nataly-Mak]

Придуманный алгоритм даёт неплохие результаты. Мне удалось улучшить результаты svb до $n=47$:

19 192
23 269
29 430
31 620
37 796
41 895
43 1071
47 1316

Уже для всех этих $n$ имею более 0,6 от предполагаемого максимума.

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

Сейчас буду писать программы для $n>47$, я их ещё не писала.

[dvorkin_sacha]

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

Придуманный алгоритм даёт неплохие результаты.

Алгоритм здесь может быть только один. И так как я в конкурсе не учавствую, то опубликую его за сутки до окончания конкурса и тогда счастливые обладатели самых мощных суперкомпьютеров потеснят верхние ряды, а уважаемая Nataly-Mak извинтся за то, что постоянно меня поддевала. Вообще я считаю этот конкурс завуалированной рекламой суперкомпьютеров, а это ставит участников конкурса в неравные условия: поэтому возмущен этим и поэтому и опубликую алгоритм, до которого сам додумался за один вечер. Только, пожалуйста, подскажите, когда начнутся последние сутки конкурса по московскому времени: хочу быть пунктуальным.

P.S.
Уважаемая Nataly-Mak, с помощью этого алгоритма можно добиться гораздо лучших результатов, чем у Вас, и с помощью обыкновенного компьютера.