405894: GYM102152 L Median

You are given a grid $$$g$$$ consisting of $$$n$$$ rows each of which is divided into $$$m$$$ columns. The grid contains unique values between $$$1$$$ and $$$n \times m$$$ (inclusive).

Also, you are given two values $$$h$$$ and $$$w$$$, and your task is to find the smallest median value that can be found in a rectangle of size $$$h \times w$$$.

A rectangle of size $$$h \times w$$$ is a rectangle consisting of $$$h$$$ rows and $$$w$$$ columns such that its top left corner is at a cell ($$$a,\,b$$$) and its right bottom corner is at a cell ($$$c,\,d$$$), and the following conditions are satisfied: ($$$c - a + 1 \equiv h$$$) and ($$$d - b + 1 \equiv w$$$).

The median of a set of numbers is the middle element in the sorted list of the given set. For example, the median of $$$\{2, 1, 3\}$$$ is $$$2$$$ and the median of $$$\{4, 2, 3, 1, 5\}$$$ is $$$3$$$.

The first line contains four integers $$$n$$$, $$$m$$$, $$$h$$$, and $$$w$$$ ($$$1 \le n,\,m \le 10^3$$$, $$$1 \le h,\,w \le n$$$), in which $$$n$$$ and $$$m$$$ are the number of rows and columns in the grid, respectively, and $$$h$$$ and $$$w$$$ are representing the size of the required rectangle. Both $$$h$$$ and $$$w$$$ are odd integers.

Then $$$n$$$ lines follow, each line contains $$$n$$$ integers, giving the grid. It is guaranteed that the grid contains unique values between $$$1$$$ and $$$n \times m$$$ (inclusive).

Print a single line containing the smallest median value that can be found in a rectangle of size $$$h \times w$$$.

4 4 3 3
13 16 15 4
5 2 8 9
14 11 12 10
1 6 3 7

6

In the first test case, there are $$$4$$$ possible rectangles of size $$$3 \times 3$$$, which are:

1. Starts at ($$$1,\,1$$$). $$$\rightarrow$$$ Contains elements: $$$\{13, 16, 15, 5, 2, 8, 14, 11, 12\}$$$. $$$\rightarrow$$$ Median value = $$$12$$$.
2. Starts at ($$$1,\,2$$$). $$$\rightarrow$$$ Contains elements: $$$\{16, 15, 4, 2, 8, 9, 11, 12, 10\}$$$. $$$\rightarrow$$$ Median value = $$$10$$$.
3. Starts at ($$$2,\,1$$$). $$$\rightarrow$$$ Contains elements: $$$\{5, 2, 8, 14, 11, 12, 1, 6, 3\}$$$. $$$\rightarrow$$$ Median value = $$$6$$$.
4. Starts at ($$$2,\,2$$$). $$$\rightarrow$$$ Contains elements: $$$\{2, 8, 9, 11, 12, 10, 6, 3, 7\}$$$. $$$\rightarrow$$$ Median value = $$$8$$$.

So, the smallest median value that can be found in a rectangle of size $$$3 \times 3$$$ is $$$6$$$.