Factorials

[dimkadimon]

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

Если сможем доказать что существует C так чтобы b(n)<=(log(log n))^C для всех n тогда NP != P.

Ошибка. Тут должно быть (log n)^C.

[Pavlovsky]

Для сокращения перебора можно использовать еще такую эвристику. Запретить операции сложения и вычитания с 1. Естественно кроме начальной операции 2=1+1. То есть у нас последовательности будут состоять только из четных чисел (кроме начальной 1).

[Nataly-Mak]

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

Для сокращения перебора можно использовать еще такую эвристику. Запретить операции сложения и вычитания с 1. Естественно кроме начальной операции 2=1+1. То есть у нас последовательности будут состоять только из четных чисел (кроме начальной 1).

Хорошая идея, но не для меня (ибо я не делаю перебор).

Кстати, найденные мной оптимальные решения для 21! и 30! состоят только из чётных чисел (кроме числа 1).

[Nataly-Mak]

Выходим на финишную прямую:

Цитата:

14 24.32 Valery Pavlovsky Ekaterinburg, Russia 29 Mar 2013 03:45
19 24.00 Vladimir Chirkov Bobruisk, Russia 26 Mar 2013 12:35
22 23.77 Alex Chernov Penza, Russia 27 Feb 2013 10:40
28 23.68 Kalachev Gleb Moscow, Russia 3 Feb 2013 16:52
39 23.31 Viktor Polesov Moskow, Russia 1 Apr 2013 11:27
43 23.15 Gennady Gusev Rybinsk, Russia 31 Mar 2013 16:57
51 22.60 Dmitry Ezhov Sterlitamak, Russia 23 Mar 2013 19:07
53 22.48 Vadim Trofimov Saint Petersburg, Russia 4 Mar 2013 05:49

Осталось 20 дней.
Приведённые конкурсанты довольно активны, за исключением Алексея Чернова, Глеба Калачёва и Вадима Трофимова.
Вчера неплохо подтянулся Геннадий Гусев.
В клубе 23+ четверо россиян. Хороший клуб, но 24+ лучше

[dimkadimon]

Любое решение можно представить из единичек. Например 1, 2, 4, 6, 24, 30, 720, 900, 924, 518400, 12! дает

1=1
2=1+1
4=2*2=(1+1)*(1+1)
6=2+4=(1+1)+(1+1)*(1+1)
24=4*6=(1+1)*(1+1)*((1+1)+(1+1)*(1+1))
30=4+24=(1+1)*(1+1)+(1+1)*(1+1)*((1+1)+(1+1)*(1+1))
720=24*30=(1+1)*(1+1)*((1+1)+(1+1)*(1+1))*((1+1)*(1+1)+(1+1)*(1+1)*((1+1)+(1+1)*(1+1)))
итд...

-- 01.04.2013, 21:25 --

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

Для сокращения перебора можно использовать еще такую эвристику. Запретить операции сложения и вычитания с 1. Естественно кроме начальной операции 2=1+1. То есть у нас последовательности будут состоять только из четных чисел (кроме начальной 1).

Можно но опасно. Иногда нужно использовать +/-1. Экономия от этой евристики совсем небольшая. Если увеличиваем последовательность из n чисел до (n+1) чисел то вместо 3n(n+1)/2 вариантов для нового числа имеем 3n(n-1)/2 вариантов, значит экономим 3n варианта.

[Pavlovsky]

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

Иногда нужно использовать +/-1.

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

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

Экономия от этой евристики совсем небольшая.

Экономия очень большая! Мы увеличиваем глубину перебора на один шаг, при сохранении объема перебора. Ведь экономия начинается уже со второй операции.
1,2,3
1,2,4
Последовательность 1,2,3 и всех ее потомков мы выкидываем из перебора. Уже экономия в два раза!

[mertz]

I added sliding windows, but it did very little to cut run time. A window of 5 would only use the last 5 values. I had a separate window for add, subtract and multiply. It was not effective and did not reduce run times by much.

For 11!, there is only one solution of 12 that starts 1,2,4. I will have to add an option to ignore sequences with odd numbers and run some tests.

The number of updates in the last 24 hours is less than 20. Most of the activity is at the top of the leader board.

The number of people above 20 points has only changed from 77 to 86 in the last month.

