GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Wednesday 2 November 2022

[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.

No comments:

Post a Comment