Greedy Grid Moves Codechef Solution

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}Ai,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}Ai+1,j​>Ai,j+1​
  • She will move the token to cell $(i,j+1)$ if A_{i+1, j} \lt A_{i, j+1}Ai+1,j​<Ai,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}Ai,1​,Ai,2​,…,Ai,M​.

Output Format

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

Constraints

Sample 1:

3
2 2
4 1
2 3
2 2
1 4
2 3
3 4
4 2 11 10
6 7 1 9
5 12 3 8

4
3
9

Explanation:

Test case $1$: Since A_{1, 1} = 4A1,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<7$ so she will never choose to do this.