Приглашаем всех желающих принять участие в чемпионате по алгоритмическому программированию, приуроченном к 10-летию Центра развития ИТ-образования МФТИ.
Чемпионат пройдет в двух дивизионах: A/B и C/D. Задачи контеста подготовили преподаватели МФТИ и СПбГУ.
Участвовать в чемпионате можно как в команде до 3-х человек, так и в одиночку.
Зарегистрироваться на чемпионат можно по ссылке: https://clck.ru/SHb6p
16 декабря Центр развития ИТ-образования МФТИ (ЦРИТО) отмечает 10-летний юбилей. Открытый чемпионат 6 декабря — одна из образовательных инициатив ЦРИТО, которая наряду с другими текущими проектами в области ИТ помогает десяткам тысяч молодых и опытных специалистов из России и зарубежных стран в профессиональном и карьерном росте.
А вы можете опубликовать расписание, ссылку на вход в тестирующую систему?
Ссылки на пробный тур и тестирующую систему обоих дивизионов (как и логины и пароли) появятся в личном кабинете в субботу.
Будет ли открыто дорешивание? Спасибо!
А есть где-нибудь обсуждение задач?
Например, как решать задачу F? Верно ли, что можно k раз запускать Дейкстру, после каждого прохода обновляя веса ребер? Это получило WA5 — то ли из-за плохой реализации, то ли из-за неправильной идеи (в таком случае хотелось бы увидеть контрпример).
И дайте ссылку на дорешивание, пожалуйста,
В том же контесте. В обоих дивизионах.
По F запускали min-cost-max-flow по следующему графу: Каждое ребро дублируем k раз (каждое пропускной способностью 1, а цена каждого следуюущего увеличивается на 1). Восстанавливаем ответом k раз запускаем dfs по ребрам с потоком. Ну и аккуратно обработать самый первый поток, ибо цена 0 (мы еще в цену добавили количество ребер по которым прошли)
Тест 5:
Ответ — 51: сходить по три раза по каждому из трёх понятных маршрутов. Видимо, Дейкстра оступается, а потом, в отличие от потока, не может отменить свою ошибку.
Решение жюри — min-cost max-flow с сетью из $$$n \cdot n \cdot k$$$ рёбер — то же, что в комментарии Zool. С Фордом-Беллманом $$$50^5$$$, если вдруг не успевает — есть много возможных оптимизаций: например,
breakв Форде-Беллмане, или учесть, что для каждого дополняющего пути у каждого мультиребра интересны не все $$$k$$$ стоимостей, а только парочка. И действительно есть проблема с нулевыми рёбрами при восстановлении пути. У нас она решается отменой не одного, а двух парных рёбер при проходе по ребру в любую сторону.Можно поподробнее про проблему? У меня никаких костылей в коде нет (у меня правда и граф другой — рёбра можно не раскопировать, а просто стоимость считать в зависимости от текущего потока).
Если ребро стоит честный 0, и мы ищем кратчайшие пути, мы можем сходить по одному ребру за 0 туда (в одном пути) и за 0 обратно (в другом).
У меня в реализации каждое ребро $$$(u, v, cost)$$$ расчетверяется:
$$$u \xrightarrow[1]{+cost} v$$$, $$$v \xrightarrow[0]{-cost} u$$$, $$$v \xrightarrow[1]{+cost} u$$$, $$$u \xrightarrow[0]{-cost} v$$$.
Если, например, прошли по первому из этих четырёх рёбер — делаю все пропускные способности нулями, кроме второго ребра — которое отменяет первое. Ну и возвращаю, если прошли обратно.
Никогда не выгодно ходить по одному и тому же ребру в две разные стороны. Более того, если вы разрешаете так делать, то вы формально даже нарушаете модель задачи (допустим вы 5 раз прошли в одну сторону, потом решили пойти в другую: в модели задачи это стоит 5, в вашей сети — 0). Это, конечно, неважно, потому что, опять же, никогда не выгодно ходить по одному ребру в разные стороны.
Поэтому вместо того чтобы делать две копии ребра в разные стороны, а потом для каждого из них делать обратное для остаточной сети, можно просто сделать две копии в разные стороны, которые являются обратными друг к другу в остаточной сети. В такой сети проблемы с нулевыми ребрами просто не существует: никакой валидный поток не может по одному ребру пройти в две стороны.
Согласен с первым абзацем.
А про второй абзац — не понимаю, как сделать два ребра, а не четыре, но чтобы у них были правильные стоимости. Нам же нужно уметь для каждой цены $$$x$$$:
Это четыре ребра, а не два.
Понятно, как делать, если пересчитывать стоимость на лету: на каждом ребре поддерживать поток по нему. Тогда проблемы и нет. Но мы же сейчас про другое решение, которое сначала строит сеть, а потом пускает на ней обычный min-cost max-flow без хаков.
Окей, видимо я неправильно понял о чем речь. Я говорил про решение, которое пересчитывает стоимость в зависимости от потока.