Версия для печати темы

Автор: pegoopik 20.5.2017, 14:55

Предисловие. Я пытаюсь не шлака добавить, а только действительно интересные задачи.

Несколько зим назад я предложил на сайт две задачи на разные темы:

1. Физика, чуть углубляясь в оптику, но с расчетом на эрудицию
2. Теория игр. Три полосы, фишки, выигрышная стратегия и прочее.

По первому вопросу так и не получил ни одного правильного ответа. А по второму так и вовсе получил резолюцию вида:

Вы не хотите решать самостоятельно, вы используете нас, чтобы получить ответ на вашу задачу.

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

Обе задачи имеют красивые решения. И я с огромным удовольствием видел бы их на сайте.

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

==============================

Формулировка:

Есть множество 2х мерных векторов, найти такое его подмножество, которое даст в сумме вектор максимальной длины.

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

В лоб решение - это О(2^N), чуть подумав получаем O(N^2), оптимизировав можем получить O(N*Ln(N)), но если перед расчетами отсортировать вектора некоторым образом, получаем O(N).
Всё портит сортировка, т.к. она уже O(N*Ln(N)), но формулировку можно составить по-разному.

==============================


Администраторам ресурса:
Если вы и это забреете, я уж и не знаю, как к вам попадают новые задачи.

Автор: alan 20.5.2017, 15:27

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

К счастью или к сожалению, но на сайт задачи проходят только если интересность их условия превосходит сложность решения. Обычно прежде чем опубликовать задачу самостоятельно решает хотя бы 4 модератора. Задач много - на всех модераторов не хватает - поэтому задачи непроизвольно проходят естественный отбор по признаку интересности модераторам, непрошедшие оказываются погребены под кучей новых поступлений.

Автор: pegoopik 20.5.2017, 15:31

Вот как, не знал, спасибо!
Но тем не менее я предложил 2 задачи в 2014 году. Как-то долго....
Можно как-то форсировать?
Все решения задач у меня есть.

Автор: Лиходей 21.5.2017, 21:58

А можно в ПМ задачу по теории игр?

Автор: alan 21.5.2017, 22:05

Это только три года. Не так уж и много.
1. Я не помню задачи которая бы дошла до сайта меньше чем за год.
2. Есть задачи, которые были опубликованы спустя 5-6 лет. Может даже больше, но сейчас сходу не нашел.
3. Есть не опубликованные задачи многолетней давности, которые мы еще 6 лет назад решили что опубликовать нужно, но не можем это сделать по некоторым причинам - сложности формулировки условия, или недостатка решивших, и др.
Так что 3 года это не большой срок.

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

Автор: pegoopik 26.5.2017, 10:07

Отправил.