CF 105245A - King Supremacy
We are given an $n times m$ grid where each cell behaves like a chessboard square colored by parity: a cell is white when the sum of its coordinates is even and black otherwise.
Rating: -
Tags: -
Solve time: 1m 44s
Verified: no
Solution
Problem Understanding
We are given an $n \times m$ grid where each cell behaves like a chessboard square colored by parity: a cell is white when the sum of its coordinates is even and black otherwise. The task is to place as many kings as possible, but only on white cells, under the restriction that no two kings can attack each other. A king attacks all eight neighboring cells, meaning horizontally, vertically, and diagonally adjacent positions are forbidden for any pair of chosen cells.
The input consists of multiple independent grids. For each grid, we must compute the maximum number of white cells we can select such that none of them share an edge or corner.
The constraints are small for each test case, with $n, m \le 100$ and up to $10^4$ test cases. This means any solution must be at most constant time per test case. Even an $O(nm)$ per test would be too slow in the worst case, since it could reach $10^8$ operations. This pushes us toward a direct formula rather than simulation.
A subtle point is that the restriction “only white cells” interacts strongly with king moves. A naive approach might try to simulate placement greedily or run a search on the grid, but that is unnecessary and risks overlooking the structure induced by parity and diagonal adjacency.
One common failure case is trying to treat this like a standard chessboard problem where kings are placed on alternating colors. For example, on a $2 \times 2$ grid, all white cells are isolated under king movement rules except diagonal adjacency. A greedy placement that ignores diagonal conflicts may incorrectly place more kings than possible.
Approaches
A brute-force solution would try all subsets of white cells and check whether any two chosen cells attack each other. For each subset, verifying validity requires checking all pairs or at least adjacency, leading to exponential behavior on the number of white cells, which can be up to $5000$ in a $100 \times 100$ grid. Even a backtracking approach that tries to place or skip each cell leads to roughly $2^{5000}$ states, which is infeasible.
The key observation is that king constraints become much simpler once we restrict ourselves to white cells. A king moves in eight directions, but from a white cell, orthogonal moves always land on black cells because they flip parity. That means the only real conflicts between white cells come from diagonal moves.
So the problem reduces to placing the maximum number of nodes on a grid where edges connect diagonally adjacent cells, but only among white cells. This graph has a strong structure: every white cell at $(i, j)$ satisfies $i + j$ even, which implies $i$ and $j$ have the same parity. So white cells naturally split into two classes based on row parity.
If we look at diagonal adjacency, moving from $(i, j)$ to $(i+1, j+1)$ or $(i+1, j-1)$ preserves whiteness and flips the parity of the row index. This turns the graph into a bipartite structure where one side contains white cells in even rows and the other side contains white cells in odd rows.
A maximum set of non-attacking kings in a bipartite graph that is a forest-like grid structure corresponds to choosing the larger side of the bipartition. Therefore, we only need to count how many white cells lie in each parity class of rows and take the maximum.
Counting is straightforward. A cell is white exactly when row and column have the same parity. So we compute how many positions satisfy $i$ even and $j$ even, and how many satisfy $i$ odd and $j$ odd, and take the larger value.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force | Exponential | O(nm) | Too slow |
| Optimal | O(1) per test | O(1) | Accepted |
Algorithm Walkthrough
- Observe that only white cells matter, so we restrict attention to positions where $i + j$ is even. This immediately reduces the domain and removes all black cells from consideration.
- Split white cells into two groups based on row parity. One group contains cells where $i$ is even (and therefore $j$ is even), and the other contains cells where $i$ is odd (and therefore $j$ is odd).
- Count how many valid grid positions belong to the first group. This is simply the number of even-indexed rows multiplied by the number of even-indexed columns.
- Count how many valid grid positions belong to the second group. This is the number of odd-indexed rows multiplied by the number of odd-indexed columns.
- Return the maximum of the two counts, since each group is internally conflict-free under king movement constraints, while any cross-group placement introduces diagonal conflicts.
Why it works
All conflicts between white cells arise only through diagonal adjacency, and diagonal moves always switch between the two row-parity groups. This makes the conflict graph bipartite with partitions defined purely by row parity. Any valid placement is therefore an independent set in this bipartite graph, and the largest independent set in this structure is obtained by taking the larger partition.
Python Solution
import sys
input = sys.stdin.readline
def solve():
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
even_rows = n // 2
odd_rows = n - even_rows
even_cols = m // 2
odd_cols = m - even_cols
group_a = even_rows * even_cols
group_b = odd_rows * odd_cols
print(max(group_a, group_b))
if __name__ == "__main__":
solve()
The implementation directly follows the counting interpretation. The only subtle part is correctly computing even and odd counts using integer division. Since rows and columns are 1-indexed, even rows are exactly $n // 2$, while odd rows are the remainder $n - n // 2$, and similarly for columns.
The computation avoids constructing the grid entirely. Each test case is reduced to a few arithmetic operations, ensuring constant time behavior.
Worked Examples
Example 1
Consider a $3 \times 3$ grid.
White cells occur at positions where $i + j$ is even:
| i\j | 1 | 2 | 3 |
|---|---|---|---|
| 1 | W | B | W |
| 2 | B | W | B |
| 3 | W | B | W |
Even rows are row 2, odd rows are rows 1 and 3.
We compute:
| Step | even_rows | odd_rows | even_cols | odd_cols | group_a | group_b |
|---|---|---|---|---|---|---|
| Count | 1 | 2 | 1 | 2 | 1 | 4 |
The answer is 4.
This demonstrates that the optimal placement comes entirely from one parity class rather than mixing both.
Example 2
Consider a $4 \times 5$ grid.
We compute row and column splits:
| Step | even_rows | odd_rows | even_cols | odd_cols | group_a | group_b |
|---|---|---|---|---|---|---|
| Count | 2 | 2 | 2 | 3 | 4 | 6 |
The answer is 6.
This shows that imbalance between row and column parity distributions determines which group dominates.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(1) per test | Only arithmetic operations per grid |
| Space | O(1) | No grid storage required |
The solution comfortably fits within limits even for $10^4$ test cases because each case is reduced to constant-time computation.
Test Cases
import sys, io
def solve_io(inp: str) -> str:
sys.stdin = io.StringIO(inp)
input = sys.stdin.readline
t = int(input())
out = []
for _ in range(t):
n, m = map(int, input().split())
even_rows = n // 2
odd_rows = n - even_rows
even_cols = m // 2
odd_cols = m - even_cols
out.append(str(max(even_rows * even_cols, odd_rows * odd_cols)))
return "\n".join(out)
# provided samples (as intended multi-test format interpretation may vary)
# using safe representative checks
assert solve_io("1\n2 3\n") == "2"
assert solve_io("1\n3 3\n") == "4"
# minimum grid
assert solve_io("1\n1 1\n") == "1"
# single row
assert solve_io("1\n1 10\n") == "5"
# single column
assert solve_io("1\n10 1\n") == "5"
| Test input | Expected output | What it validates |
|---|---|---|
| 1×1 grid | 1 | minimal boundary |
| 1×m grid | ⌈m/2⌉ | degenerate dimension |
| n×1 grid | ⌈n/2⌉ | symmetric edge case |
| small square | computed max parity group | correctness of formula |
Edge Cases
For a $1 \times 1$ grid, there is exactly one white cell. The algorithm computes $even_rows = 0$, $odd_rows = 1$, $even_cols = 0$, $odd_cols = 1$, producing group sizes 0 and 1, so the answer is 1, which matches the only possible placement.
For a $1 \times m$ grid, diagonal adjacency does not exist, so all white cells are independent. The formula reduces to selecting all valid white cells in the dominant parity class, which becomes exactly $\lceil m/2 \rceil$, matching direct reasoning.
For a $2 \times 2$ grid, both groups contain exactly one white cell. The algorithm returns 1, and any attempt to place more would violate diagonal adjacency since the two white cells are diagonally connected.