У нас есть игра, в которой ничьих не бывает, и для каждой пары игроков мы знаем, кто кого выиграет. Наша задача — для каждого игрока определить, можно ли составить такое расписание турнира, чтобы этот игрок выиграл.
Боян? Добавим в условие дополнительное ограничение: на каждой стадии турнира каждый из игроков обязан сыграть с другим игроком (кроме игрока, для которого пара не нашлась — он автоматически проходит в следующую стадию).
Задачу в таком виде мне подкинул Jokser, вот источник (условия, задача D, тесты). К сожалению, авторское решение задачи соответствует решению оригинальной задачи без введения дополнительного ограничения (я так утверждаю, потому что разобрал тесты).
Задача смахивает на NP-полную, но такое впечатление иногда бывает обманчивым. Так можно ли все-таки решить ее за полиномиальное время? Если да, то как?
UPD. Интуитивные рассуждения приводят к тому, что задача должна быть NP-полной, т.к. сводится к чему-то вроде пересечения трех или более матроидов. Знатоки этой темы, откликнитесь...
1218 — другая задача. Там в каждый момент времени проводится только один поединок. Когда он заканчивается — начинается следующий, и т.д.
1218 — именно та задача, которую я описал в первом абзаце своего поста. Читай внимательнее :).
Ну ты не формализовал понятие "расписание". Там расписание такое, как в моем предыдущем сообщении, а не как в задаче D по ссылке.
А ты формализовал его неправильно. Более правильно: расписание турнира — это двоичное дерево, вершины которого либо являются листьями (соответствуют игрокам), либо имеют ровно двух потомков (соответствуют победителю игры между потомками).
Ну у меня Accepted на тимусе с моим пониманием. А задачи эти, разумеется, разные, например, в джедаях при матрице смежности
могут выиграть все, а в задаче D — только третий и четвертый.
Я уже давно думал над задачей в этой формулировке. Во время летних сборов в Петрозаводске 2012 я обсуждал возможность решить такую задачу с Burunduk1. Мы не пришли к какому-либо полиномиальному решению. Понятно, что все победители будут в одной компоненте сильной связности, но не все члены этой компоненты обязаны быть победителями. Других соображений пока что нет.
Upd. сам понял
Комментарий к UPD. Если задача из класса NP эффективно сводится к NP-трудной задаче, то это ни о чем не говорит. Это же просто определение NP-hard.
Должно бить NP-complete.
Если ничего не путаю, то вот:
http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460
Задача называется «Agenda control for balanced single-elimination tournaments», и ее статус неизвестен.
В статье V. Vassilevska Williams «Fixing a tournament» доказывается NP-полнота для случая, когда некоторым парам запрещено соревноваться друг с другом.
Да, это именно то, что надо. Большое спасибо за прояснение ситуации!