X. Quartets
46th Annual hosted by ICPC World Championship AASTMT Problem X Q...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
46th Annual hosted by ICPC World Championship AASTMT
Problem X Quartets Time limit: 2 seconds You are watching a group of kids playing a friendly game of Quartets and having fun. At one moment, you started being sus- picious that some of the kids may be cheating. It seems the kids themselves are not bothered by that at all. Quite the contrary, this brings them even more fun, especially when someone gets caught cheating. As a programmer, you immediately started to think about ways to detect cheating by just observing their game. Quartets is a 4-player card game that uses a deck of 32 cards divided into 8 sets of 4 cards each. Actual cards often contain educational images, which helps players to learn not only in- dividual objects but also their classification. For example, the cards may display animals while the sets correspond to various groups of animals (mammals, reptiles, etc.). At the beginning of a Quartets game, every player is dealt 8 cards and player 1 starts their turn. In each turn, a player asks another player whether they have one particular card. If the asked player has that card, they must give it to the requester, and the requester continues their turn by asking any of the players for another card. Four cards of a set, from a German Quartets deck by If the asked player does not possess the requested card, the re- Wilhelm Busch via Wikimedia Commons, public domain
questing player loses the turn and the asked player starts their turn. An important rule states that the requesting player must already have at least one card from the same set as the card they ask for. If, during their turn, a player holds a full set (“quartet”) in their hand, the player may show the quartet to the other players, put it aside and gain one point. The four cards of the quartet are permanently removed from the current game. If at any point a player has no cards left, that player leaves the game. If it was that player’s turn, the turn passes to the next player in sequence (player 1-2-3-4-1-. . .) who still has any cards. If no players have any cards, the game ends and the player with the most points is declared the winner. Players are not allowed to ask for cards that have been removed from the game, and they cannot ask for a card from a player who has left the game. Cheating in the game of Quartets is conceivable in two situations where a player falsely claims to have (or not have) some card. Specifically, the cheating occurs if
- a player asks for a card although they have no card of the corresponding set, or
- a player being asked claims not to have the requested card although they have it.
Needless to say, cheating is often discovered later. Theoretically, a watchful opponent can eventually find out about any cheating, as all cards are finally revealed at some point before the game ends. Note that asking for a card that the asked player cannot possibly have (for example, because the requester has it in their own hand) is not exactly a smart move but is not considered cheating by itself.
World Finals | ICPC 2023 Luxor
46th Annual hosted by
ICPC World
Championship AASTMTInput
The first line of input contains an integer n (1 ≤ n ≤ 1000), the number of consecutive actions in one game of Quartets, starting from the beginning of a game. The next n lines each contain a description of an action. Each action is described by one line and may be one of the following:
- x A y sk yes — player x asks player y for the card sk, and player y hands that card to player x;
- x A y sk no — player x asks player y for the card sk, player y claims not to have it, and starts their turn;
- x Q s — player x puts aside a quartet s.
In all actions, x and y (1 ≤ x, y ≤ 4, x 6= y) are integers denoting the players, s (1 ≤ s ≤ 8) is a one- digit integer corresponding to one of the sets/quartets, and k ∈ {A, B, C, D} is a character identifying the four cards within a set. Thus the cards sk are labeled 1A, 1B, 1C, 1D, 2A, 2B, . . ., 8C, 8D. The four cards that share the same first digit form a single set. The given sequence describes a valid game being played among 4 players. That is, except for the two possible ways of cheating mentioned above, all actions satisfy all the rules.
Output
If there is a possible initial distribution of the cards such that the sequence of actions corresponds to a (possibly partial) game with all players following the rules, output yes. Otherwise, output no, followed by a line giving the number of the first action after which it is certain that some player must have cheated. Actions are numbered sequentially starting with 1, the actions of putting quartets aside are also counted.
Notes
Explanation of Sample Input 1
Players 1 and 2 both claim not having 3C, and neither of them had 3A or 3D. So one of them either lied about not having 3C, or asked for 3C without having 3B (the only remaining card from set 3).
Sample Tests
4
1 A 2 3C no
2 A 3 3A yes
2 A 4 3D yes
2 A 1 3C nono
4 6
1 A 2 3C no
2 A 3 3A yes
2 A 4 3D yes
2 A 1 3B no
1 A 4 5B yes
1 Q 5yesEditorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Key Observations
It is enough to understand what each observed action implies about the initial deal. The later movement of cards only matters because it changes what we already know.
For each card we can maintain:
a forced starting owner, if known;
a set of forbidden starting owners;
its current known position: unknown, held by one player, or already gone in a declared quartet.
We also need one more kind of information: a player may be known to have started with some card from a given set, even if we do not yet know which card it was.
After replaying a prefix of the log, deciding consistency is a pure feasibility problem on the initial deal. The $8$ sets are almost independent: they interact only through the condition that each player must start with exactly $8$ cards.
Prefix consistency is monotone: once a prefix is impossible, every longer prefix is also impossible. Therefore we can binary-search the first bad action.
Algorithm
Define a procedure
prefix_consistent(k)that replays the first $k$ actions.While replaying, maintain:
start_owner[card]: forced initial owner, if known;forbidden[card][player]: this player cannot have started with this card;cur_owner[card]: current known holder, orGONE;need[player][set]: this player must have started with some still-unidentified card from this set.For an ask ``player $x$ asks player $y$ for card $c$'':
first ensure that $x$ is known to have some card in that set, adding a
need[x][set]constraint if necessary;if the answer is yes, then $c$ must currently belong to $y$ unless it was previously unknown, in which case we learn that $y$ started with $c$;
if the answer is no and $c$ has not moved yet, then $y$ cannot have started with $c$.
For a quartet declaration by player $x$, every still-unmoved card in that set must have started with $x$, and afterwards all four cards become
GONE.If the replay creates a direct contradiction, this prefix is impossible.
Otherwise, test whether some initial deal satisfies all accumulated constraints:
for one set, enumerate all $4^4 = 256$ assignments of its four cards to starting players;
keep only assignments satisfying the forced/forbidden information for those cards and the
needconditions for that set;run a dynamic program over the $8$ sets and the numbers of cards already given to players $0,1,2$; player $3$ is implicit.
If the whole log is consistent, output
yes. Otherwise binary-search the smallest prefix length that is inconsistent and outputnowith that index. enumerateCorrectness Proof
We prove that the algorithm returns the correct answer.
Lemma 1.
After replaying any prefix, the maintained constraints describe exactly the set of initial deals compatible with all observed actions in that prefix.
Proof.
We argue by induction over the replayed actions.
Initially there are no constraints, so every initial deal is allowed. Consider one more action. For a successful ask, either the asked-for card already has a known current owner, in which case that owner must be the asked player, or the card has never been seen before, in which case it must have started with the asked player. For an unsuccessful ask, if the card has never moved then the asked player cannot have started with it. In both cases, the asking player must be known to hold some card from that set, either because we already knew it or because this action forces that fact.
For a quartet declaration, every card of that set that has not moved before must have started with the declaring player; afterwards those cards are removed from play. Every contradiction detected by the replay makes the prefix impossible, and every surviving initial deal remains compatible with the updated constraints. Thus the maintained data is exact after every prefix. □
Lemma 2.
For a fixed replayed prefix, the set-by-set dynamic program returns true exactly when some initial deal satisfies all accumulated constraints.
Proof.
Within one set there are only four cards, so every possible local assignment of those four starting cards to players appears among the $256$ enumerated assignments. Filtering removes exactly the assignments that violate forced owners, forbidden owners, or the requirement that a player must have started with at least one card from that set.
Different sets interact only through the total number of cards each player must receive overall. Therefore a DP state storing how many cards players $0,1,2$ have received after processing some sets is sufficient; player $3$ is determined by the total processed cards. A transition corresponds exactly to choosing one feasible local assignment for the next set. Hence the DP reaches the final state $(8,8,8)$ if and only if there exists a globally valid initial deal. □
Lemma 3.
If a prefix is inconsistent, then every longer prefix is also inconsistent.
Proof.
By Lemma 1, inconsistency means that no initial deal can realize all actions in that prefix. Adding more observed actions can only impose additional constraints on the same initial deal; it cannot create a new initial deal that already satisfied the shorter prefix. Therefore inconsistency is monotone. □
Theorem.
The algorithm outputs the correct answer for every valid input.
Proof.
By Lemma 1 and Lemma 2,
prefix_consistent(k)is true exactly for those prefixes that can occur without cheating. If the full log is consistent, outputtingyesis correct. Otherwise, Lemma 3 shows that the inconsistent prefixes form a suffix, so binary search finds the smallest bad prefix length exactly. Thus the reported answer is correct. □Complexity Analysis
Checking one prefix of length $k$ takes $O(k)$ time for the replay plus $O(8 \cdot 256 \cdot 9^3)$ time for the DP, which is a fixed constant for this game size. The memory usage is $O(9^3)$.
The full algorithm does one full-prefix check and then $O(\log n)$ more checks during binary search, so the overall running time is $O(n \log n)$ and the memory usage remains $O(9^3)$.
Implementation Notes
The DP is done by sets, not by individual cards, because each set has only four cards and the cross-set coupling is only through the final hand sizes.
The code stores the fourth player's card count implicitly, which keeps the DP array small and simple.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
namespace {
constexpr int PLAYERS = 4;
constexpr int SETS = 8;
constexpr int CARDS_PER_SET = 4;
constexpr int TOTAL_CARDS = 32;
constexpr int UNKNOWN = -1;
constexpr int GONE = 4;
struct Action {
char type = '?'; // 'A' or 'Q'
int x = -1;
int y = -1;
int set_id = -1;
int card = -1;
bool yes = false;
};
int card_id(int set_id, char rank) {
return set_id * CARDS_PER_SET + (rank - 'A');
}
bool player_known_to_have_set(int player, int set_id,
const array<array<char, SETS>, PLAYERS>& need,
const array<int, TOTAL_CARDS>& cur_owner) {
if (need[player][set_id]) {
return true;
}
int first = set_id * CARDS_PER_SET;
for (int card = first; card < first + CARDS_PER_SET; ++card) {
if (cur_owner[card] == player) {
return true;
}
}
return false;
}
bool assign_start_owner(int card, int player, array<int, TOTAL_CARDS>& start_owner,
array<array<char, PLAYERS>, TOTAL_CARDS>& forbidden) {
if (forbidden[card][player]) {
return false;
}
if (start_owner[card] != UNKNOWN && start_owner[card] != player) {
return false;
}
start_owner[card] = player;
return true;
}
bool prefix_consistent(const vector<Action>& actions, int prefix_len) {
array<int, TOTAL_CARDS> start_owner;
start_owner.fill(UNKNOWN);
array<int, TOTAL_CARDS> cur_owner;
cur_owner.fill(UNKNOWN);
array<array<char, PLAYERS>, TOTAL_CARDS> forbidden{};
array<array<char, SETS>, PLAYERS> need{};
for (int i = 0; i < prefix_len; ++i) {
const Action& action = actions[i];
if (action.type == 'A') {
int x = action.x;
int y = action.y;
int set_id = action.set_id;
int card = action.card;
if (!player_known_to_have_set(x, set_id, need, cur_owner)) {
need[x][set_id] = true;
}
if (action.yes) {
if (cur_owner[card] == GONE) {
return false;
}
if (cur_owner[card] != UNKNOWN && cur_owner[card] != y) {
return false;
}
bool resolved_start = false;
if (cur_owner[card] == UNKNOWN) {
if (!assign_start_owner(card, y, start_owner, forbidden)) {
return false;
}
resolved_start = true;
}
cur_owner[card] = x;
if (resolved_start) {
need[y][set_id] = false;
}
} else {
if (cur_owner[card] == y || cur_owner[card] == GONE) {
return false;
}
if (cur_owner[card] == UNKNOWN) {
if (start_owner[card] == y) {
return false;
}
forbidden[card][y] = true;
}
}
} else {
int x = action.x;
int set_id = action.set_id;
for (int offset = 0; offset < CARDS_PER_SET; ++offset) {
int card = set_id * CARDS_PER_SET + offset;
if (cur_owner[card] == GONE) {
return false;
}
if (cur_owner[card] != UNKNOWN && cur_owner[card] != x) {
return false;
}
if (cur_owner[card] == UNKNOWN) {
if (!assign_start_owner(card, x, start_owner, forbidden)) {
return false;
}
}
cur_owner[card] = GONE;
}
need[x][set_id] = false;
}
}
static bool dp[9][9][9];
static bool next_dp[9][9][9];
memset(dp, 0, sizeof(dp));
dp[0][0][0] = true;
for (int set_id = 0; set_id < SETS; ++set_id) {
vector<array<int, PLAYERS>> options;
options.reserve(256);
for (int mask = 0; mask < (1 << (2 * CARDS_PER_SET)); ++mask) {
array<int, PLAYERS> cnt{};
bool ok = true;
for (int i = 0; i < CARDS_PER_SET; ++i) {
int player = (mask >> (2 * i)) & 3;
int card = set_id * CARDS_PER_SET + i;
if (start_owner[card] != UNKNOWN && start_owner[card] != player) {
ok = false;
break;
}
if (forbidden[card][player]) {
ok = false;
break;
}
++cnt[player];
}
if (!ok) {
continue;
}
for (int player = 0; player < PLAYERS; ++player) {
if (need[player][set_id] && cnt[player] == 0) {
ok = false;
break;
}
}
if (ok) {
options.push_back(cnt);
}
}
if (options.empty()) {
return false;
}
memset(next_dp, 0, sizeof(next_dp));
int processed_cards = set_id * CARDS_PER_SET;
for (int c0 = 0; c0 <= 8; ++c0) {
for (int c1 = 0; c1 <= 8; ++c1) {
for (int c2 = 0; c2 <= 8; ++c2) {
if (!dp[c0][c1][c2]) {
continue;
}
int c3 = processed_cards - c0 - c1 - c2;
if (c3 < 0 || c3 > 8) {
continue;
}
for (const auto& cnt : options) {
int n0 = c0 + cnt[0];
int n1 = c1 + cnt[1];
int n2 = c2 + cnt[2];
int n3 = c3 + cnt[3];
if (n0 > 8 || n1 > 8 || n2 > 8 || n3 > 8) {
continue;
}
next_dp[n0][n1][n2] = true;
}
}
}
}
memcpy(dp, next_dp, sizeof(dp));
}
return dp[8][8][8];
}
void solve() {
int n;
cin >> n;
vector<Action> actions;
actions.reserve(n);
for (int i = 0; i < n; ++i) {
Action action;
cin >> action.x;
--action.x;
char kind;
cin >> kind;
if (kind == 'A') {
action.type = 'A';
cin >> action.y;
--action.y;
string card;
string result;
cin >> card >> result;
action.set_id = card[0] - '1';
action.card = card_id(action.set_id, card[1]);
action.yes = (result == "yes");
} else {
action.type = 'Q';
string set_str;
cin >> set_str;
action.set_id = set_str[0] - '1';
}
actions.push_back(action);
}
if (prefix_consistent(actions, n)) {
cout << "yes\n";
return;
}
int low = 1;
int high = n;
while (low < high) {
int mid = (low + high) / 2;
if (prefix_consistent(actions, mid)) {
low = mid + 1;
} else {
high = mid;
}
}
cout << "no\n" << low << '\n';
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/icpc/2022/X-quartets/solution.texC++ implementationcompetitive_programming/icpc/2022/X-quartets/solution.cppStatement textcompetitive_programming/icpc/2022/X-quartets/statement.txtStatement PDFcompetitive_programming/icpc/2022/X-quartets/statement.pdfMetadatacompetitive_programming/icpc/2022/X-quartets/meta.jsonYear packetcompetitive_programming/icpc/2022/contest_problems.pdf