Factorials

[Nataly-Mak]

Стартовал новый конкурс программистов на сайте Al Zimmermann
http://www.azspcs.net/Contest/Factorials

На этом сайте давно не проводились конкурсы.
Теперь вот снова начались. Это очень популярные международные конкурсы.
Не прошли и сутки, а уже почти 100 зарегистрированных участников.

В OEIS есть последовательность по конкурсной задаче - A217032.

Вот так делается 12! за 10 шагов:

1,2,4,6,24,30,720,900,924,518400,12!

Сразу пришла мысль: нельзя ли применить знаменитый алгоритм наращивания
Вроде бы можно
Вот так делаем 13! :

1,2,4,6,24,30,720,900,924,518400,12!,3,10,13,13!

Это будет 14 шагов.
Если это правильно, то точно так же можно написать вручную (без всяких программ!) последовательности для всех задач от 13! до 37!

Сомнение у меня такое: разрешается ли в последовательности использовать факториалы? Например, в моём примере используется 12!
Но в описание я не вижу, что это не разрешается. А почему бы и не использовать? Ведь 12! это такое же число (479001600).

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

-- Вс янв 20, 2013 11:53:10 --

Первые россияне на конкурсе:

Цитата:

8 17.70 Vladimir Romanov Kurgan, Russia 20 Jan 2013 07:39
12 15.88 Minin Nikita Moscow, Russia 20 Jan 2013 01:04
23 12.29 Nikolay Kurtov Novosibirsk, Russia 19 Jan 2013 21:59
25 12.09 Dmitry Shpika Krasnodar, Russia 19 Jan 2013 21:47
48 4.05 Kalachev Gleb Moscow, Russia 20 Jan 2013 07:33
70 .92 Alex Chernov Penza, Russia 20 Jan 2013 06:46
85 .61 Prokhorov Maxim Voronezh, Russia 19 Jan 2013 19:19

Как всегда, болею за всех россиян. Вперёд, Россия!

Очень радует, что международные конкурсы программистов становятся всё более популярными в России.

[Gerbicz]

Nataly (other topic)
"The fact that I do not participate in the competition officially, does not mean that I will not solve the problem and discuss it on the forum. Now I have more freedom! I do not participate in the competition, therefore, I do not perform any rules "

from azspcs.net:
"There are two types of information that you are forbidden to post. The first is specific solutions. The second is code. You may post scores, so if you want to tell everyone that you got a raw score of 99 for n = 20 (whether true or not), go right ahead. Officially, you may also discuss the algorithms you are using but be aware that doing so annoys some people."

I would say even you don't participate t in the contest you have to keep the rules. My suggestion: start in the contest and close this topic. Why Russians are cheating in every contests? I really don't know. Isn't it better to reach the results using your own brain?

[Nataly-Mak]

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

Why Russians are cheating in every contests? I really don't know.

Россияне никого не обманывали и не обманывают, и не собираются обманывать! Зарубите это себе на носу.

Меня совершенно не интересуют ваши предложения. Я собираюсь обсуждать задачу не с вами.
А если её никто не хочет здесь обсуждать, буду решать её сама; могу сделать страницу на своём сайте.

[Toucan]

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

from azspcs.net:
"...Officially, you may also discuss the algorithms you are using but be aware that doing so annoys some people."
...
Why Russians are cheating in every contests? I really don't know.

Gerbicz, a warning for groundless accusations and offtopic. Discussing the algorithms is allowed by the official rules of the contest so such discussion is not cheating and your annoyance is just your problem.

Btw, you do quotation incorrectly: to quote a message fragment, select it with mouse and click the ("Insert") button under the message text.

[jcmeyrignac]

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

Nataly (other topic)
I would say even you don't participate t in the contest you have to keep the rules. My suggestion: start in the contest and close this topic. Why Russians are cheating in every contests? I really don't know. Isn't it better to reach the results using your own brain?

Robert, I think that you are mistaking cheating and collaboration, and I don't see why you see cheating everywhere.

You have to realize that there are two ways to participate in such contests:
1) alone, and in this case, you believe in competition. It's the "american point-of-view": my value is what I can do alone, and I want to measure my value by doing my best.
2) in a team, and in this case, you believe in collaboration. It's the "russian point-of-view": my value is what I can provide to the team.

Anyway, I agree that Nataly should not disclose solutions, at least for N>=13.
Proving that you can extend a N-1 solution to N is nice, but please, do not disclose better results.

Do you know where we can find solutions for N=1 to 12 ?

[Nataly-Mak]

jcmeyrignac в сообщении #674121 писал(а):

