Factorials

[Nataly-Mak]

Pavlovsky
В-о-о-о-т! Теперь обещание выполнено и даже перевыполнено
Можно почивать на лаврах

[Pavlovsky]

Я уже неделю не работаю. Работают программы. Правда мозг, в отличие от компьютера выключить нельзя. В голову постоянно лезут всякие мысли. Опять пришла в голову супер-пупер идея. Вот думаю, стоит ли ее реализовывать?! Кодировать много, а гарантии успеха нет.

[Nataly-Mak]

Ну, если супер-пупер идея, конечно, стоит попробовать

Кстати, расслабляться нельзя, у dimkadimon ведь тоже программы работают
Так что, 12-ое место надо держать зубами!

[Pavlovsky]

Буду ли реализовывать супер-пупер идею еще не решил. Поэтому публикую ее для всеобщего обсуждения.

Пусть у нас есть множество делителей N!, которые можно построить меньше чем за K операций. Например их можно получить полным перебором последовательностей длины K и меньше. Для каждого делителя, вошедшего в множество, у нас определено минимальное количество операций необходимое для его построения.

Составим список всех разложений N! на множители. В качестве множителей будем использовать только числа из полученного множества. В список будем включать разложения, нижняя оценка количества операций которых меньше порогового значения (например текущий рекорд для N!). Нижнюю оценку количества операций можно получить по формуле:
НО = КУ + МКО
НО - Нижняя Оценка;
КУ - Количество умножений, необходимое чтобы получить N! из множителей;
МКО - Из чисел вошедших в разложение выбираем число требующее максимальное количество операций на его построение.

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

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

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

[dimkadimon]

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

Австралия пройдена. У dimkadimon было достаточно времени, чтобы защитить свою позицию. Я ждал долго когда он поднимется вверх.

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

Эх... увы мои программы пришли в тупик. Я знал что этот момент скоро настанет.

[Nataly-Mak]

Сегодня у нас играли

Цитата:

12 24.53 Valery Pavlovsky Ekaterinburg, Russia 11 Apr 2013 03:21
26 23.74 Viktor Polesov Moskow, Russia 11 Apr 2013 17:43

[Nataly-Mak]

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

11 24.47 Dmitry Kamenetsky Adelaide, Australia 14 Mar 2013 22:17
12 24.46 Lucien Pech Zürich, Switzerland 30 Mar 2013 17:40
13 24.42 Valery Pavlovsky Ekaterinburg, Russia 7 Apr 2013 04:37
14 24.41 Ashley Wood Guildford, United Kingdom 4 Apr 2013 22:13
15 24.40 Michael Hürter Saarbrücken, Germany 6 Apr 2013 20:17
16 24.37 Andy Sloane Sunnyvale, California, United States 8 Feb 2013 21:39

Очень плотная группа. Надо из нее быстрее выбираться, а то затопчут.

Здесь не менее плотно:

Цитата:

24 23.77 Alex Chernov Penza, Russia 27 Feb 2013 10:40
25 23.74 Johan Roos Lund, Sweden 20 Feb 2013 08:23
26 23.74 Viktor Polesov Moskow, Russia 11 Apr 2013 17:43
27 23.74 Helge Keller Karlsruhe, Germany 5 Apr 2013 13:05
28 23.74 Heinz Druckmüller Schwaz, Austria 8 Apr 2013 09:50
29 23.72 Walter Schneider Reute, Baden-Württemberg, Germany 15 Feb 2013 14:24

[Nataly-Mak]

И ещё кандидат на 12-ое место (а может, и повыше):

Цитата:

13 24.51 Michael Hürter Saarbrücken, Germany 11 Apr 2013 21:16

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

Сейчас в основном ищу идеи для больших N, как улучшить хвост.
Этот хвост у нас сейчас выглядит так:

30 31 32 33 34 35 36 37
17 18 18 18 17 19 18 20
17 19 20 20 21 22 22 23

(вторая строка - оптимальные решения)
Плохо выглядит, надо сказать. Есть решения плюс 4 от оптимального, это никуда не годится!

[Nataly-Mak]

Повисла напряжённая тишина
Последние выходные, заключительные шаги...
Всё очень трудно.
Как я уже сказала, мне не хватает:
а) мощности машины;
б) программного обеспечения всех алгоритмов.
Программисты команды работают очень много, но... всё равно мне программ не хватает.
Это моя беда - что совсем разучилась писать хорошие программы

Ну, если не можешь, то и не берись, а взялась, то не хнычь
Так и вот, сейчас, например, в полуручном режиме грызу 37!
То есть пытаюсь реализовать алгоритм:

$37! = A \cdot B \cdot C$
$37! = 335780006100 \cdot (18!)^2$
$A=(18!)^2$

Далее пытаюсь найти хорошие множители B и C. И делаю это буквально вручную, с помощью калькулятора.
Пишу так на листе бумаги:

