Problem: krabotage (2023 round3)

Despite his age, Mr. Krabs still goes trick-or-treating. Free candy (free anything, really) is irresistible to him. Bikini Bottom is an \(R \times C\) grid of houses, with house \((i, j)\) having \(A_{i,j}\) pieces of candy.

Mr. Krabs plans to travel from house \((1, 1)\), the top-left corner, to house \((R, C)\), the bottom-right corner, taking as much candy as possible along the way. When Mr. Krabs is at house \((i, j)\), he takes all the candy, and then either moves down to house \((i + 1, j)\) or right to house \((i, j + 1)\).

Plankton wants to sabotage him, and has decided to complete his own candy run before Mr. Krabs even starts his trip. Plankton will go from house \((1, C)\), the top-right corner, to house \((R, 1)\), the bottom-left corner. When Plankton is at house \((i, j)\), he takes all its candy (so there's none left for Mr. Krabs later) and either moves down to house \((i + 1, j)\) or left to house \((i, j - 1)\).

What's the maximum amount of candy that Mr. Krabs can collect, assuming that Plankton strives to minimize this value by completing his trip before Mr. Krabs starts?


# Constraints

\(1 \leq T \leq 100\)
\(2 \leq R, C \leq 300\)
\(0 \leq A_{i,j} \leq 1{,}000{,}000{,}000\)

The sum of \(R * C\) across all test cases is at most \(500{,}000\).


# Input Format

Input begins with an integer \(T\), the number of test cases. Each case begins with a line containing the two integers \(R\) and \(C\). Then, \(R\) lines follow, the \(i\)th of which contains the \(C\) integers \(A_{i,1}\) through \(A_{i,C}\).


# Output Format

For the \(i\)th test case, print "`Case #i:` " followed by a single integer, the maximum pieces of candy that Mr. Krabs can get if Plankton optimally sabotages.


# Sample Explanation

The following depicts sample cases 1 through 5. Plankton's paths to minimize Mr. Krabs's candy are greyed out, while Mr. Krabs's optimal paths through the remaining candy (in spite of Plankton's sabotage) are drawn in red.

{{PHOTO_ID:216354288143884|WIDTH:650}}


Sample input:
5
3 4
2 5 3 6
1 7 2 5
4 5 1 3
2 2
2 2
2 1
3 3
3 4 5
5 3 1
7 6 4
3 3
1 1 1
3 3 3
3 2 1
3 3
1 1 3
3 3 1
1 3 2


Sample output:
Case #1: 12
Case #2: 1
Case #3: 11
Case #4: 5
Case #5: 6


Solution: The key observation required is that the common part of Mr. Krabs and Plankton's paths will always be a single sub-row or sub-column of the input grid. We can use this observation to construct a dynamic programming approach.

Let's denote \(dp(r, c, d)\) as the minimum possible number of candies Mr. Krabs can collect if:
- Plankton started his route from house \((r, c)\),
- Plankton's route's next segment's direction is \(d\) (\(0\) for vertical, \(1\) for horizontal),
- Mr. Krabs's path intersects Plankton's path, and
- Mr. Krabs strives to maximize the number of candies he gets.

We see that the answer to the problem is equal to \(\min(dp(1, C, 0), dp(1, C, 1))\). To compute each \(dp(r, c, d)\), we will need to consider all valid lengths of the next path's segment. For each length, consider two scenarios and pick the maximum of those:
1. Mr. Krabs's path intersects the current segment.
2. Mr. Krabs's path will intersect one of the next segments.

For case 1, we can precompute helper tables \(\text{max\_up\_left}(r, c)\) and \(\text{max\_down\_right}(r, c)\) for the maximum number of pieces of candy that can be collected on the untouched grid. These computations are a classic dynamic programming problem, which can be done in \(O(R* C)\) time. The implementation requires considering all possible ways of crossing the current segment and finding the most profitable way for Mr. Krabs.

For case 2, we should simply check the value of \(dp(r', c', 1 - d)\), where \((r', c')\) is the first cell of the next segment.