Anyway, I agree that Nataly should not disclose solutions, at least for N>=13.
Proving that you can extend a N-1 solution to N is nice, but please, do not disclose better results.

Я больше не буду
Но я хотела показать алгоритм наращивания на конкретном примере. К тому же, это совсем не лучшее решение. Правда ведь? 14 шагов - это очень много!

-- Вс янв 20, 2013 17:12:47 --

jcmeyrignac в сообщении #674121 писал(а):

Do you know where we can find solutions for N=1 to 12 ?

Я знаю только последовательность в OEIS - A217032.
Что есть ещё?

[jcmeyrignac]

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

Я больше не буду
Но я хотела показать алгоритм наращивания на конкретном примере. К тому же, это совсем не лучшее решение. Правда ведь? 14 шагов - это очень много!

Indeed !

I just found the solutions published by Stan Wagon (it was hidden in his forum):
http://mathforum.org/wagon/current_solu ... s1153.html

In my opinion, the above page discloses a lot more than Natalya's message.

[Nataly-Mak]

jcmeyrignac в сообщении #674133 писал(а):

In my opinion, the above page discloses a lot more than Natalya's message.

Действительно

И вот вижу на указанной странице:

...10!, 10!^2,...

Моё сомнение развеялось: можно использовать факториалы в последовательности.

На указанной странице даже программка есть, кажется, для Mathematica.
И метод решения задачи описывается. Жаль, что не умею читать по-английски

[Gerbicz]

jcmeyrignac
"You have to realize that there are two ways to participate in such contests:"
Yes, but Nataly doesn't want to participate in the contest, just giving out the solutions/methods.

"Anyway, I agree that Nataly should not disclose solutions, at least for N>=13."
On the previous contest their discussion was 67 pages long. You can ask it, but my wild guess that nobody can stop them.

Toucan
"such discussion is not cheating and your annoyance is just your problem."
So annoying other people is OK in Russia. In rest of the world it is not OK.

[Xaositect]

I was interested in this topic (complexity of defining integers) a while ago and computed a database of all numbers of complexity $\leq 7$ (by simple exhaustive search of programs).
All straight-line programs for factorials up to 7! are under the spoiler

(Оффтоп)

1
---
1, 2
---
1, 2, 3, 6
1, 2, 4, 6
---
1, 2, 4, 6, 24
---
1, 2, 3, 4, 12, 10, 120
1, 2, 3, 5, 8, 15, 120
1, 2, 3, 5, 8, 24, 120
1, 2, 3, 5, 8, 40, 120
1, 2, 3, 5, 10, 12, 120
1, 2, 3, 5, 15, 8, 120
1, 2, 4, 5, 20, 100, 120
1, 2, 3, 5, 25, 24, 120
1, 2, 3, 5, 25, 125, 120
1, 2, 3, 6, 12, 10, 120
1, 2, 3, 6, 18, 20, 120
1, 2, 3, 9, 12, 10, 120
1, 2, 3, 9, 12, 108, 120
1, 2, 3, 9, 10, 12, 120
1, 2, 3, 9, 11, 121, 120
1, 2, 4, 3, 12, 10, 120
1, 2, 4, 5, 6, 20, 120
1, 2, 4, 5, 6, 24, 120
1, 2, 4, 5, 6, 30, 120
1, 2, 4, 5, 10, 12, 120
1, 2, 4, 5, 20, 6, 120
1, 2, 4, 5, 20, 24, 120
1, 2, 4, 5, 25, 24, 120
1, 2, 4, 5, 25, 30, 120
1, 2, 4, 5, 25, 125, 120
1, 2, 4, 6, 5, 30, 120
1, 2, 4, 6, 5, 20, 120
1, 2, 4, 6, 5, 24, 120
1, 2, 4, 6, 10, 12, 120
1, 2, 4, 6, 10, 20, 120
1, 2, 4, 6, 10, 60, 120
1, 2, 4, 6, 12, 10, 120
1, 2, 4, 6, 16, 20, 120
1, 2, 4, 6, 24, 5, 120
1, 2, 4, 6, 24, 20, 120
1, 2, 4, 6, 24, 30, 120
1, 2, 4, 6, 24, 96, 120
1, 2, 4, 6, 24, 144, 120
1, 2, 4, 6, 36, 30, 120
1, 2, 4, 8, 32, 30, 120
1, 2, 4, 8, 64, 56, 120
1, 2, 4, 8, 64, 60, 120
1, 2, 4, 8, 7, 15, 120
1, 2, 4, 8, 12, 10, 120
1, 2, 4, 8, 10, 12, 120
1, 2, 4, 8, 16, 15, 120
1, 2, 4, 8, 16, 128, 120
1, 2, 4, 8, 32, 128, 120
1, 2, 4, 8, 64, 128, 120
1, 2, 4, 16, 8, 128, 120
1, 2, 4, 16, 12, 10, 120
1, 2, 4, 16, 8, 15, 120
1, 2, 4, 16, 6, 20, 120
1, 2, 4, 16, 14, 30, 120
1, 2, 4, 16, 15, 8, 120
1, 2, 4, 16, 15, 30, 120
1, 2, 4, 16, 15, 60, 120
1, 2, 4, 16, 20, 6, 120
1, 2, 4, 16, 32, 30, 120
1, 2, 4, 16, 64, 60, 120
---
1, 2, 3, 9, 27, 729, 720
1, 2, 3, 9, 81, 80, 720
1, 2, 3, 9, 81, 729, 720
1, 2, 4, 6, 24, 30, 720
1, 2, 4, 16, 20, 36, 720
---
1, 2, 3, 6, 12, 72, 70, 5040
1, 2, 3, 6, 36, 72, 70, 5040
1, 2, 3, 9, 8, 72, 70, 5040
1, 2, 3, 9, 81, 72, 70, 5040
1, 2, 4, 6, 12, 72, 70, 5040
1, 2, 4, 6, 36, 35, 140, 5040
1, 2, 4, 6, 36, 35, 144, 5040
1, 2, 4, 6, 36, 35, 1260, 5040
1, 2, 4, 6, 36, 72, 70, 5040
1, 2, 4, 6, 36, 144, 35, 5040
1, 2, 4, 6, 36, 144, 140, 5040
1, 2, 4, 6, 36, 144, 5184, 5040
1, 2, 4, 6, 36, 1296, 1260, 5040
1, 2, 4, 8, 9, 72, 70, 5040
1, 2, 4, 8, 64, 72, 70, 5040
1, 2, 4, 16, 18, 72, 70, 5040
1, 2, 4, 16, 20, 256, 252, 5040
1, 2, 4, 16, 64, 63, 80, 5040
1, 2, 4, 16, 64, 80, 63, 5040
1, 2, 4, 16, 64, 80, 5120, 5040
1, 2, 4, 16, 256, 20, 252, 5040
1, 2, 4, 16, 256, 252, 20, 5040

