← All solutions

Problem authors:
Martin Kacer and Yujie An
Solved by 8 teams.
First solved after 179 minutes.
Shortest team solution: 3096 bytes.
Shortest judge solution: 2894 bytes.

To solve this problem, we need to understand what data a single move provides us about the state of the world and determine whether the information we have is compatible with some starting positions of the cards. Given that we have to check consistency of our knowledge with possible starting hands, we will represent our knowledge in terms of what it implies about the starting hands (and separately keep how that state changed from the time we started).

There are three types of events listed in the input, we need to understand how they affect the state of the world. We will store the following types of information:

• A specific card started in the hand of player P
• A specific card did not start in the hand of player P
• A specific player started with some card in set S, which has not moved yet

Additionally, for each card, we store its current position, if it has moved.

If a player x asks y for a card C, and gets it, then:

• If we don’t know for sure that x has a card in the suit (we could know that because x is known to have a card in that suit now, or they’re known to have an unknown card in that suit), we now mark x as having started with a card in the suit that we don’t know yet.
• If we knew the current position of C, it was either in y’s hand, in which case we learn nothing, or it was in someone else’s hand, which means someone cheated.
• If we didn’t know the current position of C, then we learn that it started in y’s hand, and is currently in x’s hand. Also, if we knew that y started with some unknown card of the suit, we now clear this information.

If a player x asks a player y for C and doesn’t get it, then:

• We learn the same thing as above about x having a card in the suit,
• If we don’t know the current position of C (which means it didn’t move from the beginning), we know y didn’t start with C.

Finally, if a player declares a quartet, we need to know that for all the cards in the set, either it has moved and they already have it (in which case we know nothing), or it hasn’t moved, and then we learn they started with it. And we mark all the cards to have a known position of “gone”.

Given this knowledge, how do we check if the information we have is consistent with some starting hand? The constraints are small enough that a somewhat pruned brute force search can work. However, the problem can also be represented as a matching problem, where we are matching the 32 cards in the players’ hands to the 32 cards values.

• If we know a specific card started in a player’s hand, we just pick one of the eight cards in that player’s hand, and hard-match it to the card values.
• If we know a specific card has not started in a player’s hand, we remove the edges connecting every card in the player’s hand to that card value.
• If we know a player has to start with a card from a set that hasn’t moved, we pick one card in that player’s hand, and remove all the edges connecting it to any other sets.

If there exists a perfect matching in this graph, it’s possible no-one has cheated yet.