Back to solutions

Grid Game

MediumArrays

Minimize the second robot's best path after the first robot plays optimally.

Open problem
Constraints
  • 1 <= n <= 5*10^4
  • 0 <= grid[i][j] <= 10^5

Try every turn-down column

Time O(n)Space O(1)

The first robot's path is fully described by the column where it drops from the top row to the bottom row. For each such column, the second robot's best is the larger of the remaining top-right sum and the remaining bottom-left sum. The first robot picks the column minimising that maximum, computed with running prefix/suffix sums.

Key terms
turn-down column:
The single column where the first robot moves from the top row to the bottom row.
minimax:
Minimising the maximum the opponent can achieve.
long long gridGame(vector<vector<int>>& grid) {
    int n = grid[0].size();
    long long topRight = 0;
    for (int j = 1; j < n; j++) topRight += grid[0][j];
    long long bottomLeft = 0, res = LLONG_MAX;
    for (int j = 0; j < n; j++) {
        res = min(res, max(topRight, bottomLeft));
        if (j + 1 < n) topRight -= grid[0][j + 1];
        bottomLeft += grid[1][j];
    }
    return res;
}
Step by step
  1. Precompute topRight = sum of the top row to the right of column 0.
  2. Sweep each column j: remove grid[0][j] from topRight (the first robot took it).
  3. The second robot's best at this turn is max(topRight, bottomLeft); track the minimum over all j.
  4. Add grid[1][j] to bottomLeft after evaluating. Return the tracked minimum.