 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/imperative-programming/2/c/solution

Write

v = f [0, N - 1]

, assuming

M, N > 0

v

is at least every value in the first row and at most every value in the last column. Hence

v = x v < x v > x ⟹ (0, N - 1) is a solution, ⟹ discard row 0, ⟹ discard column N - 1.

The same observation applies to the top-right corner of any remaining rectangular subarray of this monotone matrix.

 New to topics? Read the docs here!