= Solution
Use column heights and update the cached count by the number of removed cells:
``
class Chomps(N: Int) {
require(N > 0 && N.toLong * N.toLong <= Int.MaxValue)
private val height = Array.fill(N)(N)
private var remaining = (N.toLong * N.toLong).toInt
def Count(): Int = remaining
def Legal(x: Int, y: Int): Boolean =
0 <= x && x < N && 0 <= y && y < height(x)
def Move(x: Int, y: Int): Unit = {
require(Legal(x, y), "illegal move")
var i = x
while (i < N && height(i) > y) {
remaining -= height(i) - y
height(i) = y
i += 1
}
}
def Display(): Unit = {
require(N < 10, "single-digit display labels required")
var y = N - 1
while (y >= 0) {
print(y + " ")
var x = 0
while (x < N) {
print(if (y < height(x)) "* " else " ")
x += 1
}
println()
y -= 1
}
print(" ")
var x = 0
while (x < N) { print(x + " "); x += 1 }
println()
}
}
``
The strengthened <representation invariant> includes $remaining=\sum_i h(i)$. The move loop's processed columns have their final truncated heights, unprocessed columns retain their old heights, and each subtraction removes exactly the corresponding height reduction. Because heights are nonincreasing, once a column is no higher than `y`, neither is any later column; stopping there is valid. A legal move removes at least one token and leaves a <order ideal>.
The constructor computes $N^2$ in `Long` and checks representability before converting, avoiding <integer overflow> in the cached `Int` count. `Legal` rejects out-of-range coordinates before indexing. The methods meet the bounds in part (a); `Display` additionally checks its stated single-digit-label assumption.
Back to article page
