Truth-Tellers and Liars
Time limit1sMemory limit128 MB
Count all ways to label N people as truth-tellers or liars so that every statement matches the truth-and-lies rule.
- Level
Medium5 of 10
- Topics
- Brute force, Bit manipulation, Simulation
- Solved
- No attempts yet
Problem
A group of N people is given. Each person is either someone who always tells the truth or someone who always lies.
Every person is interviewed. Each of them names several other members of the group and states, for each named member, whether that member tells the truth or lies.
The rules are: every statement made by a truth-teller must be true, and a liar must have at least one false statement.
Count the number of distinct assignments of the labels truth-teller / liar to the N people that are consistent with all of the statements under these rules.
Input
The first line contains the number of people N in the group. (2 ≤ N ≤ 20)
The next 2N lines contain the statements of each person. The statement of person j consists of two lines in the following form:
K A1 A2 ... AK
L B1 B2 ... BL
The first line lists the people whom person j claims tell the truth: K is how many people are named, and A1, A2, …, AK are their numbers. The second line lists the people whom person j claims lie: L is how many, and B1, B2, …, BL are their numbers. If no one is named, the line contains only 0.
People are numbered from 1 to N. No one makes a statement about herself, and no one names the same person as both a truth-teller and a liar.
It is guaranteed that at least one valid assignment exists.
Output
Print a single integer: the number of truth-teller / liar assignments to the N people that are consistent with all the statements under the rules above.
The original task asked to print one valid assignment as
true/falseper person, but such an assignment need not be unique, which makes exact-match judging impossible. It has therefore been reformulated to output the total count of valid assignments, a value that is uniquely defined.