Omkar and Medians -- CF 1536D

Difficulty: 1700 * Techniques: constructive, invariant checking, set with ordered queries Problem Link

Quick Revisit

• PROBLEM: Can a sequence be consecutive medians of a growing array?
• KEY INSIGHT: Don't construct -- just check. No previously-used median value may lie strictly between consecutive medians.
• TECHNIQUES: constructive (existence check), set with lower_bound, invariant reasoning
• TRANSFER: "Does a valid construction exist?" -- find the necessary condition that separates YES/NO, skip actual construction.

First Read

Given a sequence $b_1,b_2,\dots ,b_n$ of desired medians, determine if there exists an array of size $2n-1$ such that after adding two elements and sorting each step, the medians match $b$. Well -- more precisely, we're constructing a sequence of arrays where each array of size $2i-1$ has median $b_i$.

Actually, re-reading: we have a sequence of $n$ numbers, and we need to decide if they can be consecutive medians of a growing sequence of odd-length. The answer is YES or NO.

My First Wrong Approach

I initially tried to construct the actual array -- inserting two elements at each step to shift the median to $b_{i+1}$. This got complicated fast. How do you choose the two elements? There are so many degrees of freedom.

Then I realized: we don't need to construct anything. We just need to check if the sequence $b$ is valid.

What Makes a Sequence Invalid?

Think about consecutive medians $b_i$ and $b_{i+1}$. Between them we insert two elements. The median can shift, but not arbitrarily. Here is the crisp invariant the file ends up depending on:

For every consecutive pair $b_i,b_{i+1}$ with $b_i\ne b_{i+1}$, no value already present in the array may lie strictly between $min(b_i,b_{i+1})$ and $max(b_i,b_{i+1})$.

Why: previously appearing medians are guaranteed to still be in the array (medians come from the array's elements and are never removed). If such a value $v$ sits strictly between the old and new median, then sorting the size-$2(i+1)-1$ array places $v$ closer to the middle than $b_{i+1}$, so the median can't jump past $v$ in one step of two insertions.

We only know with certainty about previously appearing medians, but that is enough -- they are the only values we are forced to include. So the check reduces to: between consecutive medians, no previously-used median value lies strictly between.

A small example of the violation

Suppose $b=[5,2,8]$.

• After step 1, the array is $[5]$ with median 5. Used set: $\{5\}$.
• Step 1 to step 2: median moves from 5 to 2. Range $(2,5)$ contains nothing in the used set, so this is allowed. Used set: $\{2,5\}$.
• Step 2 to step 3: median moves from 2 to 8. Range $(2,8)$ contains 5 -- and 5 is in the used set. Output NO.

The intuition: 5 is sitting in the array, and the median can't leap from 2 over 5 to 8 by inserting only two elements.

Compare with $b=[5,2,3]$, where the new range $(2,3)$ is empty in the used set (5 is outside the open interval), so the answer is YES. The "strictly between" semantics is exactly what the lower_bound(lo + 1) then *it < hi idiom captures.

The Algorithm

1. Maintain a set of "used" median values.
2. For each consecutive pair $(b_i,b_{i+1})$ where $b_i\ne b_{i+1}$:
   • Check if any value in the used set lies strictly between $b_i$ and $b_{i+1}$.
   • If yes: output NO.
   • If no: add $b_i$ to the used set (if not already there).
3. If we never fail, output YES.

The "check if any value lies strictly between" is a lower_bound / upper_bound query on a std::set. Clean and $O(n\log n)$.

Implementation Notes

• If $b_i=b_{i+1}$, no check needed -- the median doesn't move.
• We add $b_i$ to the set before processing the next transition, not after. Think of it as: $b_i$ has been "used" and is now in the array.
• Edge case: $n=1$ is always YES.

The Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    vector<int> b(n);
    for (auto& x : b) cin >> x;

    set<int> used;
    used.insert(b[0]);

    for (int i = 0; i + 1 < n; i++) {
        if (b[i] == b[i + 1]) {
            continue;
        }
        int lo = min(b[i], b[i + 1]);
        int hi = max(b[i], b[i + 1]);
        auto it = used.lower_bound(lo + 1);
        if (it != used.end() && *it < hi) {
            cout << "NO\n";
            return;
        }
        used.insert(b[i + 1]);
    }
    cout << "YES\n";
}

int main() {
    int t; cin >> t;
    while (t--) solve();
}

Transfer Lesson

• "Does a valid construction exist?" -- often you don't need to construct, just check necessary conditions. Find the invariant that separates YES from NO.
• Strictly-between check -- lower_bound(lo + 1) then compare with hi is the idiom for checking if a set has any element in the open interval $(lo,hi)$.
• Median problems -- the median is "sticky." Values near it resist change, so consecutive medians can't jump over previously-established values.

---

See also: Constructive Algorithms | Set and Multiset | Invariant Technique | Pattern Recognition Guide | Practice Ladder 1400-1700