Hints: Me When Median Problem

Each merge sorts $\{a_i, a_{i+1}, b_i, b_{i+1}\}$ and replaces the four numbers with $s_2$ and $s_3$. What happens to a value: is it modified, or simply kept or discarded?

Answer to Hint 1: Values are never combined arithmetically. Each merge keeps two of the four input values unchanged ($s_2$ and $s_3$) and discards the other two ($s_1$ and $s_4$).

So after all $n - 1$ merges, the two surviving numbers are exactly two of the original $2n$ values.

Answer to Hint 2: Since the answer is some original value, you can binary search on the answer $X$.

For each candidate $X$, ask: can the merge process keep both survivors $\ge X$?

Answer to Hint 3: Mark each value $\ge X$ as high, each value $< X$ as low. For pair $i$, let

$$ h_i = \#\{v \in \{a_i, b_i\} : v \ge X\} \in \{0, 1, 2\}. $$

Calling each entry of pair $(a_i, b_i)$ either Low ($< X$) or High ($\ge X$): an $HH$ pair has both entries high ($h_i = 2$), an $LH$ pair has one of each ($h_i = 1$), and an $LL$ pair has both low ($h_i = 0$). The goal is to reach root state $h = 2$, i.e. a surviving $HH$.

Answer to Hint 4: When two adjacent pairs with high-counts $h_l, h_r$ merge, count highs among the four input values: $h = h_l + h_r$. Keeping $s_2$ and $s_3$ gives:

So the merge rule on states is $g(a, b) = \max(0, \min(2, a + b - 1))$.

Answer to Hint 5: Feasibility for threshold $X$ is now a pure combinatorial question on a sequence in $\{0, 1, 2\}^n$:

Can some binary tree of adjacent merges reduce the sequence to root state $2$?

Notice that $g(1, x) = x$, so a $1$ ($LH$ pair) is inert — every $1$ in the sequence can be deleted without changing the set of reachable root values.

Answer to Hint 6: After dropping the $1$s, the sequence lives in $\{0, 2\}^*$ ($LL$s and $HH$s only). What does each kind of run do?

• A run of $0$s: every internal merge gives $g(0, 0) = 0$, so the whole run collapses to a single $0$ token.
• A run of $2$s: every internal merge gives $g(2, 2) = 2$, so all the $2$s “survive” and continue to count.

So a $0$-token represents an entire run of $LL$s, but each $2$ in a $2$-run is a separate “credit”.

Answer to Hint 7: What happens when a $0$-token meets a $2$? $g(0, 2) = g(2, 0) = 1$, which is inert. So merging a $0$-token with an adjacent $2$ kills both — the $2$ is consumed, and the result no longer interacts with anything.

Consequence: each maximal run of $0$s can remove at most one $2$.

Answer to Hint 8: Let

$$ m = \#\{i : h_i = 2\}, \qquad k = \#(\text{maximal runs of } 0 \text{ in the } 1\text{-dropped sequence}). $$

We have $k$ zero-runs and they together can kill at most $k$ of the $m$ twos. We need at least one $2$ to survive (the root would then be reachable as $2$). So:

Threshold $X$ is feasible $\iff m > k$.

Conversely, if $m \le k$ then every binary tree ends up with all twos cancelled by zero-runs.

Answer to Hint 9: The feasibility check is a single $O(n)$ left-to-right scan:

• For each $i$, compute $h_i = [a_i \ge X] + [b_i \ge X]$.
• Skip when $h_i = 1$.
• On $h_i = 2$, increment twos; clear an “in zero-run” flag.
• On $h_i = 0$, if the flag is off, increment zero_runs; set the flag.
• Accept iff twos > zero_runs.

Binary search on $X$ over the $\le 2n$ distinct candidate values gives the answer in $O(n \log n)$ total time and $O(n)$ memory.

Edge case: when $n = 1$ there are no merges, so the answer is just $\min(a_1, b_1)$.