Сегодня писали муниципальный тур Всероссийской олимпиады школьников по информатике. Здесь 3 подгруппы тестов. Первая подгруппа — (N <= 10). Я не знал, как решается эта задача и написал перебор всех перестановок(N!) + разумеется, проверка. Если находил подходящую перестановку, удовлетворяющую входным данным, то ответ — Yes, иначе No. Можете объяснить мне, пожалуйста, решение этой задачи на полный балл? Буду очень благодарен!
UPD: Результаты пришли. Первая подгруппа тестов прошла(20 баллов).
UPD1: Господа минусующие, если вы минусуете, значит, для вас эта задача — пустяк. Так почему бы не написать правильное решение, вместо того, чтобы минусовать?
Сначала допустим, что первый человек в хороводе — лжец. Из этого мы можем восстановить по цепочке всех остальных людей. Если мы не встретили противоречия — ответ найден. Иначе проделаем то же самое, допустив, что первый человек — рыцарь. Если и здесь мы встретили противоречие, то ответа не существует.
Я точно такое же решение писал с помощью dfs, но оно некорректно работало. Задумка была такая: первый человек — лжец. Пускаю из него dfs. Если он лжец, то на следующем шаге запускаю dfs из всех остальных людей(т. к. у нас могут быть и рыцари, и лжецы, то мы можем запустится на втором шаге от каждого, зная — лжец он или нет), а когда ставим последнего — проверяем, можем ли мы круг замкнуть или нет. Если не получилось, то делаю все тоже самое, зная, что первый человек — рыцарь.
Пусть v — это предпоследний человек в уже построенной последовательности, тогда, если текущий персонаж не использован и его левый сосед равен v(то есть v — рыцарь/лжец и левый сосед рыцарь/лжец), то пускаем из него dfs, говоря, что он рыцарь. А если левый сосед не равен v, то наш текущий персонаж — лжец. Пускаем из него dfs.
Вот такая задумка "спотыкалась" на первом сэмпле в самом конце. Генерировала верно последовательность, длины (n — 2), только последние два элемента не в том порядке. Возможно, это просто совпадение, а возможно, что я где-то что-то недопроверял. Вот сам сэмпл:
На самом деле, для любого решения есть два симметричных случая, переходящих друг в друга по принципу рыцарь->лжец и лжец->рыцарь. Просто нужно заметить, что единичка имеет смысл "такой же", а нолик — "другой".
Собственно, сформулируем необходимое условие: количество левых единичек должно быть равно количеству правых единичек, аналогично для ноликов.
Заметим, что для некоторых групп людей существуют эквивалентные преобразования:
Если у нас сходится необходимое условие, то выполним все возможные преобразования, начиная с первого типа и переходя к следующему типу только тогда, когда не осталось возможных преобразований предыдущего типа. В конце, если мы получим (1-1) или (0-0) + (0-0), то ответ существует, во всех остальных случаях, а это (0-0), (0-0) + (1-1) и (0-0) + (0-0) + (1-1), ответа нет.
Там ограничения — (N <= 10^5). Это в ТЛ уложится?
Кстати, MrDindows предлагал точно такое же решение. Спасибо!
Это можно вообще за O(1) сделать, если нам известно количество людей каждого типа :).
Спасибо большое, я понял идею! Жаль, что я не додумался до этого :(
Не стоит ни о чем жалеть, у тебя все еще впереди :).
Я всегда жалею о том, что не додумываюсь до довольно простых вещей. Ну, на регион я прошел, по идее. Так что, возможно, действительно не стоит жалеть.
Но ведь порядок показаний жителей не обязательно соответствует порядку в хороводе, а значит однозначно восстанавливать таким образом нельзя.
Понятно, что соседи друг про друга говорят одно и то же (можно разобрать случаи). Значит, пары можно "склеивать", если у одного справа то же, что у другого слева. В результате склеивания получится какая-то цепочка из 0 и 1, причем 1 означает, что соседи одинаковые, а 0 — что разные. То есть нулей в цепочке должно быть четное количество.
Этого хватает для критерия: количество нулей слева должно равняться количеству нулей справа, то же для единиц, и, кроме того, количество нулей слева должно быть четным. Вроде, всё.
(UPD: ниже написано, почему не всё.)
Свойства контрпримера к Вашему решению описаны выше.
UPD. Исправил ссылку.
А можно сам контрпример, а не свойства? А то приведенный сэмпл вполне решается (количество единиц и нулей слева и справа совпадает, количество нулей слева четно, ответ YES, последовательность, например, РРЛРР).
Могу еще пару тестов дать из проверяющей системы, если нужно.
Там он уже есть:
Очевидно, первые два человека склеиваются в один хоровод, а третьему придется танцевать самому по себе.
P.S. Да, я дал ссылку не на свой комментарий. Прошу прощения.
А, это вы не туда ссылку дали. Да, с этим согласна.
Придется еще проверять, что нет двух отдельных хороводов из 0 и из 1 — ну тоже несложно, и вполне можно обойтись без симуляции. Достаточно проверить, что если есть и 0, и 1, то есть и переход (хотя бы один "1 0").
We can take any person and first time consider him a liar and second time consider him a knight. Then by their data we could build all the chain. We should consider the arrangement that will is not contrary, if there is such an arrangement we should print "Yes". If there is no such build then we should print "No".
Нужно начать с пербого человека в хороводе. По условию етот человек обязательно окажется либо рыцарем либо лжецом. Нужно проверить два случая. 1) Первый житель в хороводе рыцарь 2) Первый житель не рыцарь т.е. лжец и построит остальную последовательность опираясь на данные первого жителя. Если есть сценарий где нет противоречий вывести "Yes", иначе "No".
Прошу прощения за мой русский. Надеюсь обяснил доходчиво.
UPD: т.к. интерфейс был на английском не увидел все ети комментарии под постом. Сори.
Я вот тут описывал свою стратегию решения. Как раз решал так, как Вы говорите. http://codeforces.com/blog/entry/9874#comment-153450