← All solutions

Shortest judge solution: 1871 bytes. Shortest team solution (during contest): 1841 bytes.

Python solutions by the judges: both Pypy and CPython

This is a problem that can be solved by a brute-force search, but the implementation can be a bit messy, and depending on your exact approach, it may be important to have good constant factors.

The very simplest approach is just to generate all disjoint sets of cards for the four hands (well, one hand is already given so there’s only one option for that) and then go through all the played rounds and check that they are consistent with assignment of cards to hands. However, this will probably not run in time unless it is fairly carefully implemented, so something a bit better is needed.

The next approach could be to first guess the murderer, weapon, and room, and then do the above-mentioned brute-force search for a partition of cards into hands, and break as soon as a valid solution is found. This turns out to run a bit faster and is definitely possible to make fast enough (because the worst case for the above is when pretty much all partitions of cards into hands yields a valid solution, and many of those partitions into hands will result in the same murderer/weapon/room).

A different algorithmic approach which essentially makes constant factor worries go away is to generate the possible hands separately: for player 2 we compute all possible subsets of 5 cards S₁, S₂, . . . that are compatible with all the played rounds, and similarly for player 3 all sets of 4 cards T₁, T₂, . . . and for player 4 all subsets of 5 cards U₁, U₂, . . .. Now for a given guess of murderer/weapon/room, let X be the set of remaining cards after removing the three answer cards and the hand of player 1. We are then trying to find i, j, k such that S_i ∪ T_j ∪ U_k = X. This can easily be done in time O(#S · #T) – simply try all S_i’s and T_j’s and then check if X∆S_i ∆T_j is one of the U_k’s (by keeping a dictionary of all U_k’s). The subsets are most conveniently represented by integers, which makes lookups quick. This solution is fast enough that it can even be done in CPython.