Новые задачи, не так то просто Опции

[pegoopik]

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

[alan]

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

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