Did Al say the scoring system was going to stay for this contest? It did make everyone post their scores.

With Neil and ISS vanishing, will we have to wait until September for Al's next contest?

[Pavlovsky]

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

For 11!, there is only one solution of 12 that starts 1,2,4.

По правилам конкурса достаточно и одного решения.

-- Пн апр 01, 2013 19:35:35 --

Обоснование эвристики запрета операций сложения и вычитания с единицей. Еще раз повторяю это эвристика. Всегда можно привести контрпример, например 1,2,3,9,81,729,720
1) При факторизации N! получается множитель 2^k. Причем k очень большое. Разумно двойки присоединять ко всем числам последовательности.
2) В подавляющем количестве случаев, мы можем заменить число A+1 на число AB+B без потерь в длине последовательности.

[Nataly-Mak]

Ах, какая эвристика упала прямо с неба и прямо в мою голову

Сколько же различных реализаций имеет один и тот же алгоритм!
Я говорила, что довела технику применения алгоритма №1 до совершенства.
Оказалось, ещё не довела
Сейчас осенила новая идея. Сразу попробовала реализовать. И удалось с ходу улучшить решение для 22!, пока только 15 шагов (было 16). Но и то хлеб
Может быть, и оптимальное удастся получить. Во всяком случае, ещё на всех других N надо этот метод попробовать.
Что я только ни пробовала для 22!, 16 шагов --- хоть застрелись. Наконец-то сдвинулась с мёртвой точки.

P.S. Эвристику пока не раскрываю

[Nataly-Mak]

У нас в крманде самый низкий коэффициент 0,809 (34!, имеем 21 шаг при оптимальном в 17 шагов). Все остальные коэффициенты больше.
Повторено 11 рекордных решений.

Недавно я в личной переписке с одним из членов команды сделала мрачный прогноз: "21! мы не возьмём" К счастью, этот прогноз не подтвердился.
Делаю второй мрачный прогноз: "22! мы не возьмём"

[dimkadimon]

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

2) В подавляющем количестве случаев, мы можем заменить число A+1 на число AB+B без потерь в длине последовательности.

Но AB+B занимает две операции, а А+1 только одну. Мои лучшие решения для N=34, 35 и 36 используют +/-1.

[Nataly-Mak]

Эвристика работает
Улучшила решение для 23! тоже на 1 шаг --- пока 16 шагов.

Если сделать все решения плюс 1 от оптимальных, будет совсем не плохо.
Теперь надо для 24! попробовать этот метод. У нас для 24! пока плюс 2 от оптимального, что очень плохо. Надо сделать хотя бы плюс 1 от оптимального.

Дальше лучше уже: 26! - оптимальное, для N=25,27-29 плюс 1 от оптимального, 30! оптимальное.
Ну, а хвост (N>30) похуже.

Эх, спать вот надо, какая жалость

[Pavlovsky]

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

Мои лучшие решения для N=34, 35 и 36 используют +/-1.

Если в последовательности есть числа вида $A \pm 1$, то тогда есть хороший шанс укоротить последовательность на одну операцию, избавившись от этих чисел.

[dimkadimon]

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

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

Мои лучшие решения для N=34, 35 и 36 используют +/-1.

Если в последовательности есть числа вида $A \pm 1$, то тогда есть хороший шанс укоротить последовательность на одну операцию, избавившись от этих чисел.

Не знаю как это сделать. Например имеем 1, 2, 3, 9, 81, 80, 77, 720, 518400, 39916800=11! Как эту последовательность можно преобразовать чтобы убрать 80=81-1?

[Pavlovsky]

Никто и не обещал, что это всегда возможно.
А вот из последовательности 1,2,3,9,81,80,720 число 80 легко убирается. Последние две операции (81-1)*9 заменяем на 81*9-9. 1,2,3,9,81,729,720.

Забавно как эвристика запрета операций с единицей оценивает давний спор о том какие начальные последовательности лучше.

Эвристика согласна, что начало 1,2,3 плохое. А вот вопрос, что лучше 1,2,4,6 или 1,2,4,16 эвристика оставляет открытым. Эвристика считает оба начала переспективными. По-человечески очень мудрое решение. Правда еще добавляет начало 1,2,4,8. Сказать, что это начало совсем плохое, я бы не решился.