ICPC 2019 - C. Checks Post Facto

#include <bits/stdc++.h>
using namespace std;

namespace {

struct Move {
    bool is_jump;
    vector<int> seq;
};

struct Piece {
    int color;   // 0 = black, 1 = white
    bool king;
    int origin;
};

enum class ActionType {
    success,
    add_start_piece,
    add_captured_piece,
    upgrade_origin,
    need_blocker,
    fail,
};

struct SimResult {
    ActionType type = ActionType::fail;
    int square = -1;
    int color = -1;
    int origin = -1;
    array<char, 32> final_board{};
};

int sq_row[32], sq_col[32];
int board_id[8][8];

bool is_king(char c) {
    return c == 'B' || c == 'W';
}

int piece_color(char c) {
    return (c == 'b' || c == 'B') ? 0 : 1;
}

char king_char(int color) {
    return color == 0 ? 'B' : 'W';
}

char man_char(int color) {
    return color == 0 ? 'b' : 'w';
}

bool man_allowed(int color, int sq) {
    int row = sq_row[sq];
    if (color == 0) {
        return row != 7;
    }
    return row != 0;
}

char minimal_piece(int color, int sq) {
    if (man_allowed(color, sq)) {
        return man_char(color);
    }
    return king_char(color);
}

bool same_color(char a, char b) {
    return piece_color(a) == piece_color(b);
}

bool insert_piece(array<char, 32>& start, int sq, char need, bool require_change) {
    char& cur = start[sq];
    if (cur == '.') {
        cur = need;
        return true;
    }
    if (!same_color(cur, need)) {
        return false;
    }
    if (is_king(need) && !is_king(cur)) {
        cur = need;
        return true;
    }
    return !require_change;
}

bool upgrade_origin(array<char, 32>& start, int origin, int color) {
    return insert_piece(start, origin, king_char(color), false);
}

bool in_bounds(int r, int c) {
    return 0 <= r && r < 8 && 0 <= c && c < 8;
}

int other_color(int color) {
    return color ^ 1;
}

bool promotion_row(int color, int sq) {
    int row = sq_row[sq];
    return color == 0 ? row == 7 : row == 0;
}

vector<pair<int, int> > jump_options_from(
    int sq,
    const array<int, 32>& board,
    const vector<Piece>& pieces
) {
    vector<pair<int, int> > result;
    int id = board[sq];
    if (id == -1) {
        return result;
    }
    const Piece& piece = pieces[id];
    static const int dr_all[4] = {1, 1, -1, -1};
    static const int dc_all[4] = {1, -1, 1, -1};
    for (int dir = 0; dir < 4; ++dir) {
        int dr = dr_all[dir];
        int dc = dc_all[dir];
        if (!piece.king) {
            if (piece.color == 0 && dr != 1) {
                continue;
            }
            if (piece.color == 1 && dr != -1) {
                continue;
            }
        }
        int mr = sq_row[sq] + dr;
        int mc = sq_col[sq] + dc;
        int tr = sq_row[sq] + 2 * dr;
        int tc = sq_col[sq] + 2 * dc;
        if (!in_bounds(tr, tc) || !in_bounds(mr, mc)) {
            continue;
        }
        int mid = board_id[mr][mc];
        int to = board_id[tr][tc];
        if (mid == -1 || to == -1) {
            continue;
        }
        if (board[to] != -1) {
            continue;
        }
        if (board[mid] == -1) {
            continue;
        }
        if (pieces[board[mid]].color == piece.color) {
            continue;
        }
        result.push_back(make_pair(mid, to));
    }
    return result;
}

pair<int, int> first_jump_for_player(
    int color,
    const array<int, 32>& board,
    const vector<Piece>& pieces
) {
    for (int sq = 0; sq < 32; ++sq) {
        if (board[sq] == -1 || pieces[board[sq]].color != color) {
            continue;
        }
        vector<pair<int, int> > opts = jump_options_from(sq, board, pieces);
        if (!opts.empty()) {
            return make_pair(sq, opts[0].second);
        }
    }
    return make_pair(-1, -1);
}

SimResult simulate(const array<char, 32>& start, int first_player, const vector<Move>& moves) {
    array<int, 32> board;
    board.fill(-1);
    vector<Piece> pieces;
    for (int sq = 0; sq < 32; ++sq) {
        if (start[sq] == '.') {
            continue;
        }
        Piece piece;
        piece.color = piece_color(start[sq]);
        piece.king = is_king(start[sq]);
        piece.origin = sq;
        board[sq] = (int)pieces.size();
        pieces.push_back(piece);
    }

    int player = first_player;
    for (const Move& move : moves) {
        int from = move.seq[0];
        if (board[from] == -1) {
            SimResult res;
            res.type = ActionType::add_start_piece;
            res.square = from;
            res.color = player;
            return res;
        }
        int id = board[from];
        if (pieces[id].color != player) {
            return SimResult();
        }

        if (!move.is_jump) {
            int to = move.seq[1];
            int dr = sq_row[to] - sq_row[from];
            int dc = sq_col[to] - sq_col[from];
            if (abs(dr) != 1 || abs(dc) != 1) {
                return SimResult();
            }
            if (!pieces[id].king) {
                if ((player == 0 && dr != 1) || (player == 1 && dr != -1)) {
                    SimResult res;
                    res.type = ActionType::upgrade_origin;
                    res.origin = pieces[id].origin;
                    res.color = player;
                    return res;
                }
            }

            pair<int, int> forced = first_jump_for_player(player, board, pieces);
            if (forced.first != -1) {
                SimResult res;
                res.type = ActionType::need_blocker;
                res.square = forced.second;
                return res;
            }

            if (board[to] != -1) {
                return SimResult();
            }
            board[from] = -1;
            board[to] = id;
            if (!pieces[id].king && promotion_row(player, to)) {
                pieces[id].king = true;
            }
        } else {
            int cur = from;
            bool promoted_now = false;
            for (int step = 1; step < (int)move.seq.size(); ++step) {
                int to = move.seq[step];
                int dr = sq_row[to] - sq_row[cur];
                int dc = sq_col[to] - sq_col[cur];
                if (abs(dr) != 2 || abs(dc) != 2) {
                    return SimResult();
                }
                if (!pieces[id].king) {
                    if ((player == 0 && dr != 2) || (player == 1 && dr != -2)) {
                        SimResult res;
                        res.type = ActionType::upgrade_origin;
                        res.origin = pieces[id].origin;
                        res.color = player;
                        return res;
                    }
                }
                int mr = (sq_row[cur] + sq_row[to]) / 2;
                int mc = (sq_col[cur] + sq_col[to]) / 2;
                int mid = board_id[mr][mc];
                if (board[mid] == -1) {
                    SimResult res;
                    res.type = ActionType::add_captured_piece;
                    res.square = mid;
                    res.color = other_color(player);
                    return res;
                }
                if (pieces[board[mid]].color == player) {
                    return SimResult();
                }
                if (board[to] != -1) {
                    return SimResult();
                }

                board[cur] = -1;
                board[mid] = -1;
                board[to] = id;
                cur = to;

                if (!pieces[id].king && promotion_row(player, cur)) {
                    if (step + 1 < (int)move.seq.size()) {
                        SimResult res;
                        res.type = ActionType::upgrade_origin;
                        res.origin = pieces[id].origin;
                        res.color = player;
                        return res;
                    }
                    pieces[id].king = true;
                    promoted_now = true;
                }
            }
            if (!promoted_now) {
                vector<pair<int, int> > extra = jump_options_from(cur, board, pieces);
                if (!extra.empty()) {
                    SimResult res;
                    res.type = ActionType::need_blocker;
                    res.square = extra[0].second;
                    return res;
                }
            }
        }

        player = other_color(player);
    }

    SimResult res;
    res.type = ActionType::success;
    res.final_board.fill('.');
    for (int sq = 0; sq < 32; ++sq) {
        if (board[sq] == -1) {
            continue;
        }
        const Piece& piece = pieces[board[sq]];
        res.final_board[sq] = piece.king ? king_char(piece.color) : man_char(piece.color);
    }
    return res;
}

string serialize(const array<char, 32>& start) {
    return string(start.begin(), start.end());
}

array<char, 32> answer_start, answer_final;
unordered_set<string> seen;

bool dfs(array<char, 32> start, int first_player, const vector<Move>& moves) {
    string key = serialize(start);
    if (!seen.insert(key).second) {
        return false;
    }

    while (true) {
        SimResult res = simulate(start, first_player, moves);
        if (res.type == ActionType::success) {
            answer_start = start;
            answer_final = res.final_board;
            return true;
        }
        if (res.type == ActionType::fail) {
            return false;
        }
        if (res.type == ActionType::add_start_piece || res.type == ActionType::add_captured_piece) {
            char need = minimal_piece(res.color, res.square);
            if (!insert_piece(start, res.square, need, true)) {
                return false;
            }
            continue;
        }
        if (res.type == ActionType::upgrade_origin) {
            if (!upgrade_origin(start, res.origin, res.color)) {
                return false;
            }
            continue;
        }
        if (res.type == ActionType::need_blocker) {
            for (int color = 0; color < 2; ++color) {
                array<char, 32> next = start;
                char need = minimal_piece(color, res.square);
                if (!insert_piece(next, res.square, need, true)) {
                    continue;
                }
                if (dfs(next, first_player, moves)) {
                    return true;
                }
            }
            return false;
        }
    }
}

Move parse_move(const string& s) {
    Move move;
    move.is_jump = s.find('x') != string::npos;
    int value = 0;
    for (char ch : s) {
        if (isdigit(ch)) {
            value = value * 10 + (ch - '0');
        } else {
            move.seq.push_back(value - 1);
            value = 0;
        }
    }
    move.seq.push_back(value - 1);
    return move;
}

vector<string> render_board(const array<char, 32>& board) {
    vector<string> out(8, string(8, '-'));
    for (int sq = 0; sq < 32; ++sq) {
        out[sq_row[sq]][sq_col[sq]] = board[sq];
    }
    for (int r = 0; r < 8; ++r) {
        for (int c = 0; c < 8; ++c) {
            if (board_id[r][c] == -1) {
                out[r][c] = '-';
            } else if (out[r][c] == '-') {
                out[r][c] = '.';
            }
        }
    }
    return out;
}

void init_board_map() {
    for (int r = 0; r < 8; ++r) {
        for (int c = 0; c < 8; ++c) {
            board_id[r][c] = -1;
        }
    }
    int id = 0;
    for (int r = 0; r < 8; ++r) {
        for (int c = 0; c < 8; ++c) {
            if ((r + c) % 2 == 1) {
                board_id[r][c] = id;
                sq_row[id] = r;
                sq_col[id] = c;
                ++id;
            }
        }
    }
}

void solve() {
    init_board_map();

    char first_char;
    int n;
    cin >> first_char >> n;
    vector<Move> moves(n);
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        moves[i] = parse_move(s);
    }