In total, there are \(\mathcal{O}(R*C)\) DP states. Since we need to consider all possible valid segment lengths for each state, the overall complexity of the solution is \(\mathcal{O}(R*C*(R + C))\).


Code: #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

using int64 = long long;

int N, M;
vector<vector<int>> A;
vector<vector<int64>> dpl, dpr;
vector<vector<vector<int64>>> dp;

int64 rec(int dir, int x, int y) {
  if (dp[dir][x][y] != -1LL) {
    return dp[dir][x][y];
  }
  int64 res = dpr[0][0];
  if (dir) {
    int64 extra_exit = (y + 2 < M) ? dpr[x][y + 2] : 0;
    int64 max_cost = extra_exit;
    for (int ty = y; ty >= 0; --ty) {
      int64 best_entrance = 0LL;
      if (x) {
        best_entrance = max(best_entrance, dpl[x - 1][ty]);
        if (ty != y) {
          best_entrance = max(best_entrance, dpl[x - 1][ty + 1]);
        }
      }
      int64 best_exit = extra_exit;
      if (x + 1 != N && ty + 1 != M) {
        best_exit = max(best_exit, dpr[x + 1][ty + 1]);
      }
      max_cost = max(max_cost, best_entrance + best_exit);
      if (ty) {
        best_entrance = max(best_entrance, dpl[x][ty - 1]);
      }
      int64 local_max_cost = max(max_cost, best_entrance + best_exit);
      if (x + 1 != N || !ty) {
        int64 cur = (x + 1 == N) ? 0LL : rec(dir ^ 1, x + 1, ty);
        cur = max(cur, local_max_cost);
        res = min(res, cur);
      }
    }
  } else {
    int64 extra_entrance = (x - 2 >= 0) ? dpl[x - 2][y] : 0;
    int64 max_cost = extra_entrance;
    for (int tx = x; tx < N; ++tx) {
      int64 best_exit = 0LL;
      if (y + 1 != M) {
        best_exit = max(best_exit, dpr[tx][y + 1]);
        if (tx != x) {
          best_exit = max(best_exit, dpr[tx - 1][y + 1]);
        }
      }
      int64 best_entrance = extra_entrance;
      if (y && tx) {
        best_entrance = max(best_entrance, dpl[tx - 1][y - 1]);
      }
      max_cost = max(max_cost, best_entrance + best_exit);
      if (tx + 1 != N) {
        best_exit = max(best_exit, dpr[tx + 1][y]);
      }
      int64 local_max_cost = max(max_cost, best_entrance + best_exit);
      if (y || tx + 1 == N) {
        int64 cur = y ? rec(dir ^ 1, tx, y - 1) : 0LL;
        cur = max(cur, local_max_cost);
        res = min(res, cur);
      }
    }
  }
  return dp[dir][x][y] = res;
}

int64 solve() {
  cin >> N >> M;
  A.assign(N, vector<int>(M));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      cin >> A[i][j];
    }
  }
  dpl.assign(N, vector<int64>(M));
  dpr.assign(N, vector<int64>(M));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      dpl[i][j] = A[i][j];
      if (i) {
        dpl[i][j] = max(dpl[i][j], A[i][j] + dpl[i - 1][j]);
      }
      if (j) {
        dpl[i][j] = max(dpl[i][j], A[i][j] + dpl[i][j - 1]);
      }
    }
  }
  for (int i = N - 1; i >= 0; i--) {
    for (int j = M - 1; j >= 0; j--) {
      dpr[i][j] = A[i][j];
      if (i + 1 != N) {
        dpr[i][j] = max(dpr[i][j], A[i][j] + dpr[i + 1][j]);
      }
      if (j + 1 != M) {
        dpr[i][j] = max(dpr[i][j], A[i][j] + dpr[i][j + 1]);
      }
    }
  }
  dp.assign(2, vector<vector<int64>>(N, vector<int64>(M, -1LL)));
  return min(rec(0, 0, M - 1), rec(1, 0, M - 1));
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}