I do not intend to participate in contest, but maybe we can discuss some ideas here.

[Joker_vD]

(Оффтоп)

Gerbicz
If you don't see difference between "being annoyed by someone's actions which don't actually affect you or your well-being" (that's your case) and "being annoyed by someone's actions which directly affect you" (like, someone is shouting in your ear), then there is nothing much to discuss.

[jcmeyrignac]

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

jcmeyrignac
"You have to realize that there are two ways to participate in such contests:"
Yes, but Nataly doesn't want to participate in the contest, just giving out the solutions/methods.

And what is the problem ?
Personally, I made it clear that I don't want to have spoilers for larger solutions, and I can do nothing more than that, can I ?
Being angry or furious is useless, just be frank and tell them what you want.
In the worst case, don't come here.

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

"Anyway, I agree that Nataly should not disclose solutions, at least for N>=13."
On the previous contest their discussion was 67 pages long. You can ask it, but my wild guess that nobody can stop them.

And why is this a problem ?
I find it pretty cool to have a space for discussion.
Such contests are here to stimulate imagination and coding performance.
I enjoyed my best moments when I collaborated with other great minds, not when I was trying very hard alone.
Sometimes a small comment would lead to a massive improvement, I'd like to encourage lateral thinking.

[Nataly-Mak]

Хорошая головоломка
Сейчас немножко поломала голову, нашла для 13! последовательность в 12 ходов.
В-о-о-о-т! Показанная выше последовательность в 14 ходов никуда не годится, это просто черновая разминка.

Теперь встаёт вопрос теоретических оценок оптимальных решений.
Для N=12 доказано, что минимальное число ходов 10.
Для N=13 сколько минимум?

Глядя на последовательность в OEIS, можно сделать вывод, что число шагов
$Q_n\leqslant Q_{n+1}$

Верно ли это?

Эх! Обсчиталась, пока только 13 ходов для 13!
Буду дальше голову ломать

[Gerbicz]

jcmeyrignac:
"I find it pretty cool to have a space for discussion."
After each contest there is a public discussion on yahoo about the contest. I really enjoed these, even when I have not participated on a contest. Why is not enough for them?

"Such contests are here to stimulate imagination and coding performance."
I can only agree with you. But tell me, if you can get free the algorithms and ideas or even optimal sequences for factorials then what is improved? Nothing, only cheating capability.

[svb]

Пока нашел для $N=13,14,15$ решения $step=12,13,14$.