Factorials

[whitefox]

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

Вот опять:

Цитата:

5 267 Michael Hürter Saarbrücken, Germany 6 May 2013 17:52
6 268 Alex Chernov Penza, Russia 5 May 2013 19:12

Alex Chernov (вчера) взял решение Michael Hürter (появившееся сегодня) и удлинил его на 1 шаг.

Ещё пример:

3    247    Helge Keller    Karlsruhe, Germany    2 May 2013 18:47
4    248    Robert Gerbicz    Halasztelek, Hungary    27 Apr 2013 23:05

27 апреля Gerbicz взял решение, найденное Helge Keller 2 мая, и удлинил его на один шаг

-- 07 май 2013, 10:19 --

(Gerbicz)

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

Gerbicz

This is your final warning. If you don't stop your accusations then you will be banned from the contest (and perhaps from future AZ contests).

Лично я не заинтересован, чтобы Вас исключили из конкурса (ибо поставил на Вашу победу).
Но Вы, видимо, решили, что бан будет для Вас хорошим выходом.
После конкурса сможете утверждать, что обязательно победили бы, если бы Вас не забанили (разумеется "несправедливо").

Если это не так, повторю совет который давал ранее -- о всех своих подозрениях сообщайте только администратору конкурса, и только в личных сообщениях.
Помните о презумпции невиновности.
Любое публичное обвинение без доказательств это клевета.
Клевета наказуема.

[Nataly-Mak]

Ура! Не могу удержаться, чтобы не показать:

Цитата:

5 259 Alex Chernov Penza, Russia 7 May 2013 12:28

Алексей идёт вперёд! Молодец!
Постоянно заглядываю на конкурс, болею за Алексея

До "золотой рыбки" Алексею осталось сбросить 29 шагов.

[dmd]

dimkadimon в на яхе писал(а):

V[k]=10000 for all k<=N!
V[ai]=0 for all i

k=1
while k<=N!
..next=k+1
..for ai in S
....V[k+ai]=min(V[k+ai],V[k]+1) //for addition
....V[k*ai]=min(V[k*ai],V[k]+1) //for multiplication

....if V[k]+1<V[abs(k-ai)] //for subtraction
......V[abs(k-ai)]=V[k]+1
......next=min(next,abs(k-ai)) //opportunity to go back
....end
..end
..k=next
end

Не могли бы Вы дополнительно прокомментировать Ваш алгоритм. Попробовал его перекодировать в pari/gp

