2014 Canadian Computing Competition, Stage 2

Day 1, Problem 3: Werewolf

As they usually do, N robots are playing the game of Werewolf, and the robots are numbered with integers from 1 to N. Exactly W of these robots are werewolves, and the remainder are civilians. Though the game of Werewolf involves various aspects, we will focus on a single discussion phase of the game.

Robots accuse other robots of being werewolves and defend other robots by vouching for their innocence.

The werewolves know each other's identities and:

• a werewolf never accuses another werewolf;
• any robot that a werewolf defends is another werewolf.

Civilians may accuse or defend either type of robot.

Additional constraints make our task a bit easier:

• No robot is both accused and defended.
• No robot is accused or defended more than once.
• For a robot A to accuse or defend robot B, then A < B.

You will be given all the accusations and defenses between N robots where there are exactly W werewolves. A role assignment identifies each of the robots as either werewolf or civilian. Your goal is to figure out how many role assignments satisfy all the above constraints.

Input

The first line contains three numbers (each separated by one space):

• N (1 ≤ N ≤ 200), the number of robots, followed by
• W (0 ≤ W ≤ N), the number of werewolves, followed by
• M (0 ≤ M < N), the number of accusations/defenses.

The next M lines give the accusations and defenses. Each of these lines will be one of the following two forms:

• A a b indicates robot a accused robot b of being a werewolf;
• D a b indicates robot a defended robot b.

You may assume that for 20% of the marks for this problem, N ≤ 20.

Output

The number of role assignments that are consistent with the given information. Since this number may be very large, you must output this answer modulo 10⁹ + 7.

Sample Input 1

2 1 1
D 1 2

Sample Output 1

1

Explanation for Sample 1

If robot 1 is a werewolf, then robot 2 must also be, which is too many werewolves! The only possibility is that robot 2 is the sole werewolf.

Sample Input 2

2 1 0

Sample Output 2

2

Explanation for Sample 2

With no information, either robot 1 or robot 2 could be a werewolf.

Sample Input 3

3 2 2
A 1 2
D 1 3

Sample Output 3

2

Explanation for Sample 3

Either robot 1 is a werewolf, which implies robot 2 is a civilian and robot 3 is a werewolf as well, or robot 1 is a civilian (which allows robot 2 and 3 to both be werewolves).

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: May 17, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

My solution works on official test data on my computer so I'm not exactly sure why its getting RE on the judge.

Check your memory usage