Matrix Game
Minimax with Bitmask Memoization This is a two-player zero-sum game solved by minimax: State: A pair of bitmasks $(rowMask, colMask)$ indicating which rows and columns remain, plus a boolean for whose turn it is. Tran...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
Two players play on an $m \times n$ matrix of integers. They alternate turns. On each turn, a player selects an entire remaining row or column, receives the sum of its entries, and removes it from the matrix. The game ends when no rows or columns remain. Player 1 maximizes their total score; Player 2 minimizes Player 1's total (equivalently, maximizes their own).
Determine Player 1's optimal score under perfect play.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Minimax with Bitmask Memoization
This is a two-player zero-sum game solved by minimax:
State: A pair of bitmasks $(\textit{rowMask}, \textit{colMask})$ indicating which rows and columns remain, plus a boolean for whose turn it is.
Transitions: Remove one remaining row or column.
Value: Player 1 maximizes accumulated score; Player 2 minimizes it.
The whose-turn information is determined by the parity of the number of removed rows/columns, so it need not be stored separately (though we include it for clarity).
State Space
With bitmasks for rows ($2^m$ states) and columns ($2^n$ states), plus the turn bit, the total number of states is $2 \times 2^m \times 2^n$. For $m, n \le 10$, this is $2^{21} \approx 2 \times 10^6$, which is feasible.
Bug Fix: Hash Key Encoding
The original code used the encoding $\textit{key} = (\textit{rowMask} \ll 20) \mid (\textit{colMask} \ll 8) \mid \textit{isMax}$, which causes collisions when $n > 8$ (since $\textit{colMask}$ can exceed 8 bits). The corrected version below uses a collision-free encoding.
Complexity Analysis
Time: $O(2^{m+n} \cdot (m+n) \cdot \max(m,n))$. Each of the $O(2^{m+n})$ states has $O(m+n)$ transitions, each requiring $O(\max(m,n))$ to compute the row/column sum.
Space: $O(2^{m+n})$ for memoization.
For $m, n \le 10$, this is comfortably within time limits.
Notes
The minimax approach gives the exact optimal result under perfect play from both players.
Alpha-beta pruning can speed up the search in practice but does not improve worst-case complexity.
The memoization key must encode rowMask, colMask, and the turn bit without collisions. With $m, n \le 12$, using 15 bits each for the masks and 1 bit for the turn suffices within a
long long.
Code
C++ solution used for this page.
// IOI 1991 - Problem 3: Matrix Game
// Two-player game on m x n matrix. Players alternate removing a row or column,
// scoring its sum. Player 1 maximizes, Player 2 minimizes Player 1's total.
// Minimax with bitmask memoization. Feasible for m,n <= 10.
#include <bits/stdc++.h>
using namespace std;
int m, n;
int A[12][12];
unordered_map<long long, int> memo;
int rowSum(int r, int colMask) {
int s = 0;
for (int c = 0; c < n; c++)
if (colMask & (1 << c)) s += A[r][c];
return s;
}
int colSum(int c, int rowMask) {
int s = 0;
for (int r = 0; r < m; r++)
if (rowMask & (1 << r)) s += A[r][c];
return s;
}
// Returns Player 1's optimal score from this state onward
int solve(int rowMask, int colMask, bool isMax) {
if (rowMask == 0 || colMask == 0) return 0;
long long key = ((long long)rowMask << 20) | ((long long)colMask << 8) | isMax;
auto it = memo.find(key);
if (it != memo.end()) return it->second;
int best = isMax ? INT_MIN : INT_MAX;
// Try removing each remaining row
for (int r = 0; r < m; r++) {
if (!(rowMask & (1 << r))) continue;
int s = rowSum(r, colMask);
int future = solve(rowMask ^ (1 << r), colMask, !isMax);
if (isMax)
best = max(best, s + future);
else
best = min(best, future); // Player 2 takes s, not added to P1
}
// Try removing each remaining column
for (int c = 0; c < n; c++) {
if (!(colMask & (1 << c))) continue;
int s = colSum(c, rowMask);
int future = solve(rowMask, colMask ^ (1 << c), !isMax);
if (isMax)
best = max(best, s + future);
else
best = min(best, future);
}
return memo[key] = best;
}
int main() {
scanf("%d%d", &m, &n);
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
scanf("%d", &A[i][j]);
printf("%d\n", solve((1 << m) - 1, (1 << n) - 1, true));
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.