Всем привет!
ВКОШП уже не за горами, надо начинать тренироваться! В качестве тренировки на сайте интернет-олимпиад будет проведено две командных олимпиады. Первая из них состоится уже в эту субботу (5 ноября) в 16:00.
Множество проблем возникло у величайшего мага Доктора Стрэнджа, и вам предстоит помочь ему разобраться с ними, пока он спасает мир.
Продолжительность этой олимпиады будет составлять 5 часов в усложненной номинации и 3 часа в базовой. Подробнее о номинациях и правилах можно прочитать здесь. По возникшим вопросам во время олимпиады просьба писать на почту жюри.
Если вы еще не регистрировали команду на интернет-олимпиады в этом сезоне, то сделать это можно тут. Все команды будут подтверждены перед началом олимпиады.
Условия появятся на сайте в момент начала олимпиады. Сдавать задачи можно в PCMS2 Web Client.
Олимпиаду для вас подготовили Михаил Путилин (SpyCheese), Илья Збань (izban), Николай Будин (budalnik), Станислав Наумов (josdas), Дмитрий Филиппов (DimaPhil), Илья brb Пересадин, (pva701), Григорий Шовкопляс (GShark), Виктория Ерохина (viktoria) и Наталья Слепкова (filyera).
Удачи!
У кого-то есть адекватные решения на F?
Жадина. Давай покрасим сначала все вершины в белый цвет. Будем перебирать вершины 1..n и смотреть не выгодно ли нам поменять цвет. Просто проходимся по всем ребрам данной вершины и считаем сумму среди ребер с одинаковыми цветами концов и сумму с разными цветами. В нашу глобальную сумму входят все ребра с одинаковыми концами, тогда если мы поменяем цвет данной вершины то из глобальной суммы отнимется сумма ребер которые с одинаковыми концами, а прибавится сумма других ребер. Так мы всегда можем выбрать цвет данной вершины, чтобы в глобальную сумму прибавить не больше половины от суммы всех инцидентных ей ребер.
Code
Кто нибудь может рассказать, как решается E в усложненной номинации? P.S Пожалуйста.
Сортируешь по правому концу а если равны по левому. Сдаешь книгу как можно позже, для этого можно использовать дерево отрезков + бинпоиск.
Достаточно обычной кучи
Моделирование процесса + жадина. Будем перебирать в порядке возрастания моменты времени. Если в данный момент мы берем книгу, то давай кинем в сет1 момент времени когда мы закончим читать эту книгу и ее номер (pair < int, int >). Теперь давай посмотрим какие книги мы закончили читать в этот момент времени (они лежат в сет1) и удалим их из сет1 и кинем дедлайн этой книги в сет2. Теперь давай посмотрим какую книгу выгодно сдать в данный момент времени. Это книга которую мы уже прочитали и ее дедлайн ближе всего. Просто достаем из сет2, если он не пустой, минимальный дедлайн. Ответ -1 будет тогда когда дедлайн книги из сет2 меньше чем момент времени в котором мы сейчас находимся. Чтобы быстро перебирать моменты времени можно проходиться только по временам начала, конца и начало+время чтения наших книг, а от них продвигаться до ближайшего пока сет2 не пуст.
Code
Когда там архив уже выложат? :)
Спасибо что залил в тренировки, чувак! 2016-2017 Цикл интернет-олимпиад. Третья командная олимпиада, усложненный уровень, «Доктор Стрендж» (5 ноября 2016 года)
Хм, спасибо. А то я не заметил, как сам внезапно залил этот контест в тренировки)