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
solution exists.
Let
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
of these), quadratically sorts its contents (
steps), and directly picks out the median rank, and optimizes this. The worst case situation is obtained by
and
. Therefore, this algorithm's time complexity is
.
Subtask 2
Using any
sort algorithm (these are well-known), the brute force algorithm can be improved to
. This solves subtask 2.
Also, an
sort (bucket sort) is possible, to obtain a simple
algorithm, but this does not suffice to solve Subtask 3.
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
algorithms are also possible and they solve Subtask 3. Here is one: say the vertical offset of the final rectangle is known [
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
scan length.]
This is rather involved to code; see Subtask 5 for a simpler and better solution.
Subtask 4
This subtask accommodates possible
algorithms, although we have not encountered them.
Subtask 5
Here is an
solution. Observe that the program's output can be verified by some algorithm which answers the question "Does any rectangle have median
?" This query can be answered in
time. A rectangle has median
if and only if it contains more values
than otherwise. Assign all cells in the grid a 'value' according to a 'threshold' function:
if greater than
,
if equal to
,
if less than
. 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
. We simply binary search values of
to find the minimum value for which the answer is "yes".
N.B. An
algorithm suffices for
score.
Linear Solution
Mihai Patrascu (ROM) found an
solution with the following reasoning.
Claim 1: Given a value
, one can identify in
time which rectangles have a median better than
.
Proof: In linear time, build a partial-sums array:
#{elements in
better than
}. The number of elements better than
in any rectangle can now be found by combining
values of
. The median of an
by
rectangle is better than
if and only if the number of elements better than
is less than
. QED
Claim 2: One can find the best median of
designated rectangles, in running time
.
Proof: Compress everything to a
grid and binary search for the best median. In each step of the binary search, I need to go over the entire
grid, and a number of elements that are originally
, but decreasing geometrically each time. QED
Claim 3: One can find the best median of all rectangles in
time.
Proof: By the above, one can set
and still get linear time. Sample
rectangles; apply Claim 2. Apply Claim 1 to filter everybody with worse medians. One is left with
rectangles. Do the same again, one is left with
rectangles. Now just apply Claim 2. QED
Comments