ChatGPT OpenAI SWE DSA Round

You are given a rectangular grid board of size N x M where each cell contains an integer. A player starts from cell (0, p) in the top row. The objective is to reach the bottom of the grid while maximizing the total score collected.

From a cell (i, j), the player may move to:

(i+1, j-1) → diagonally left-down
(i+1, j) → straight down
(i+1, j+1) → diagonally right-down
(i+2, j) → special jump move

The player must always remain inside the grid boundaries.

The special jump move (i+2, j) may be used at most K times during the traversal.

The total score is equal to the sum of all visited cell values.

Question 1: Find the maximum achievable score from the starting cell to any cell in the last row.

Question 2: Return one path that produces the maximum score.

Question 3: Return the number of distinct maximum-score paths modulo 10^9 + 7.

Example:

board =
[
[1, 2, 3, 4],
[5, 6, 1, 2],
[7, 8, 9, 1],
[3, 2, 5, 6]
]

p = 1
K = 1

One valid path:

(0,1) → (1,1) → (2,2) → (3,3)

Another valid path using a jump:

(0,1) → (2,1) → (3,2)

Question 4:
Additionally:

visiting two consecutive cells with equal values gives bonus +X
visiting three strictly increasing values consecutively gives bonus +Y