    array<char, 32> start;
    start.fill('.');
    int first_player = (first_char == 'B' ? 0 : 1);
    seen.clear();
    bool ok = dfs(start, first_player, moves);
    (void)ok;

    vector<string> before = render_board(answer_start);
    vector<string> after = render_board(answer_final);
    for (int r = 0; r < 8; ++r) {
        cout << before[r] << ' ' << after[r] << '\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 2019\\C. Checks Post Facto}
\author{}
\date{}

\begin{document}
\maketitle

\section*{Problem Summary}

We are given only a middle segment of a checkers game: whose turn starts first, and a sequence of legal moves. We must construct \emph{some} initial board such that these moves can be played legally in order, and then output both the initial board and the final board after the sequence.

The initial board does \emph{not} need to be reachable from a real game. It only needs to obey the local rules of checkers:
\begin{itemize}[leftmargin=*]
    \item men move forward, kings move both ways,
    \item captures are forced,
    \item jump moves must continue as long as that same piece can keep capturing,
    \item promotion ends the turn immediately,
    \item black men may not start on the last row and white men may not start on the first row.
\end{itemize}

\section*{Key Observations}

\begin{itemize}[leftmargin=*]
    \item Start from the empty initial board and replay the move list. Whenever the replay fails, repair the \emph{earliest} inconsistency by adding or upgrading the smallest possible initial piece, then restart from the beginning.
    \item There are three mandatory repairs:
    \begin{itemize}[leftmargin=*]
        \item If the moving square is empty, we must place a piece of the current player's color there initially.
        \item If a capture jumps over an empty square, we must place an opponent piece there initially.
        \item If a man ever needs to move or jump backward, or continue moving after reaching the promotion row, that piece must actually have been a king from the start.
    \end{itemize}
    \item The crucial monotonicity is: there is never any advantage to placing a king when a man would suffice. A king only creates extra possible moves and extra possible forced captures later. So every newly added piece should be the \emph{least powerful} piece compatible with the rules: a man if that row allows it, otherwise a king.
    \item After all mandatory repairs have converged, any remaining illegality must come from a forced capture that is \emph{not} taken in the given move list. Such a capture can be blocked by occupying its landing square. The blocking piece can be taken to be a minimal Black piece or a minimal White piece, so this is the only place where we need branching.
\end{itemize}

\section*{Algorithm}

\begin{enumerate}[leftmargin=*]
    \item Represent the initial board by 32 dark squares, initially all empty.
    \item Run a DFS on initial boards. For one fixed initial board:
    \begin{enumerate}[leftmargin=*]
        \item Replay the given move list from the beginning.
        \item Each current piece remembers the square where it started, so if we later discover it must really be a king, we can upgrade that initial square.
        \item Stop at the first inconsistency:
        \begin{itemize}[leftmargin=*]
            \item missing moving piece $\rightarrow$ add a minimal piece at that start square,
            \item missing captured piece $\rightarrow$ add a minimal opponent piece at that jumped-over square,
            \item illegal backward motion by a man, or a man that would need to continue after promotion $\rightarrow$ upgrade that piece's origin square to a king,
            \item an available forced capture that the move list does not take $\rightarrow$ branch by placing a minimal Black blocker or a minimal White blocker on the landing square of one such unwanted jump.
        \end{itemize}
        \item If a mandatory repair was applied, restart replay immediately from move 1 on the modified initial board.
        \item If all moves replay successfully, we have found a valid initial board and can output the resulting final board.
    \end{enumerate}
    \item Memoize visited initial boards so the DFS never explores the same state twice.
\end{enumerate}

\section*{Correctness Proof}

We prove that the algorithm outputs a valid pair of boards.

\paragraph{Lemma 1.}
If, during replay, the next listed move starts from an empty square, then any valid solution must contain a piece of the current player's color on that square initially.

\paragraph{Proof.}
At that moment in the replay, the listed move needs a piece on that square. Since our replay has already followed the same earlier moves, any piece that could be there must have existed from the initial position. Therefore some initial piece of the current player's color must occupy that square. \qed

\paragraph{Lemma 2.}
If, during replay, a listed jump needs an opponent piece on the jumped-over square and that square is empty, then any valid solution must contain an initial opponent piece on that square.

\paragraph{Proof.}
For the listed jump to be legal, the jumped-over square must contain an opponent piece at that moment. Since our replay has already processed all earlier listed moves exactly as required, the only way to make that happen is that some initial opponent piece remained there until being captured. \qed

\paragraph{Lemma 3.}
If a currently replayed piece must move backward as a man, or would need to keep moving after a man-promotion, then in every valid solution that piece must have started as a king.

\paragraph{Proof.}
A man is not allowed to move or jump backward. Also, once a man reaches the promotion row, the turn ends immediately. Therefore any listed move violating one of these restrictions cannot be made by a man at all; the same physical piece must have been a king before the move sequence started. \qed

\paragraph{Lemma 4.}
Whenever Lemma 1, 2, or 3 applies, performing the corresponding repair used by the algorithm cannot destroy any valid completion.

\paragraph{Proof.}
By Lemma 1 and Lemma 2, the required piece must exist in every valid solution, so adding the least powerful compatible initial piece only makes our partial reconstruction closer to any valid solution. By Lemma 3, upgrading that origin square to a king is also necessary in every valid solution. None of these repairs removes any move that must remain legal later. \qed

\paragraph{Lemma 5.}
After all mandatory repairs have converged, if the replay is still illegal, then the first remaining illegality is an untaken forced capture; blocking one such jump by occupying its landing square is sufficient, and trying both colors covers all possibilities.

\paragraph{Proof.}
All other local failures have already been eliminated by Lemma 4. Thus the only remaining issue is that the move list wants a simple move, or wants to stop a jump sequence, while some capture is available. A capture is unavailable as soon as its landing square is occupied. Therefore placing \emph{some} piece on that landing square blocks that unwanted jump. Since the color of that blocker is irrelevant for blocking, trying both colors is exhaustive; choosing a man whenever possible is the least restrictive option. \qed

\paragraph{Theorem.}
If a valid reconstruction exists, the DFS finds one and outputs a correct initial board and final board.

\paragraph{Proof.}
By Lemma 4, every mandatory repair preserves the existence of a valid completion. Once mandatory repairs are exhausted, Lemma 5 shows that every remaining valid solution corresponds to one of the blocker branches explored by the DFS. Hence the DFS never discards all valid solutions, and eventually reaches a state where replay succeeds completely. The reported initial board is exactly the board used for that successful replay, and the reported final board is the board obtained after executing the listed moves, so both outputs are correct. \qed

\section*{Complexity Analysis}

For a fixed initial board, replaying all moves is $O(n)$ because the board has constant size $32$. The DFS branches only when choosing blocker colors, and each branch permanently adds a new initial piece, so the search depth is at most $32$. Thus the theoretical worst case is exponential in the number of blocker decisions, but the state space is tiny in practice and the official intended solution relies on exactly this bounded backtracking.

\section*{Implementation Notes}

\begin{itemize}[leftmargin=*]
    \item Each live piece stores its origin square in the initial position. That makes the ``upgrade this piece to a king from the start'' repair immediate.
    \item When a new piece is added on a forbidden man row, the implementation inserts a king instead of a man, because that is the least powerful legal choice.
    \item Memoizing the 32-character initial board string prevents the DFS from revisiting the same reconstruction state.
\end{itemize}

\end{document}