CLUE - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

HARD

EXPLANATION

Given the sums of the cards of each logician, we create a list of every possible game configuration with the same sums. Then one turn at a time, we determine if the logician whose turn it is can win, and if not we remove from the list all configurations in which that logician would win on that turn. A configuration is a winning configuration if in every other configuration where the current logician’s cards are the same, the secret cards are also the same. A game will never end if every logician has a turn without the size of the list decreasing. In this case there is no winner. That being said, the following game lasts 49 turns before being won!

9 10 11
6 7 14
1 2 4
3 8 18
13 15 16