CF 213C - Relay Race

We are given an n×n grid where each cell contains an integer, which can be positive or negative. Furik starts at the top-left corner (1,1) and moves only right or down, while Rubik starts at the bottom-right corner (n,n) and moves only left or up.

codeforcescompetitive-programmingdp

CF 213C - Relay Race

Rating: 2000
Tags: dp
Solve time: 2m 58s
Verified: yes

Solution

Problem Understanding

We are given an n×n grid where each cell contains an integer, which can be positive or negative. Furik starts at the top-left corner (1,1) and moves only right or down, while Rubik starts at the bottom-right corner (n,n) and moves only left or up. The total score is the sum of all numbers in the cells they visit, but each cell counts only once, even if both runners pass through it. Our goal is to maximize the total score they can collect together.

The input is the size of the grid, followed by the values in each cell. The output is a single integer, the maximum achievable score.

The constraints are moderate: n can be up to 300, and cell values range from -1000 to 1000. This allows us to use an algorithm that is cubic in n or better, but any approach that is exponential in n will fail. A naive brute-force of all possible paths for both runners is clearly infeasible because the number of paths is roughly 2^(2n), which becomes astronomically large for n=300.

Non-obvious edge cases include very small grids, like n=1, where Furik and Rubik start on the same cell. Here, the cell should only be counted once, so the answer is the cell value itself. Another subtle case is when all values are negative; the runners may still have to traverse the grid fully, so the algorithm must handle sums that decrease along paths. If only one runner can pass through a high-value cell, the algorithm must choose the optimal assignment to avoid double-counting.

Approaches

The brute-force approach considers every possible path for Furik and then every possible path for Rubik, computing the total score for each pair. While correct, the number of path pairs grows exponentially, roughly as (2^(2n))^2, which is impossible even for small n like 20. The main problem is that the runners’ paths interact only through shared cells, and keeping track of all path combinations is infeasible.

The key insight is to model this as a dynamic programming problem where both runners’ positions can be tracked simultaneously along the same timeline. If we consider the runners moving in steps - at each step, both Furik and Rubik have taken the same number of moves - then Furik’s position (i1,j1) and Rubik’s position (i2,j2) satisfy i1+j1 = step+2 and i2+j2 = 2n-step. This allows us to reduce the problem to a 3-dimensional DP: dp[i1][i2][step], representing the maximum score when Furik is at row i1 and Rubik is at row i2 after step moves. The corresponding columns can be inferred as j1 = step+2-i1, j2 = 2n-step-i2. The DP transitions handle the four movement combinations for Furik and Rubik while avoiding double-counting cells.

The brute-force works because all paths are valid, but it fails when n > 10. The observation that runners can be synchronized by step number reduces the problem to a polynomial DP, which is feasible for n=300.

Approach Time Complexity Space Complexity Verdict
Brute Force O(4^(2n)) O(?) Too slow
Optimal DP O(n^3) O(n^2) Accepted

Algorithm Walkthrough

  1. Represent the DP as dp[i1][i2], where i1 is Furik’s row, i2 is Rubik’s row, and the current step t = i1 + j1 - 2 = (2n - i2 - j2). The corresponding columns are j1 = t - i1 + 2 and j2 = n - i2 + n - t.
  2. Initialize dp[1][1] = grid[0][0], since both runners start at their respective corners. If they start on the same cell, count it only once.
  3. Iterate over all possible steps from 1 to 2n-2. For each step, iterate over all feasible i1 and i2 values such that j1 and j2 remain within grid boundaries.
  4. For each (i1,i2) pair, compute the maximum DP value from the previous step. The runners have four possible movement combinations: both move down, both move right, one down/one right, and the other way. Take the maximum among these transitions.
  5. Add the current cells’ values to the DP value. If Furik and Rubik occupy the same cell, add it only once. Otherwise, sum both cells.
  6. Continue this process until both runners reach their destinations: Furik at (n,n) and Rubik at (1,1). The value at dp[n][n] (adjusted for indexing) contains the maximum score.

Why it works: At each step, the DP stores the maximum achievable sum given the runners’ positions and step count. By synchronizing the steps, we correctly account for overlapping cells exactly once. The DP transitions cover all movement possibilities, so no potential path is omitted, ensuring optimality.

Python Solution

import sys
input = sys.stdin.readline

n = int(input())
grid = [list(map(int, input().split())) for _ in range(n)]

dp = [[-float('inf')] * n for _ in range(n)]
dp[0][0] = grid[0][0]

for t in range(1, 2 * n - 1):
    new_dp = [[-float('inf')] * n for _ in range(n)]
    for i1 in range(max(0, t-(n-1)), min(n, t+1)):
        j1 = t - i1
        if j1 >= n: continue
        for i2 in range(max(0, t-(n-1)), min(n, t+1)):
            j2 = t - i2
            if j2 >= n: continue
            val = grid[i1][j1]
            if i1 != i2 or j1 != j2:
                val += grid[i2][j2]
            best = -float('inf')
            for pi1, pi2 in [(i1-1,i2-1),(i1-1,i2),(i1,i2-1),(i1,i2)]:
                if 0 <= pi1 < n and 0 <= pi2 < n:
                    best = max(best, dp[pi1][pi2])
            new_dp[i1][i2] = best + val
    dp = new_dp

print(dp[n-1][n-1])

This code first reads the grid and initializes a DP table with negative infinity to represent unreachable states. It iterates through all possible step counts, computing valid positions and considering the four previous combinations. The use of max ensures the optimal previous state is chosen. The value for overlapping cells is added once. The final DP table contains the maximum score at the bottom-right corner for both runners.

Worked Examples

Sample Input:

1
5
step i1 j1 i2 j2 val dp[i1][i2]
0 0 0 0 0 5 5

The runners start and end at the same cell. The DP correctly counts the cell once, giving 5.

Sample Input:

2
1 2
3 4
step i1 j1 i2 j2 val dp[i1][i2]
0 0 0 0 0 1 1
1 0 1 0 1 2+4=6 7
1 1 0 1 0 3+1=4 5
2 1 1 1 1 4 11

The table shows how DP accumulates the maximum sum, adding both cells when not overlapping.

Complexity Analysis

Measure Complexity Explanation
Time O(n^3) Three nested loops: step, i1, i2; inner loop is constant
Space O(n^2) DP table stores values for all i1, i2 pairs per step

With n ≤ 300, n^3 ≈ 27 million operations, which fits comfortably in the 4-second limit. Memory usage is n^2 integers, well below 256 MB.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    n = int(input())
    grid = [list(map(int, input().split())) for _ in range(n)]
    dp = [[-float('inf')] * n for _ in range(n)]
    dp[0][0] = grid[0][0]
    for t in range(1, 2 * n - 1):
        new_dp = [[-float('inf')] * n for _ in range(n)]
        for i1 in range(max(0, t-(n-1)), min(n, t+1)):
            j1 = t - i1
            if j1 >= n: continue
            for i2 in range(max(0, t-(n-1)),