335780006100/2=167890003050
335780006100/3=111926668700
335780006100/4=83945001525
335780006100/5=67156001220
335780006100/6=55963334350
335780006100/7=47968572300
335780006100/10=33578000610
335780006100/11=30525455100
...
335780006100/100=3357800061
...
335780006100/2100=159895241
335780006100/3300=101751517
...
335780006100/7700=43607793
...

И так далее. Сколько будет таких разложений
$335780006100=B \cdot C$ ?
Очень много!
Вручную всё это проверить нереально.
Проверяю я составление чисел B и C по программе mertz, понятное дело.
Но... полностью процесс не автоматизирован. Надо, чтобы всё это делалось программой: разложение на множители и проверка всех разложений.
Вот --- алгоритм я знаю, схему его реализации представляю, ручками это делать могу, а вот программу сделать не могу.
Получаю "двойку" по программированию

[dmd]

Количество делителей этого числа не очень большое, всего 2304, т.к. в нём относительно мало двоек и троек.

? d=37!/18!^2
%76 = 335780006100
?
? print(factorint(d))
[2, 2; 3, 1; 5, 2; 7, 1; 11, 1; 19, 1; 23, 1; 29, 1; 31, 1; 37, 1]
?
? w=divisors(d);
?
? #w
%78 = 2304
?
? for(i=1, #w, q= w[i]; g= d/q; print("    q= ",q,"    g= ",g));
    q= 1    g= 335780006100
    q= 2    g= 167890003050
    q= 3    g= 111926668700
    q= 4    g= 83945001525
. . .

У меня другая проблема - получаю "двойку" по матмоделированию. Мой субъективный критерий математической профпригодности - способность составить считабельную матмодель. Увы и ах - для задачи этого конкурса я не сумел составить считающую матмодель. Все мои усилия безжалостно проглатываются черной дырой экспоненциальности. Так как постоянно алгоритмически блуждаю вокруг построения последовательностей. А это явно не считабельное направление для больших N, не говоря уже про 100!. Так что все участники конкурса, вошедшие в область 24+, успешно подтвердили свою профпригодность. Уже жду-недождусь разбор полётов после окончания конкурса.

[Nataly-Mak]

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

Количество делителей этого числа не очень большое, всего 2304, т.к. в нём относительно мало двоек и троек.

По меркам автоматического счёта это не много, а по меркам ручной работы даже чересчур много. Представьте себе: вручную поделить 2304 раза, потом 2304 раза проверить разложения. Крыша точно поедет

[Pavlovsky]

Давненько не публиковал свои результаты. Для N<28, мои результаты совпадают с рекордными результатами.
Первая строка N. Вторая строка текущие рекорды. Третья строка мои результаты.

28   29   30   31   32   33   34   35   36   37
16   17   17   18   18   18   17   19   18   20
17   17   18   19   18   20   17   20   19   21

[Nataly-Mak]

Для сравнения --- результаты нашей команды:

28 29 30 31 32 33 34 35 36 37
16 17 17 18 18 18 17 19 18 20
17 18 17 19 20 20 21 22 22 23

Есть у нас один результатик лучше - оптимальное решение для 30!

Pavlovsky
странно, что вы не нашли оптимальное решение для 30!
Я нашла его по алгоритму №1 в полуручном режиме (только воспользовалась программой mertz при составлении множителя K в разложении).
Включите ЕИ

А у нас безобразные решения для 34! и 36! --- аж плюс 4 от оптимального. И ничего не могу найти

-- Вс апр 14, 2013 22:36:35 --

С германцем, похоже, придётся драться за 12-ое место

Цитата:

12 24.58 Valery Pavlovsky Ekaterinburg, Russia 14 Apr 2013 04:35
13 24.57 Michael Hürter Saarbrücken, Germany 13 Apr 2013 14:08

[Nataly-Mak]

От немца оторвались и 11-ое место уже не такое недосягаемое

Цитата:

11 24.69 Lucien Pech Zürich, Switzerland 9 Apr 2013 17:47
12 24.63 Valery Pavlovsky Ekaterinburg, Russia 15 Apr 2013 03:37
13 24.57 Michael Hürter Saarbrücken, Germany 13 Apr 2013 14:08

Вперёд, только вперёд!

[Pavlovsky]

Забавно, теперь каждый новый результат, будет приводить к перемещению вверх по турнирной лестнице. Вплоть до 5-го места! Вот только где брать эти новые результаты? Вроде есть очень хорошие шансы улучшить результаты для N=28,30. Решения, на единицу хуже рекорда, программа выдает пачками. Но где искать рекордные результаты для этих N - непонятно.

После того, как программы нашли рекорд для N=34, чего я вообще не ожидал. Полагаю потенциал, моих программ позволяет выйти на 25 баллов. Но для этого нужна удача и время. На удачу в этом конкурсе мне жаловаться не приходится. Поэтому требовать от фортуны еще подарки судьбы, как то не этично. А времени не хватает катострофичеси. За оставшееся время максимум чего можно получить еще 1-2 новых результата.