Me When Median Problem

Binary search the answer

We binary search the final value $x$. For a fixed $x$, call a number good if it is $\ge x$. We only need to know whether the final column has two good numbers.

For each column define

$$c_i = [a_i \ge x] + [b_i \ge x], \qquad c_i\in\{0,1,2\}.$$

If two columns with counts $p$ and $q$ are merged, then among the four boolean values, the operation keeps the middle two. So the new count is

$$F(p,q)= \begin{cases} 0, & p+q\le 1,\\ 1, & p+q=2,\\ 2, & p+q\ge 3. \end{cases}$$

Equivalently, $F(p,q)=\operatorname{clamp}(p+q-1,0,2)$.

The cute part

Notice that $1$ is an identity:

$$F(1,c)=c.$$

So columns with exactly one good value are useless middlemen. Delete them from the sequence.

Now only two types remain:

• $2$: a good token, call it $+$.
• $0$: a bad token, call it $-$.

The merge table becomes:

$$++\to +,\qquad --\to -,\qquad +-\to \text{identity}.$$

So equal signs compress, opposite signs cancel. Very civilized. Almost suspiciously so.

When can we end with $+$?

After deleting mixed columns, let:

• $P$ be the number of $+$ tokens, i.e. columns where both values are $\ge x$.
• $R$ be the number of maximal contiguous blocks of $-$ tokens, i.e. bad runs.

Claim:

$$x \text{ is achievable} \iff P > R.$$

Why necessary?

Every bad run must disappear before the final result can be $+$. A run of only $-$ tokens can only stay $-$ if merged internally. To destroy a bad run, some adjacent $+$ must cancel with it. That consumes one $+$ token.

There are $R$ bad runs, so at least $R$ good tokens are spent just cleaning up the garbage. To finish with $+$, one more good token must survive. Therefore

$$P \ge R+1 \iff P>R.$$

Why sufficient?

If $P>R$, repeatedly do this:

1. Pick any remaining bad run.
2. Collapse it to one $-$.
3. Cancel it with an adjacent $+$.

This consumes one $+$ and removes at least one bad run. If the current values are $P'$ and $R'$, after one cleanup step we still have

$$P'-1 > R'-1.$$

So the invariant $P>R$ survives until no bad runs remain. Then at least one $+$ is left, and all remaining $+$ tokens compress to one $+$.

That means the final column has two values $\ge x$, so $\min(a_1,b_1)\ge x$.

Algorithm

For a fixed $x$:

• Scan columns left to right.
• If both values are $\ge x$, increment $P$ and mark the last non-mixed type as good.
• If both values are $<x$, start a new bad run only if the previous non-mixed type was not bad.
• If the column is mixed, ignore it completely.

The predicate is monotonic: if $x$ works, every smaller value also works. Binary search $x$ from $1$ to $2n$.

Complexity

Each check is $O(n)$, and binary search does $O(\log n)$ checks since values are at most $2n$.

$$\text{Time per test case}=O(n\log n),\qquad \text{Memory}=O(n).$$

Across all tests, this easily fits because $\sum n\le 10^5$.