Четвёртый раунд SnarkNews Winter Series 2016 в связи с плотным расписанием соревнований 29-31 января и по просьбам участников сборов в Петрозаводске продлён до 23:00 31 января.
По просьбам участников серии публикуется ссылка для регистрации и участия в четвёртом раунде.
Также в комментариях к этому посту можно будет по окончании раунда в соответствии с расписанием обсуждать задачи раунда.
Хорошо, что появился пост про продление 4го раунда, а то я забыла, что он начался :) Вроде стандартного поста о начале не было.
Я так понимаю, раунд уже закончился?
Как правильно надо было сдавать E?
(У меня зашло за (MN)^2 с перебором ребер, в котором я уменьшаю поток относительно найденного решения, но только с отсекой по времени, и, видимо, это не то, что предполагалось)
У меня такое: нахожу какой-то ответ используя maxflow. Дальше проверяю, является ли этот ответ единственным. Ответ не является единственным, если в нем можно выбрать прямоугольник, что два противоположных угла можно сделать -1, а другие два +1. #code
Хм, а есть какое-то доказательство корректности? Наличие такого прямоугольника соответствует циклу длины 4 из непустых / неполных ребер в графе дополняющих путей. А наличие не единственного решения эквивалентно наличию любого цикла четной длины. Интересно, почему из второго следует первое (то есть почему не может быть так — цикл длины 6, но при этом не существует цикла длины 4)
+0-
-+0
0-+
Я не умею это доказывать, но похоже что это верно :)
+0-
-+X
0-+
Если X полное (X = MAX), можно там поставить -, иначе можно +.
Ага, подтвердил сгенерив много случайных маленьких тестов. Ну да, и проверку на такой прямоугольник можно сделать за O(NM2), что похоже на необходимую сложность.
По расписанию 5-ый раунд должен был стартовать 31.01.2016, в 14:00. Читаем примечание: "при форс-мажорных обстоятельствах время начала раунда может быть сдвинуто вперёд, но не более, чем на 12 часов." На данный момент, по прошествии более 24 часов от запланированного начала, раунд по ссылке со snarknews все еще недоступен.