Problem Restatement

An N x M grid (M even) with values in [0, K]. Alice (minimizer) and Bob (maximizer) alternate turns, Alice first. The game has exactly M turns (one per column).

Each turn: Choose an unmarked column j and a cell in that column. Set that cell’s value to any a in [0, K]. The entire column j becomes marked.

Goal: Compute the final asymmetry under optimal play.

Asymmetry: Sum over all rows i and all column pairs (j, M-1-j) of g[i][j] - g[i][M-1-j] .

Key Insight: Per-Pair Decomposition (Mirroring Lemma)

Lemma. The game value equals Vmirror = Σ_p v_p, where the sum is over the M/2 reflected column-pairs p = {j, M-1-j} and v_p is the value of the isolated two-move subgame on pair p in which Alice moves first and Bob responds.

Bob attains this by mirroring: whenever Alice plays a column, Bob immediately plays its partner column. This is a provably optimal strategy for Bob (verified both ways below). Since each column is edited exactly once and a pair’s asymmetry contribution depends only on the two edited cells inside it, the board then splits into M/2 independent Alice-first / Bob-second episodes.

Proof of the decomposition (both bounds):

  • Bob guarantees ≥ Vmirror. Mirroring keeps the invariant “before each Alice move every pair is fully-open or fully-closed,” so Alice always opens a fresh pair and Bob closes it. The game becomes M/2 independent two-move episodes, each worth exactly v_p. Total = Σ v_p = Vmirror.
  • Alice caps at ≤ Vmirror. Let w_p be the pair value when Bob plays first (Alice responds last). Because Bob is the maximizer and moving last helps him, w_p ≤ v_p. The only way a pair can exceed v_p is if Bob edits both of its columns (value y_p ≥ v_p). Alice prevents this with a transversal/pairing strategy: Bob can claim only one column per turn, so the instant Bob opens a fresh pair, Alice closes it on her next move. Every pair then has exactly one Alice edit and one Bob edit, costing ≤ v_p. Hence Vgame ≤ Σ v_p = Vmirror.

Both bounds meet, so Vgame = Vmirror. ∎

Verification. Exhaustive minimax (independent of the closed-form formula below) confirms this on ~2400 random grids spanning M ∈ {4,6}, N ∈ {1,2,3}, K ∈ {1..5}:

  • Vgame == Vmirror (sum of per-pair Alice-first subgames) — 0 mismatches.
  • Vfree == Vbobmirror (Bob constrained to always mirror from the root vs. unconstrained) — 0 differences, i.e. Bob can never beat the mirror.

See test_mirror.py and test_mirror2.py.

Nuance (do not overstate the lemma). “Bob mirrors” is true as “there exists an optimal Bob strategy that always mirrors,” but not as “every optimal Bob move in every reachable position is a mirror.” Off the optimal line — after Bob has already deviated and left a dangling half-open pair that Alice threatens to seize (cost y_p) — mirroring the newly opened pair becomes suboptimal and Bob must instead close the dangling pair. These nodes never arise on optimal play (for M ≥ 6 they exist but only after a prior Bob blunder). Also, if Bob deviates and lets Alice take both columns of a pair, Alice drives that pair down to S - (two largest c[r]) (which is 0 only when N = 1 or the two largest c already cover all asymmetry — not “zero” in general).

Since the asymmetry is a sum over independent pairs, the game decomposes into M/2 independent per-pair subgames, each solved as follows:

  • c[r] = g[r][j] - g[r][M-1-j] , S = sum(c[r] for all rows r)
  • For each column assignment (Alice takes column j or M-1-j):
    • Alice picks row r_A and value v
    • Bob responds in the other column, choosing row r_B and value to maximize

Value Choice Analysis (given column & row)

When Alice sets g[r_A][col] = v and Bob sets g[r_B][other]:

  • Same row (r_B = r_A): Bob achieves max(v, K-v) at row r_A. Total = S - c[r_A] + max(v, K-v)

  • Different row (r_B != r_A): Alice’s row contributes |v - g[r_A][other]|, Bob’s row contributes max(g[r_B][col], K-g[r_B][col]). Total = S - c[r_A] + |v - x| + flip[r_B] where x = g[r_A][other] and flip[r] = max(g[r][col], K-g[r][col]) - c[r]

Critical Deviation From Original Plan: The Value Tradeoff

Original plan treated “same row” and “different row” as separate cases with independent value choices:

  • Match gain = half_k - max(c), achieved by Alice setting v = floor(K/2)
  • Different gain = -c[r_A] + best_flip_excluding(r_A), achieved by Alice setting v = x

This was wrong. Alice must pick a single value v that simultaneously addresses both threats:

  • v = floor(K/2) minimizes Bob’s same-row response
  • v = x minimizes Alice’s row contribution for different-row

Correct analysis: Alice minimizes over integer v:

f(v) = max(max(v, K-v), |v - x| + F)

where F = best flip gain excluding r_A. This is the maximum of two V-shaped functions and has a closed-form minimum:

a = min(x, K-x),  b = max(x, K-x)
If F <= a:         inner = half_k          (Bob's same-row defense is binding)
If a <= F <= b:   inner = ceil((b+F)/2)   (tradeoff between both threats)
If F > b:         inner = F               (Bob's different-row gain is binding)

The pair contribution for a given (column assignment, row r_A) is:

S - c[r_A] + inner

Alice picks the column assignment and row to minimize this.

N=1 Edge Case

When N=1, there are no different rows for Bob to target. Alice and Bob always go to the same row. Alice sets v = floor(K/2), Bob achieves ceil(K/2). Each pair contributes half_k.

Algorithm

For each of M/2 column pairs, in O(N):

  1. Compute c[r] and S
  2. For each column assignment (2 options): a. Compute flip gains for Alice’s column b. Find top 2 flip gains (for “best excluding any row” via the top-2 trick) c. For each row r_A: compute inner and gain = inner - c[r_A] d. Alice’s best for this column = min over r_A of gain
  3. Alice’s best = min over column assignments
  4. Add S + Alice’s best to total

Time: O(N * M), Space: O(N * M)