dimkadimon()=
{
  f= 13!; d= divisors(f);
  a= setunion(Set(), [1,2,4,6,36,32,1152,2304,2310]); \\аналог S
  k= setunion(Set(), d);  \\ список всех дивизоров f
  v= vector(#k, X, 10000); \\аналог "V[k]=10000 for all k<=N!", но только для дивизоров
  for(i=1, #a, j= setsearch(k, a[i]); v[j]= 0); \\аналог "V[ai]=0 for all i"
  for(j=1, #k,
   for(i=1, #a,
    \\ сложения
    z= k[j]+a[i]; ij= setsearch(k, z);
    if(ij, v[ij]= min(v[ij], v[j]+1));
    \\ умножения
    z= k[j]*a[i]; ij= setsearch(k, z);
    if(ij, v[ij]= min(v[ij], v[j]+1));
    \\ вычитания
    z= abs(k[j]-a[i]); ij= setsearch(k, z);
    if(ij,
     if((v[j]+1)<v[ij],
      v[ij]= v[j]+1;
      j= min(j, ij)
     )
    )
   )
  );
  \\ итоговый вывод результатов
  for(j=1, #k, if(v[j]<10000, print("j= ",j,"    k= ",k[j],"   v= ",v[j])));
  print();
  print("jmax= ",#k,"    k= ",k[#k],"   v= ",v[#k])
};

в принципе работает, но только для уже наполовину готовой последовательности S.


Допустим пытаюсь достроить 1,2,4,6,36 до оптимального решения 13!, ориентируясь на одно из известных оптимальных решений 1,2,4,6,36,32,1152,2304,2310,2340,2661120,6227020800.

Но S=[1,2,4,6,36] слишком короткая, алгоритм не сумел достроить:

. . .
j= 1511    k= 43545600   v= 8
j= 1515    k= 47900160   v= 8
j= 1528    k= 68428800   v= 10
j= 1535    k= 80870400   v= 7
j= 1540    k= 95800320   v= 9

jmax= 1584    k= 6227020800   v= 10000

Последовательность S=[1,2,4,6,36,32] тоже не достраивается, S=[1,2,4,6,36,32,1152,2304] аналогично, а вот S=[1,2,4,6,36,32,1152,2304,2310] успешно достроилась:

. . .
j= 1577    k= 778377600   v= 4
j= 1579    k= 1037836800   v= 4
j= 1580    k= 1245404160   v= 4
j= 1581    k= 1556755200   v= 5
j= 1582    k= 2075673600   v= 5
j= 1583    k= 3113510400   v= 5
j= 1584    k= 6227020800   v= 3

jmax= 1584    k= 6227020800   v= 3

Вопрос собственно такой: какие входные последовательности использовались для этого алгоритма?

[Nataly-Mak]

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

Последовательность S=[1,2,4,6,36,32] тоже не достраивается, S=[1,2,4,6,36,32,1152,2304] аналогично, а вот S=[1,2,4,6,36,32,1152,2304,2310] успешно достроилась:

Извините, что вмешиваюсь.
Последовательность S=[1,2,4,6,36,32,1152,2304] не достраивается
Но тут остаётся добавить всего 4 шага!
Программа mertz выполняет достраивание этой последовательности до 13! мгновенно:

found 3 solutions for 6227020800 in 11 steps
1,2,4,6,36,32,1152,2304,2310,2340,2661120,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,2695680,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,5405400,6227020800

Сейчас попробую достроить последовательность S=[1,2,4,6,36,32].

Эта последовательность достроилась за 1 мин. 19 сек.
Те же три решения.

-- Вт май 07, 2013 23:29:36 --

Цитата:

Но S=[1,2,4,6,36] слишком короткая, алгоритм не сумел достроить.

Программа mertz достраивает эту последовательность до 13! за 14 мин. 33 сек.
Вот найденные решения:

found 14 solutions for 6227020800 in 11 steps
1,2,4,6,36,144,30,576,546,78624,79200,6227020800
1,2,4,6,36,144,576,540,546,78624,79200,6227020800
1,2,4,6,36,144,576,582,546,78624,79200,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,2661120,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,2695680,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,5405400,6227020800
1,2,4,6,36,38,1444,1440,54720,56160,110880,6227020800
1,2,4,6,36,38,40,1440,54720,56160,110880,6227020800
1,2,4,6,36,40,1440,1404,56160,112320,110880,6227020800
1,2,4,6,36,40,1440,1404,56160,54720,110880,6227020800
1,2,4,6,36,40,1440,57600,56160,112320,110880,6227020800
1,2,4,6,36,40,1440,57600,56160,54720,110880,6227020800
1,2,4,6,36,40,39,1440,56160,112320,110880,6227020800
1,2,4,6,36,40,39,1440,56160,54720,110880,6227020800

Это притом, что у меня очень слабая машина.

[Nataly-Mak]

До кучи --- эксперимент.
Ищу все решения для 13! по программе mertz с применением обеих эвристик:
(обрезка по делителям 13! и "только чётные числа").
Программа работала 2 мин. 22 сек. Найдено 31 решение.

(Оффтоп)

found 31 solutions for 6227020800 in 11 steps
1,2,4,16,12,10,160,156,24960,24948,249480,6227020800
1,2,4,16,12,10,160,156,24960,24948,249600,6227020800
1,2,4,16,12,10,160,156,24960,24948,622702080,6227020800
1,2,4,16,20,36,720,2880,756,2860,2162160,6227020800
1,2,4,16,20,36,720,2880,756,2860,2177280,6227020800
1,2,4,16,20,36,720,2880,756,2860,8236800,6227020800
1,2,4,6,24,22,132,576,600,79200,78624,6227020800
1,2,4,6,24,22,576,600,13200,79200,78624,6227020800
1,2,4,6,24,22,576,600,3600,79200,78624,6227020800
1,2,4,6,24,26,144,576,550,79200,78624,6227020800
1,2,4,6,24,26,576,550,13200,79200,78624,6227020800
1,2,4,6,24,26,576,550,3300,3276,10810800,6227020800
1,2,4,6,24,26,576,550,3300,3276,1886976,6227020800
1,2,4,6,24,26,576,550,3300,3276,1900800,6227020800
1,2,4,6,24,26,576,550,3300,79200,78624,6227020800
1,2,4,6,24,30,144,576,546,78624,79200,6227020800
1,2,4,6,24,30,576,546,13104,78624,79200,6227020800
1,2,4,6,24,30,576,546,3276,3300,10810800,6227020800
1,2,4,6,24,30,576,546,3276,3300,1886976,6227020800
1,2,4,6,24,30,576,546,3276,3300,1900800,6227020800
1,2,4,6,24,30,576,546,3276,78624,79200,6227020800
1,2,4,6,24,576,572,600,3600,3024,10886400,6227020800
1,2,4,6,24,576,572,600,3600,3024,1729728,6227020800
1,2,4,6,24,576,572,600,3600,3024,2059200,6227020800
1,2,4,6,36,144,576,540,546,78624,79200,6227020800
1,2,4,6,36,30,144,576,546,78624,79200,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,2661120,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,2695680,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,5405400,6227020800
1,2,4,6,36,40,1440,1404,56160,112320,110880,6227020800
1,2,4,6,36,40,1440,57600,56160,112320,110880,6227020800

В программе mertz реализован поиск от 4-х различных баз данных:
последовательности из 4 членов (Base 4), из 5 членов (Base 5), из 6 членов (Base 6) и из 7 членов (Base 7).
Понятно, что решения для 13! надо искать от Base 7. Можно, конечно, и от других базовых последовательностей, но это будет дольше.

Ради интересна проверила тот же поиск 13! (с двумя эвристиками) от Base 5 и от Base 6.
Те же 31 решения и то же время: 2 мин. 22 сек.
А мне почему-то думалось, что от более коротких последовательностей поиск будет выполняться дольше.

[mertz]

The different bases are just used to break the work down into smaller pieces.

[Nataly-Mak]

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

The different bases are just used to break the work down into smaller pieces.

Google перевёл так:

Цитата:

Различные базы используются только нарушить работу на более мелкие куски.

Ничего не поняла

Когда работала с программой, всегда для решений в 10-11 шагов использовала Base 7, для решений в 9 шагов - Base 6, для решений в 8 шагов - Base 5, для решений в 7 шагов - Base 4. Вроде всё получалось нормально.
Просто интуитивно так решила рассуждала: чем длиннее решение, тем длиннее берём базовые последовательности для его построения.
Первоначально в программе была только одна база - Base 5. Потом появились другие, но я не стала спрашивать о назначении других, использовала их по своему разумению

Вот он --- языковой барьер

-- Ср май 08, 2013 06:05:30 --

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

На Yahoo я описал свой Dynamic Programming метод: http://tech.groups.yahoo.com/group/AlZi ... ssage/5629

Суть в том что мы можем решить упрощенную задачу: найти оптимальное SLP в котором все операции используют одно из чисел в последовательности S=a1, a2, ..., ai. Tо есть мы берем S и оптимально достраиваем еe до N! используя числа из S. Чтобы реализовать этот метод надо использовать условие что все числа делители N!.

Нашла описание метода dimkadimon.
Мне тоже стал интересен вопрос, заданный dmd: какие последовательности S мы берём в качестве начальных последовательностей, чтобы их потом достраивать.
И почему некоторые последовательности, выбранные dmd, не достраиваются до решения 13!
Тогда как программой mertz эти начальные последовательности очень быстро достраиваются (даже безо всяких эвристик).

[dimkadimon]

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

Последовательность S=[1,2,4,6,36,32] тоже не достраивается, S=[1,2,4,6,36,32,1152,2304] аналогично, а вот S=[1,2,4,6,36,32,1152,2304,2310] успешно достроилась:

Метод использует только операции в которых хотя бы одно число из S. Допустим S=[1,2,4,6,36,32,1152,2304,2310] тогда

2340=2304+36
2695680=2340*1152
6227020800=2695680*2310

Если S=[1,2,4,6,36,32,1152,2304] то можно получить 2310=2304+6, а вот умножать на 2310 уже нельзя. Без этого наверно нельзя получить 13! из его делителей. Вам надо проверить сам путь достройки.

Я этот метод использовал как быстрый способ для определения оценки для незаконченой последовательности S. Конечно для этого можно использовать другие способы, как например поиск на следующие k шагов. Когда у нас есть оценка для каждого S тогда можно использовать например beam search и сортировать последовательности по их оценке. Свой метод с beam search я описал на yahoo.

[Nataly-Mak]

Ах, вот как близко "золотая рыбка"
Умеют же люди!

Цитата:

1 233 Wes Sampson La Jolla, California, United States 8 May 2013 00:53

[Pavlovsky]

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

[dimkadimon]

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

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

240 это 3-е место...

[dmd]

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

Метод использует только операции в которых хотя бы одно число из S.

Ну это видно невооружённым глазом в Вашем коде. Именно так буквально и транслировал его в код для pari/gp.

[Nataly-Mak]

Фантастика!
Wes Sampson до решения 230 шагов остался всего 1 шаг --- в буквальном смысле

[Pavlovsky]

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

240 это 3-е место...

Очевидно у победителя будет результат заметно меньше 230. С результатом 240 даже в пятерку попасть проблематично.

[Nataly-Mak]

Цитата:

1 231 Wes Sampson La Jolla, California, United States 8 May 2013 11:35
2 234 Jarek Wroblewski Wroclaw, Poland 9 May 2013 04:44

Кто же будет первым
Сильные противники, интересная борьба!