Task Information for Quality of Living

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

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(N3).

Subtask 2

Using any O(N log N) sort algorithm (these are well-known), the brute force algorithm can be improved to O(N2 log N). This solves subtask 2.

Also, an O(N) sort (bucket sort) is possible, to obtain a simple O(N2) 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.

Subtask 3

O(N1.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(N0.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.

Subtask 4

This subtask accommodates possible O(N log N log N) algorithms, although we have not encountered them.

Subtask 5

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(n2) 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.

Linear Solution

Mihai Patrascu (ROM) found an O(N) solution with the following reasoning.

Claim 1:
Given a value X, one can identify in O(HW) time which rectangles have a median better than X.
Proof:
In linear time, build a partial-sums array: A[i][j] = #{elements in Q[0..i][0..j] better than X }. The number of elements better than X in any rectangle can now be found by combining 4 values of A. The median of an H by W rectangle is better than X if and only if the number of elements better than X is less than HW/2. QED
Claim 2:
One can find the best median of K designated rectangles, in running time O(K2 log(HW) + HW).
Proof:
Compress everything to a KxK grid and binary search for the best median. In each step of the binary search, I need to go over the entire KxK grid, and a number of elements that is originally HW, but decreasing geometrically each time. QED
Claim 3:
One can find the best median of all rectangles in O(HW) time.
Proof:
By the above, one can set K = sqrt(HW) / log(HW) and still get linear time. Sample K rectangles; apply Claim 2. Apply Claim 1 to filter everybody with worse medians. One is left with HW/K rectangles. Do the same again, one is left with HW/K2 ≤ log(HW) rectangles. Now just apply Claim 2. QED

O(N2) Solution for Subtask 2 in Pascal using bucket sort

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 }