 Solution

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

0 \leq r \leq i, 0 \leq c < j i \leq r < M, j \leq c < N ⟹ f [r, c] < x, ⟹ f [r, c] > x .

Indeed the first entries are at most

f [i, j - 1]

, and the second are at least

f [i, j]

. In particular, the entire splitting row

i

contains no answer. The only remaining candidates are the upper-right rectangle

r < i, c \geq j

and the lower-left rectangle

r > i, c < j

. These are the exclusions guaranteed by the given adjacent inequalities; further comparisons may exclude more.

 New to topics? Read the docs here!