Task Author: Christopher Chen (AUS)
This problem looks like many other grid tasks. Such problems have also appeared on some previous IOIs. Heavy range-search algorithms might seem to be useful, but actually a much simpler 100% solution exists.
Let N = R*C measure the size of a problem instance.
Subtask 1 can be solved by the most obvious brute force algorithm that considers each rectangle (there are (R-H+1)*(C-W+1) of these), quadratically sorts its contents ((H*W)^{2} steps), and directly picks out the median rank, and optimizes this. The worst case situation is obtained by H=R/2 and W=C/2. Therefore, this algorithm's time complexity is O(N^{3}).
Using any O(N log N) sort algorithm (these are well-known), the brute force algorithm can be improved to O(N^{2} log N). This solves subtask 2.
Also, an O(N) sort (bucket sort) is possible, to obtain a simple O(N^{2}) algorithm, but this does not suffice to solve Subtask 3. See below for a Pascal implementation.
There are some obvious opportunities for improvement, such as exploiting the large overlap between certain rectangles when filling/emptying the array to be sorted. But these improvements do not affect the time complexity.
O(N^{1.5} log N) algorithms are also possible and they solve Subtask 3. Here is one: say the vertical offset of the final rectangle is known [O(N^{0.5}) possibilities]. Then scan across the row, using some efficient data structure to keep track of the median (think of incremental/sliding window, such as a range tree plus binary search, or a pair of heaps for values less/greater than the median). [Each value is added/subtracted from the data structure exactly once, for an O(N log N) scan length.]
This is rather involved to code; see Subtask 5 for a simpler and better solution.
This subtask accommodates possible O(N log N log N) algorithms, although we have not encountered them.
Here is a O(N log N) solution. Observe that the program's output can be verified by some algorithm which answers the question "Does any rectangle have median ≤ X?" This query can be answered in O(n^{2}) time. A rectangle has median ≤ X if and only if it contains more values ≤ X than otherwise. Assign all cells in the grid a 'value' according to a 'threshold' function: -1 if greater than X, 0 if equal to X, 1 if less than X. Using the well-known cumulative data structure for queries on rectangular sums, try all possible rectangle locations and return "yes" if the 'values' inside any sum to ≥ 0. We simply binary search values of X to find the minimum value for which the answer is "yes".
N.B. An O(N log N) algorithm suffices for 100% score.
Mihai Patrascu (ROM) found an O(N) solution with the following reasoning.
const MaxDimension = 3000; MaxRank = sqr(MaxDimension); type TCoordinate = 0 .. MaxDimension - 1; TRank = 1 .. MaxRank; Qtype = array [ TCoordinate, TCoordinate ] of TRank; TRankSet = array [ TRank ] of Boolean; var sorttemp: TRankSet; { for bucket sorting and median finding, kept global for speed } function rectangle(R, C, H, W: Longint; var Q: Qtype): TRank; { returns best median of all HxW rectangles in RxC city Q } function median(a, b: TCoordinate): TRank; { returns median rank in rectangle with top-left corner at [a, b] } var i, j: TCoordinate; { traverses Q } r: Longint; { traverses [ 0 ] + sorttemp } c: Longint; { counts elements in sorttemp <= r } begin { insert elements from rectangle into the buckets } for i := a to a + H - 1 do begin for j := b to b + W - 1 do begin sorttemp[ Q[i, j] ] := True end { for j } end { for i } { determine the median by counting off half the elements } ; r := 0 { r in [ 0 ] + sorttemp } ; for c := 1 to (H * W) div 2 + 1 do begin repeat r := r + 1 until sorttemp[r] end { for c } ; median := r { restore invariant for sorttemp, by removing the elements } ; for i := a to a + H - 1 do begin for j := b to b + W - 1 do begin sorttemp[ Q[i, j] ] := False end { for j } end { for i } end; { median } var i: TRank; { traverses sortemp for initialization } result: TRank; { best rank seen so far } a, b: TCoordinate; { traverses all rectangles } m: TRank; { median of rectangle with top-left corner at [a, b] } begin for i := 1 to R * C do sorttemp[i] := False ; result := MaxRank; ; for a := 0 to R - H do begin for b := 0 to C - W do begin m := median(a, b) ; if m < result then result := m end { for b } end { for a } ; rectangle := result; end; { rectangle }