Хм, вообще-то там проходило совсем тупое решение с двумя циклами:
for (long i = 0; 2 * i * i <= x; i++) for (long j = i; i * i + j * j <= x; j++) if (i * i + j * j == x) ans++;
По крайней мере на Java, на Python может и не проходило
Задача легко решается за O(N^2)
Добавим к p для каждого ящика его w. Теперь несложно доказать (но мне влом писать), что существует оптимальная башня в которой ящики идут сверху вниз в порядке возрастания p. Теперь посчитаем следующую динамику — какой наименьший вес имеет башенка из i ящиков если ящики можно выбирать из j первых. Пересчет очевиден.
Вынужден не согласится. Я не видел еще ни одного сколь-нибудь длинного подобного документа, в котором нету ничтожных пунктов. Это делается, чтобы люди считали, что чего-то они сделать не могут, тогда как на самом деле — могут
Если бы все было так просто. За каждый городок, прежде чем там развернуть сеть, надо заплатить 100500 откатов местным чиновникам. Таким образом в Никарагуа развернуть сеть куда дешевле…
В посте по ссылке какой-то очень сложный алгоритм потока представлен. На олимпиадах обычно используется алгоритм попроще, который работает за O(E * F), где F — число раз, которые мы находим новый путь из истока в сток (в случае, если все ребра имеют пропускную способность 0 или 1 — это просто максимальный поток). В большинстве случаев он опережает остальные алгоритмы по скорости
Это шутка такая? Вы знаете, с какими костылями проходят те турниры? Вы видели список правил, скажем, Chaos-турниров? Простыня текста на несколько мониторов с тем, какие ограничения
К сожалению, такую прорву игровых фракций практически невозможно сбалансировать…
При описании алгоритмов было бы хорошо писать их асимптотическую сложность
ИМХО, самый простой для написания метод топологической сортировки — поддерживаем для каждой вершины число входящих ребер (deg). На каждом шаге берем ту вершину, у которой число входящих ребер равно 0 (любую из них), присваиваем ей следующий незанятый номер и вычитаем 1 их всех элементов массива deg, куда входит ребро из данной вершины. Наивная имплементация дает O(v^2), если вершины хранить в хипе, отсортированные по deg — O(e)
for (long i = 0; 2 * i * i <= x; i++) for (long j = i; i * i + j * j <= x; j++) if (i * i + j * j == x) ans++;
По крайней мере на Java, на Python может и не проходило
Добавим к p для каждого ящика его w. Теперь несложно доказать (но мне влом писать), что существует оптимальная башня в которой ящики идут сверху вниз в порядке возрастания p. Теперь посчитаем следующую динамику — какой наименьший вес имеет башенка из i ящиков если ящики можно выбирать из j первых. Пересчет очевиден.
К сожалению, такую прорву игровых фракций практически невозможно сбалансировать…
ИМХО, самый простой для написания метод топологической сортировки — поддерживаем для каждой вершины число входящих ребер (deg). На каждом шаге берем ту вершину, у которой число входящих ребер равно 0 (любую из них), присваиваем ей следующий незанятый номер и вычитаем 1 их всех элементов массива deg, куда входит ребро из данной вершины. Наивная имплементация дает O(v^2), если вершины хранить в хипе, отсортированные по deg — O(e)
Насчет Сергея — не знаю
Burunduk1 — студент СПбГУ
pashka — выпускник СПбИТМО
halyavin — выпускник МГУ, сейчас аспирант там же
mystic — выпускник БГУ
SergeiRogulenko — студент МГУ
Всем спасибо за поздравления и кому-то — за инвайт