GitHub 源文件 Markdown 中文

Interval Medians

Algorithm and attribution

Problem setter's solution: fix a left endpoint, extend the right endpoint, and maintain two sorted parts with heaps. Codex (GPT-6) organizes the implementation, states the size invariants and verifies boundary cases. Program: std.cpp.

The sliding-window algorithm, with source, is a parallel option: it outputs by length directly, reducing space from \(O(n^2)\) to \(O(n)\) with the same time bound. It requires ordered multisets supporting deletion. The reference keeps the problem setter's heap algorithm; both time/space choices remain available.

Two-heap invariant

The lower part has \(\lceil L/2\rceil\) elements and the upper part has \(\lfloor L/2\rfloor\) . Use a max-heap for the lower part and a min-heap for the upper part. Every lower value must be at most every upper value. Store equal values with their multiplicities.

Insert a value into the lower heap if that heap is empty or the value does not exceed its maximum; otherwise insert it into the upper heap. If the lower heap has the wrong size, move one boundary element between the heaps. Insertion and these moves preserve the ordering between parts.

For odd length, return twice the lower heap's maximum. For even length, return the sum of the two boundary values. Compare container sizes using signed integers or addition, avoiding unsigned subtraction underflow.

Correctness

Both heaps start empty. Inductively, insertion and adjustment preserve the required sizes and ordering. Thus the heaps contain precisely the two specified parts of the sorted interval. Their boundaries or maintained sum give twice the median.

Rebuild the heaps for each left endpoint and extend the right endpoint through every possible position. This visits every nonempty interval exactly once. Store answers indexed by length and left endpoint, then print in the required order.

Complexity and numeric bounds

There are \(n(n+1)/2\) extensions, each performing a constant number of heap operations. Time is \(O(n^2\log(n+1))\) . The heaps use \(O(n)\) space and the answer table uses \(O(n^2)\) . Output alone requires \(\Omega(n^2)\) time.

Let \(U=\max_i\lvert a_i\rvert\) . The absolute answer is at most \(2U\) . It fits a signed 32-bit integer under these constraints; the implementation consistently uses 64-bit integers to keep the doubling operation explicit and safe. Negative values cannot be discarded; each interval has a fixed number of selected elements.

Verification and Use

Every sequence of length at most six over a three-value alphabet is checked by sorting each interval, with additional random large and negative values. Formal data cover thousand-element monotone, constant and alternating-extreme sequences.

The ten input recipes, fixed seeds and purposes are in tests/plan.json . After compiling the program, run:

python tests/generate.py --out-dir <output-directory> --std <compiled-program>

Omit --std to generate only inputs, or use --case 01 to select one input. Independent checks are in check_r15.py. See the five-round alternating measurements and environment. Finite tests and timings of these implementations supplement the proofs; they do not establish a time guarantee for every implementation with the same asymptotic bound.

Measured Results

Program	Largest per-case median	Peak working set
Reference	0.074143 s	9.11 MiB
Alternative	0.206148 s	5.38 MiB

The reference limit is 0.5 seconds. Both programs agree on all ten measured formal inputs and finish within this limit. Peak working set includes process overhead; maximum time and memory may come from different inputs.