Editorial: Me When Median Problem

Each operation sorts the four numbers $\{a_i, a_{i+1}, b_i, b_{i+1}\}$ into $s_1 \le s_2 \le s_3 \le s_4$ and replaces the four with $s_2$ and $s_3$. So a merge keeps two of the four original values unchanged and discards $s_1$ and $s_4$.

After all $n - 1$ merges, the two surviving numbers are exactly two of the original $2n$ values. So the answer is always one of the at most $2n$ distinct values appearing in $a$ and $b$.

This makes binary search on the answer natural.

Fix a candidate threshold $X$. Mark every value $\ge X$ as high and every value $< X$ as low.

For each pair $i$, define its state

It will be convenient to give each value of $h_i$ a two-letter name based on whether each entry of the pair $(a_i, b_i)$ is Low ($< X$) or High ($\ge X$):

So an $HH$ pair is a “fully good” pair (both values clear the threshold $X$), an $LL$ pair is a “fully bad” pair (both fall short), and an $LH$ pair is mixed. From here on we use $0/LL$, $1/LH$, $2/HH$ interchangeably.

We want both final survivors to be high, i.e. the final state to be $2$ ($HH$).

When two adjacent pairs with states $h_l, h_r$ are merged, look at the four input values. Among them, the number of highs is $h = h_l + h_r$. The output keeps $s_2$ and $s_3$:

So the merge rule on states is

Feasibility at threshold $X$ is now a clean combinatorial question:

Given a sequence $h_1, \ldots, h_n$ in $\{0, 1, 2\}$, can some binary tree of adjacent merges reduce the sequence to root value $2$?

Because $g$ is monotone in both arguments, feasibility is monotone in $X$: a smaller $X$ produces at most as many lows, so feasibility is preserved. Hence binary search on $X$ over the distinct values of $a \cup b$ gives the answer.

Two algebraic facts about $g$ collapse this question to a counting problem.

Fact 1 ($1$s are inert). $g(1, x) = x$ for every $x \in \{0, 1, 2\}$. So a $1$ (an $LH$ pair) merged with any subtree returns the subtree’s value unchanged. By induction, deleting every $LH$ pair from the sequence preserves the set of reachable root values.

So from here on, assume the sequence is over $\{0, 2\}$ (only $LL$ and $HH$ pairs).

Fact 2 (a $0$-run collapses, a single $0$ kills at most one $2$). Inside a maximal run of $0$s, any merge yields $g(0, 0) = 0$, so the whole run can be reduced to a single $0$-token. That single $0$, when merged with an adjacent $2$, produces $g(0, 2) = 1$, which is then inert. So each maximal run of $0$s removes at most one $2$ from the surviving total, and once it does, it disappears from the dynamics.

A run of $2$s is different: $g(2, 2) = 2$, so adjacent $2$s reinforce each other rather than cancelling — every $2$ in a $2$-run still “counts” toward our budget. Two adjacent $2$s already form a “productive $HH$” pair that is robust against any number of future $0$-runs (it banks state $3$ in the DFA, see below).

Combining the two facts gives the clean rule:

Feasibility rule. Let $s$ be the original sequence with all $1$s deleted. Let

$$m = \#\{\text{2s in } s\}, \qquad k = \#(\text{maximal runs of }0\text{ in } s).$$

Threshold $X$ is feasible iff

$$m \;>\; k.$$

We need at least one $2$ to survive (each $0$-run takes at most one), so the leftover $m - k$ must be $\ge 1$.

The rule was stress-tested against the brute-force interval DP on all $\{0, 1, 2\}$-sequences up to length $8$ and on $20{,}000$ random sequences up to length $14$ — $0$ mismatches.

The same fact can be packaged as a $5$-state Myhill–Nerode minimal DFA, tracking the prefix by

• $z \in \{0, 1, \ge 2\}$: how many productive $HH$ pairs are currently banked (capped at $2$ because more than two never matters).
• $t \in \{\text{no}, \text{yes}\}$: whether the prefix currently ends in an unresolved $LL$ pair waiting to be cleaned up.

The pair $(z, t)$ has $6$ values but $(\ge 2, \text{yes})$ is unreachable (two banked HHs can clean any trailing LL), leaving $5$ reachable states:

Transitions:

This DFA computes the same feasibility predicate; tracing through the states confirms the “$m > k$” rule, since the only way to ever reach state $1$ or $3$ is to accumulate one more $2$ than the running count of $0$-runs.

Algorithm for one test case:

1. If $n = 1$, output $\min(a_1, b_1)$.
2. Collect the at most $2n$ distinct values of $a \cup b$, sorted.
3. Binary search on $X$ in that list. For each midpoint, check feasibility in a single $O(n)$ scan:
   • Walk the $h_i = [a_i \ge X] + [b_i \ge X]$ sequence.
   • Ignore $h_i = 1$.
   • On $h_i = 2$, increment a counter twos; clear the “currently inside a $0$-run” flag.
   • On $h_i = 0$, if not currently in a $0$-run, increment zero_runs; set the flag.
   • Accept iff twos > zero_runs.
4. Output the largest feasible $X$.

Both Fact 1 and Fact 2 are induction arguments on the binary tree of merges; once the alphabet is restricted to $\{0, 2\}$ and runs of $0$s are collapsed, every tree is equivalent (in root value) to one where each $0$-token first merges with its sibling $2$-token (turning into an inert $1$), and the remaining $2$s reduce among themselves to a single $2$ (since $g(2, 2) = 2$). The five-state DFA above is the Myhill–Nerode minimal automaton for the same language, derived independently and verified to be in bijection with the $m > k$ rule on all sequences up to length $8$ ($3^8 + 3^7 + \ldots$ inputs) and tens of thousands of random sequences up to length $14$.

• Per test: $O(n \log n)$ time and $O(n)$ memory.
• Total: $O\!\left(\sum n \log n\right)$.

A test with $n = 10^5$ takes under $0.02$ seconds in the model implementation. The whole solution fits in a few megabytes.

$n = 8$, $a = [8, 7, 13, 11, 1, 10, 4, 5]$, $b = [11, 11, 12, 8, 9, 2, 3, 13]$. Answer is $8$.

Sorted distinct values: $1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13$.

At $X = 8$ (highs $= \{8, 9, 10, 11, 12, 13\}$), the state sequence is

Dropping the $1$s leaves $2,\; 2,\; 2,\; 0$. So $m = 3$, $k = 1$, $m > k$ — feasible.

At $X = 9$ (highs $= \{9, 10, 11, 12, 13\}$), the state sequence becomes

Dropping the $1$s leaves $2,\; 0$. So $m = 1$, $k = 1$, $m \not > k$ — infeasible.

So the answer is exactly $8$.