Есть N человек и столько же карточек, пронумерованных от 1 до N. (N < 1000) Каждому человеку вручается карточка. Каждый человек делает два высказывания: у меня карточка a_i и у человека b_i карточка c_i. Одно из высказываний верно, другое — нет. Двух одинаковых высказываний среди всех людей нет. Найти какое высказывание каждого человека было верным.
Идей несколько:
i) Построим двудольный граф с 2*N ребрами. Нужно построить паросочетания с дополнительными запретами на некоторые пары ребер. Можно перейти к вершинному графу, где вершины смежны, если они не могут быть в одном паросочетании и попытаться найти наибольшее вершинное покрытие.
ii) Попробуем свести к 2-SAT. Рассмотрим 2*N переменных вида: у человека i карточка j. Тогда условие на выполнение ровно одного высказывания будет эквивалентно выполнению формулы: (x || y) && (not x || not y). Как учесть, что будет выбрана только одна карточка? Допустим, относительно этой карточки сделано несколько предположений: x, y, u, z. Тогда условие станет таким: (x && not y && not u && not z) || (not x && y && not u && not z) || (not x && not y && u && not z) || (not x && not y && not u && z).
Есть ли еще какие-нибудь идеи?
Условие про уникальность в 2SAT можно закодировать с помощью условий (a_ij => !a_ik)