ICPC 2022 - X. Quartets

#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;
}

\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}

\title{ICPC World Finals 2022\\X. Quartets}
\author{}
\date{}

\begin{document}
\maketitle

\section*{Problem Summary}

Four players play with $32$ cards, grouped into $8$ sets of $4$ cards. We are given the observed
sequence of asks and quartet declarations. We must decide whether all actions can be legal for
some initial deal of eight cards to each player. If not, we must output the first action after which
cheating is unavoidable.

\section*{Key Observations}

\begin{itemize}[leftmargin=*]
    \item It is enough to understand what each observed action implies about the \emph{initial}
    deal. The later movement of cards only matters because it changes what we already know.
    \item For each card we can maintain:
    \begin{itemize}[leftmargin=*]
        \item a forced starting owner, if known;
        \item a set of forbidden starting owners;
        \item its current known position: unknown, held by one player, or already gone in a declared
        quartet.
    \end{itemize}
    \item We also need one more kind of information: a player may be known to have started with
    \emph{some} card from a given set, even if we do not yet know which card it was.
    \item 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.
    \item Prefix consistency is monotone: once a prefix is impossible, every longer prefix is also
    impossible. Therefore we can binary-search the first bad action.
\end{itemize}

\section*{Algorithm}

\begin{enumerate}[leftmargin=*]
    \item Define a procedure \texttt{prefix\_consistent(k)} that replays the first $k$ actions.
    \item While replaying, maintain:
    \begin{itemize}[leftmargin=*]
        \item \texttt{start\_owner[card]}: forced initial owner, if known;
        \item \texttt{forbidden[card][player]}: this player cannot have started with this card;
        \item \texttt{cur\_owner[card]}: current known holder, or \texttt{GONE};
        \item \texttt{need[player][set]}: this player must have started with some still-unidentified card
        from this set.
    \end{itemize}
    \item For an ask ``player $x$ asks player $y$ for card $c$'':
    \begin{itemize}[leftmargin=*]
        \item first ensure that $x$ is known to have some card in that set, adding a
        \texttt{need[x][set]} constraint if necessary;
        \item 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$;
        \item if the answer is no and $c$ has not moved yet, then $y$ cannot have started with $c$.
    \end{itemize}
    \item 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 \texttt{GONE}.
    \item If the replay creates a direct contradiction, this prefix is impossible.
    \item Otherwise, test whether some initial deal satisfies all accumulated constraints:
    \begin{itemize}[leftmargin=*]
        \item for one set, enumerate all $4^4 = 256$ assignments of its four cards to starting players;
        \item keep only assignments satisfying the forced/forbidden information for those cards and
        the \texttt{need} conditions for that set;
        \item run a dynamic program over the $8$ sets and the numbers of cards already given to
        players $0,1,2$; player $3$ is implicit.
    \end{itemize}
    \item If the whole log is consistent, output \texttt{yes}. Otherwise binary-search the smallest
    prefix length that is inconsistent and output \texttt{no} with that index.
\end{enumerate}

\section*{Correctness Proof}

We prove that the algorithm returns the correct answer.

\paragraph{Lemma 1.}
After replaying any prefix, the maintained constraints describe exactly the set of initial deals
compatible with all observed actions in that prefix.

\paragraph{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. \qed

\paragraph{Lemma 2.}
For a fixed replayed prefix, the set-by-set dynamic program returns true exactly when some initial
deal satisfies all accumulated constraints.

\paragraph{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. \qed

\paragraph{Lemma 3.}
If a prefix is inconsistent, then every longer prefix is also inconsistent.

\paragraph{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. \qed

\paragraph{Theorem.}
The algorithm outputs the correct answer for every valid input.

\paragraph{Proof.}
By Lemma 1 and Lemma 2, \texttt{prefix\_consistent(k)} is true exactly for those prefixes that can
occur without cheating. If the full log is consistent, outputting \texttt{yes} is 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. \qed

\section*{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)$.

\section*{Implementation Notes}

\begin{itemize}[leftmargin=*]
    \item 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.
    \item The code stores the fourth player's card count implicitly, which keeps the DP array small and
    simple.
\end{itemize}

\end{document}