The problem is from today's Educational Codeforces Round 171. After spending nearly two hours trying to solve this problem, I wasn’t able to achieve the desired results. Here’s an outline of my approach:

The task is to determine the smallest $$$k$$$ for which we can make all cells black, with at most one additional midpoint insertion. For each consecutive elements in the sequence, I computed both the floor and ceil midpoints as follows:

Each midpoint divides the original gap $$$v[i+1] - v[i]$$$ into two new segments:

Left Gap: $$$ \text{mid} - v[i] $$$

Right Gap: $$$ v[i+1] - \text{mid} $$$

I inserted each midpoint separately, recalculated the largest and second-largest gaps among all segments, then restored the original sequence. By aiming to minimize the maximum of these gaps across all midpoint attempts, I sought to find the smallest feasible $$$k$$$ that allows painting all required cells black.

Here’s my submission link smash me. If someone is having trouble accessing the link, here is my implementation:

void solve () {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    if (n == 1) {
        cout << 1 << endl;
        return;
    } else if (n == 2) {
        cout << v[1] - v[0] << endl;
        return;
    }
    multiset<int> res;
    for (int i = 1; i < n; i++) {
        res.insert(v[i] - v[i - 1]);
    }
    int mn = 0;
    for (int i = 0; i < n - 1; i++) {
        int x = v[i + 1] - v[i];
        int mid = (v[i] + v[i + 1]) / 2;
        res.erase(res.find(x));
        res.insert(mid - v[i]);
        res.insert(v[i + 1] - mid);
        auto it = res.rbegin();
        int gp = *it;
        it++;
        int sc = (it != res.rend()) ? *it : gp;
        mn = max(mn, sc);
        res.erase(res.find(mid - v[i]));
        res.erase(res.find(v[i + 1] - mid));
        res.insert(x);
    }
    for (int i = 0; i < n - 1; i++) {
        int x = v[i + 1] - v[i];
        int mid = (v[i] + v[i + 1] + 1) / 2;
        res.erase(res.find(x));
        res.insert(mid - v[i]);
        res.insert(v[i + 1] - mid);
        auto it = res.rbegin();
        int gp = *it;
        it++;
        int sc = (it != res.rend()) ? *it : gp;
        mn = max(mn, sc);
        res.erase(res.find(mid - v[i]));
        res.erase(res.find(v[i + 1] - mid));
        res.insert(x);
    }
    cout << mn << endl;
}

I can't find any exceptional cases. Can someone help me? Thanks in advance for your assistance.