Al Zimmermann - Sums and Products

[12d3]

Полученные мной рекорды неплохо описываются формулой $\displaystyle f(n)=\frac{cn^2}{\ln^3 n}$, за исключением первой пары-тройки значений $n$. Интересно, найдется ли этому теоретическое объяснение.

[dimkadimon]

Спросил у Ала на его форуме. Как я и ожидал, правила не изменились. Нельзя показывать код и решения. Алгоритмы можно обсуждать и это даже поощряется.

[dimkadimon]

Получил первые 9 оптимальных решений. Задача совершено скучная и 25.000 будет через неделю или меньше. Гонка к первому оптимальному результату. Мой интерес резко падает.

[whitefox]

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

Как я и ожидал, правила не изменились.

Вообще-то, изменились. Помимо кода под запрет попали и детальные алгоритмы. Но что такое "детальный алгоритм" не определено. Как пример детального алгоритма Al указывает псевдокод, но псевдокод бывает разный, например:

Используется синтаксис C++

int main()
{
    int n;
    cin >> n;
    int best_raw_score = get_best_raw_score(n);
    cout << best_raw_scores;
}

Так где граница между "детальными" и "не детальными" алгоритмами?

[Pavlovsky]

whitefox в сообщении #1074222 писал(а):

Так где граница между "детальными" и "не детальными" алгоритмами?

Самоцензура и здравый смысл вам помогут.

[whitefox]

Раз Al вообще ввёл какие-то ограничения — значит он не очень-то рассчитывает на "самоцензуру и здравый смысл" конкурсантов. В противном случае никакие запреты не нужны. И так понятно, что конкурсанты в здравом уме не сообщат соперникам свои "победоносные секреты".

-- 17 ноя 2015, 11:51 --

Al Zimmermann писал(а):

The only real change is that if you calculate the best raw scores for each value of n, you can't publish them in the forum.

Это можно понять как запрет на публикацию теоретических оптимумов.

Кроме того возникает ряд вопросов:

• Можно ли публиковать best raw scores не для всех n, а только для некоторых?
• Можно ли публиковать best raw scores полученные не вычислением, а в результате прозрения (гипотетические best raw scores)?
• Можно ли публиковать свои raw scores (whether true or not), которые могут оказаться best raw scores, а могут и нет?

[dimkadimon]

whitefox в сообщении #1074225 писал(а):

Раз Al вообще ввёл какие-то ограничения — значит он не очень-то рассчитывает на "самоцензуру и здравый смысл" конкурсантов. В противном случае никакие запреты не нужны. И так понятно, что конкурсанты в здравом уме не сообщат соперникам свои "победоносные секреты".

-- 17 ноя 2015, 11:51 --

Al Zimmermann писал(а):

The only real change is that if you calculate the best raw scores for each value of n, you can't publish them in the forum.

Это можно понять как запрет на публикацию теоретических оптимумов.

Кроме того возникает ряд вопросов:

• Можно ли публиковать best raw scores не для всех n, а только для некоторых?
• Можно ли публиковать best raw scores полученные не вычислением, а в результате прозрения (гипотетические best raw scores)?
• Можно ли публиковать свои raw scores (whether true or not), которые могут оказаться best raw scores, а могут и нет?

Я думаю на все эти вопросы ответ "нет". Ал достаточно ясно ответил на форуме. Зачем вы усложняете себе жизнь?

[whitefox]

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

Зачем вы усложняете себе жизнь?

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

Мой интерес резко падает.

Имхо, Al совершенно напрасно держит в тайне полученные рекорды. Знание их только усилило бы интригу и добавило интереса соревнованию. Представьте, что на как-нибудь спортивном турнире результаты участников держались бы в секрете. Интересно бы было следить за таким соревнованием? А участвовать в нём интересно?

Также интереса соревнованию, имхо, добавляет свободное обсуждение алгоритмов. Что с того если кто-нибудь приведёт детальный алгоритм? Это только подхлестнёт интерес к соревнованию у отстающих, и не позволит лидерам почивать на лаврах, вынудив всех конкурсантов ещё активнее шевелить мозгами в поисках ещё лучшего алгоритма.

А без всего этого, имхо, соревнование становится скучным и унылым, увы.

(Оффтоп)

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

Ал достаточно ясно ответил на форуме.

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

[Toucan]

dimkadimon, замечание за избыточное цитирование.

[Pavlovsky]

whitefox в сообщении #1074259 писал(а):

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

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

-- Вт ноя 17, 2015 15:54:45 --

whitefox в сообщении #1074259 писал(а):

Что с того если кто-нибудь приведёт детальный алгоритм? Это только подхлестнёт интерес к соревнованию у отстающих,

Отстающий, тупо скопировав код, поднимется чуть выше в рейтинге. Поощрять лентяев непедагогично.

[whitefox]

И при этом результаты команд не объявляют до завершения финала?

-- 17 ноя 2015, 14:07 --

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

тупо скопировав код

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

[Pavlovsky]

1) В конкурсе люди борются не только за первые места. У каждого свои цели. Кто то борется за попадание в первую сотню. Публикация кода делает их участие бессмысленным.
2) Публикация кода = публикация решения. Тогда конкурс превращается непонятно во что.

[whitefox]

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

[Gassa]

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

Получил первые 9 оптимальных решений.

Хм. Девять доказанно оптимальных - или просто девять текущих максимумов?

[dimkadimon]

Gassa в сообщении #1074336 писал(а):

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

Получил первые 9 оптимальных решений.

Хм. Девять доказанно оптимальных - или просто девять текущих максимумов?

Только текущих максимумов. Конечно рано радоваться.