[Solution] Greedy Grid Moves CodeChef

Problem

Anya and Becky found an $N\times M$ grid that contains distinct integers, and decided to play a game on it. The integer present at the intersection of the $i$-th row and $j$-th column is denoted $A_{i, j}$.

They place a token at the top-left corner (cell $(1, 1)$), and then take turns moving the token towards the bottom-right corner (cell $(N, M)$), each time moving the token one step right or down. Becky moves first.

Suppose the token is at position $(i, j)$. Then,

• Becky can choose to move the token to either $(i+1, j)$ or $(i, j+1)$.
• Anya, in her infinite greed wisdom, will always move the token to whichever cell has the larger value. That is,
  • She will move the token to cell $(i+1, j)$ if $A_{i+1, j} \gt A_{i, j+1}$
  • She will move the token to cell $(i, j+1)$ if $A_{i+1, j} \lt A_{i, j+1}$

Of course, the token must remain inside the grid at all times, so if $i = N$ they cannot move it down and if $j = M$ they cannot move it right.

Let $K$ be the maximum value the two encounter on their path from $(1, 1)$ to $(N, M)$. Becky would like to rein in Anya a bit, so please help her: if she makes her moves optimally, what is the minimum possible value of $K$?

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line of each test case contains two space-separated integers $N$ and $M$ — the number of rows and columns of the grid.
  • The next $N$ lines describe the grid. The $i$-th of these $N$ lines contains $M$ space-separated integers $A_{i, 1}, A_{i, 2}, \ldots, A_{i, M}$.

Output Format

For each test case, output on a new line the minimum possible value of $K$, if Becky chooses her moves optimally.

Explanation:

Test case $1$: Since $A_{1, 1} = 4$ is the largest value in the grid, no matter what path is taken the maximum value is going to be $4$.

Test case $2$: Becky can move the token down in the first move, which forces Anya to move right on hers. This gives the path $1 \to 2 \to 3$ with a maximum of $3$, which is the best possible.

Test case $3$: The optimal path is $4 \to 6 \to 7 \to 1 \to 9 \to 8$, with a maximum of $9$.
Note that if Anya had chosen to move down to $5$ when at $6$, she could have forced the maximum to be $12$. However, $5 \lt 7$ so she will never choose to do this.