Binary Search on the Answer, Two Pointers and Sweeping

#include <algorithm>
#include <cstdint>
#include <print>
#include <ranges>
#include <vector>

struct Lcg {
    std::uint64_t s;
    std::uint32_t next() {
        s = s * 6364136223846793005ULL + 1442695040888963407ULL;
        return std::uint32_t(s >> 33);
    }
    int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};

long long probes = 0;

// Smallest i in [lo, hi) with pred(i) true, or hi if there is none.
// Requires pred to be false...false true...true on [lo, hi).
// Invariant: pred is false below lo and true from hi on.
template <class Pred>
int firstTrue(int lo, int hi, Pred pred) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;  // lo <= mid < hi, never overflows
        ++probes;
        if (pred(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

int main() {
    std::vector<int> a{2, 3, 3, 3, 7, 9};
    auto lb = std::ranges::lower_bound(a, 3) - a.begin();   // first a[i] >= 3
    auto ub = std::ranges::upper_bound(a, 3) - a.begin();   // first a[i] > 3
    auto pp = std::ranges::partition_point(a, [](int x) { return x < 5; }) - a.begin();
    std::println("lower_bound(3) = {}, upper_bound(3) = {}, count = {}", lb, ub, ub - lb);
    std::println("lower_bound(8) = {}, lower_bound(10) = {}",
                 std::ranges::lower_bound(a, 8) - a.begin(),
                 std::ranges::lower_bound(a, 10) - a.begin());
    std::println("first x >= 5: index {}", pp);

    Lcg rng{8};
    int checked = 0;
    for (; checked < 5000; ++checked) {
        std::vector<int> v(rng.range(0, 8));  // empty arrays included
        for (int& x : v) x = rng.range(0, 4);  // small values: many duplicates
        std::ranges::sort(v);
        int x = rng.range(-1, 5);  // below, inside and above the values
        int fast = firstTrue(0, int(v.size()), [&](int i) { return v[i] >= x; });
        int slow = 0;
        while (slow < int(v.size()) && v[slow] < x) ++slow;
        int library = int(std::ranges::lower_bound(v, x) - v.begin());
        if (fast != slow || library != slow) {
            std::println("mismatch at case {}", checked);
            return 1;
        }
    }
    std::println("{} random cases, all agree", checked);

    for (int n : {1'000, 1'000'000, 1'000'000'000}) {
        probes = 0;
        firstTrue(0, n, [&](int i) { return i >= n / 3; });
        std::println("n = {:>13}: {} probes", n, probes);
    }
}

#include <cstdint>
#include <numeric>
#include <print>

// Largest x in [lo, hi] with ok(x) true; ok must be true...true false...false
// and ok(lo) must be true. Gives up after 100 rounds so the bug is visible.
template <class Pred>
void lastTrue(const char* name, long long lo, long long hi, Pred ok, bool roundUp) {
    for (int round = 1; round <= 100; ++round) {
        if (lo == hi) {
            std::println("{}: answer {} after {} rounds", name, lo, round - 1);
            return;
        }
        long long mid = roundUp ? lo + (hi - lo + 1) / 2 : lo + (hi - lo) / 2;
        if (ok(mid)) lo = mid;  // mid is a candidate, keep it
        else hi = mid - 1;
    }
    std::println("{}: still at lo = {}, hi = {} after 100 rounds", name, lo, hi);
}

int main() {
    auto squareFits = [](long long x) { return x * x <= 30; };  // answer: 5
    lastTrue("mid rounds down", 0, 30, squareFits, false);
    lastTrue("mid rounds up  ", 0, 30, squareFits, true);

    // Midpoint overflow, shown with 32-bit unsigned values where wrapping is defined.
    // With signed int the same sum is undefined behavior, which is worse.
    std::uint32_t lo = 3'000'000'000, hi = 4'000'000'000;
    std::uint32_t naive = (lo + hi) / 2;
    std::uint32_t safe = lo + (hi - lo) / 2;
    std::println("(lo + hi) / 2      = {}", naive);
    std::println("lo + (hi - lo) / 2 = {}", safe);
    std::println("std::midpoint      = {}", std::midpoint(lo, hi));
}

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <print>
#include <sstream>
#include <vector>

using ll = long long;

struct Lcg {
    std::uint64_t s;
    std::uint32_t next() {
        s = s * 6364136223846793005ULL + 1442695040888963407ULL;
        return std::uint32_t(s >> 33);
    }
    int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};

int predicateCalls = 0;

// Can a car with range r get from 0 to len with at most k recharging stops?
// stops: sorted positions strictly between 0 and len. Greedy: drive as far as you can.
bool canFinish(const std::vector<ll>& stops, ll len, int k, ll r) {
    ++predicateCalls;
    ll pos = 0;  // where the battery was last full
    ll prev = 0;  // last station passed
    int used = 0;
    for (ll s : stops) {
        if (s - prev > r) return false;  // a gap no charge can bridge
        if (s - pos > r) pos = prev, ++used;  // must have charged at prev
        prev = s;
    }
    if (len - prev > r) return false;
    if (len - pos > r) ++used;
    return used <= k;
}

ll minRange(const std::vector<ll>& stops, ll len, int k) {
    ll lo = 1, hi = len;  // range len always works; the answer lies in [lo, hi]
    while (lo < hi) {
        ll mid = lo + (hi - lo) / 2;
        if (canFinish(stops, len, k, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

// Brute force: try every r upwards, each checked by a DP over stations.
ll slowRange(const std::vector<ll>& stops, ll len, int k) {
    std::vector<ll> p{0};
    p.insert(p.end(), stops.begin(), stops.end());
    p.push_back(len);
    int m = int(p.size());
    for (ll r = 1;; ++r) {
        std::vector<int> fewest(m, 1 << 20);  // fewest stops to arrive at p[i]
        fewest[0] = 0;
        for (int i = 1; i < m; ++i)
            for (int j = 0; j < i; ++j)
                if (p[i] - p[j] <= r)  // a stop at p[j] counts unless j is the start
                    fewest[i] = std::min(fewest[i], fewest[j] + (j > 0));
        if (fewest[m - 1] <= k) return r;
    }
}

void solve(std::istream& in, std::ostream& out) {
    int n, k;
    ll len;
    in >> n >> k >> len;
    std::vector<ll> stops(n);
    for (ll& s : stops) in >> s;
    out << minRange(stops, len, k) << '\n';
}

int main() {
    std::istringstream in("6 2 100\n15 30 42 60 71 88\n");
    solve(in, std::cout);  // on a judge: solve(std::cin, std::cout)

    Lcg rng{3};
    int checked = 0;
    for (; checked < 3000; ++checked) {
        ll len = rng.range(1, 40);
        std::vector<ll> stops;
        for (ll x = 1; x < len; ++x)
            if (rng.range(0, 3) == 0) stops.push_back(x);  // sometimes none at all
        int k = rng.range(0, 4);
        if (minRange(stops, len, k) != slowRange(stops, len, k)) {
            std::println("mismatch at case {}", checked);
            return 1;
        }
    }
    std::println("{} random cases, all agree", checked);

    predicateCalls = 0;
    std::vector<ll> far{400'000'000, 900'000'000};
    std::println("len 10^9: range {} after {} predicate calls",
                 minRange(far, 1'000'000'000, 1), predicateCalls);
}

#include <algorithm>
#include <cstdlib>
#include <functional>
#include <print>
#include <vector>

// Water poured over columns of width 1 settles at one level h with
// sum of max(0, h - height[i]) equal to the volume. Find h.
double waterLevel(const std::vector<double>& height, double volume) {
    auto stored = [&](double h) {
        double sum = 0;
        for (double x : height) sum += std::max(0.0, h - x);
        return sum;
    };
    double lo = std::ranges::min(height), hi = std::ranges::max(height) + volume;
    for (int it = 0; it < 100; ++it) {  // a fixed count: no epsilon to choose
        double mid = (lo + hi) / 2;
        if (stored(mid) >= volume) hi = mid;
        else lo = mid;
    }
    return hi;
}

int evaluations = 0;

// Smallest value of f on [lo, hi] for f that falls, then rises (no flat steps).
using Fn = std::function<long long(long long)>;
long long ternaryMin(long long lo, long long hi, const Fn& f) {
    while (hi - lo > 2) {
        long long m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3;
        evaluations += 2;
        if (f(m1) < f(m2)) hi = m2 - 1;  // the minimum is not right of m2
        else lo = m1 + 1;                // the minimum is not left of m1
    }
    long long best = f(lo);
    for (long long x = lo + 1; x <= hi; ++x) best = std::min(best, f(x));
    return best;
}

int main() {
    std::println("level for 10 units: {:.6f}", waterLevel({3, 1, 4, 1, 5, 9, 2, 6}, 10));
    std::println("level for 1 unit:   {:.6f}", waterLevel({3, 1, 4, 1, 5, 9, 2, 6}, 1));

    // Total walking distance to a meeting point x: convex in x.
    std::vector<long long> homes{12, 40, 41, 77, 300, 999'983};
    auto walk = [&](long long x) {
        long long sum = 0;
        for (long long p : homes) sum += std::llabs(x - p) * (1 + p % 3);
        return sum;
    };
    long long brute = walk(0);
    for (long long x = 1; x <= 1'000'000; ++x) brute = std::min(brute, walk(x));
    std::println("ternary {} vs brute {}, {} evaluations instead of 1000001",
                 ternaryMin(0, 1'000'000, walk), brute, evaluations);

    // A flat step breaks it: f(m1) == f(m2) cannot tell which side to drop.
    auto flat = [](long long x) { return std::min(std::llabs(x - 100), 100LL); };
    std::println("flat part: ternary {}, true minimum 0", ternaryMin(0, 1000, flat));
}

#include <algorithm>
#include <cstdint>
#include <print>
#include <vector>

using ll = long long;

struct Lcg {
    std::uint64_t s;
    std::uint32_t next() {
        s = s * 6364136223846793005ULL + 1442695040888963407ULL;
        return std::uint32_t(s >> 33);
    }
    int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};

struct Windows { int longest; ll count; };  // windows a[l..r] with sum <= budget
long long pointerMoves = 0;

Windows twoPointers(const std::vector<ll>& a, ll budget) {
    Windows w{0, 0};
    ll sum = 0;
    int l = 0;
    for (int r = 0; r < int(a.size()); ++r) {
        sum += a[r];
        ++pointerMoves;
        while (l <= r && sum > budget) sum -= a[l++], ++pointerMoves;  // shrink
        w.longest = std::max(w.longest, r - l + 1);
        w.count += r - l + 1;  // every l' in [l, r] gives a valid window ending at r
    }
    return w;
}

Windows bruteForce(const std::vector<ll>& a, ll budget) {
    Windows w{0, 0};
    for (int l = 0; l < int(a.size()); ++l) {
        ll sum = 0;
        for (int r = l; r < int(a.size()); ++r) {
            sum += a[r];
            if (sum <= budget) w.longest = std::max(w.longest, r - l + 1), ++w.count;
        }
    }
    return w;
}

void stress(const char* name, int minValue) {
    Lcg rng{21};
    for (int test = 0; test < 3000; ++test) {
        std::vector<ll> a(rng.range(0, 10));
        for (ll& x : a) x = rng.range(minValue, 9);
        ll budget = rng.range(0, 20);
        auto differ = [&](const std::vector<ll>& v) {
            auto [l1, c1] = twoPointers(v, budget);
            auto [l2, c2] = bruteForce(v, budget);
            return l1 != l2 || c1 != c2;
        };
        if (differ(a)) {
            for (std::size_t i = 0; i < a.size();) {  // shrink, as in lesson 2
                std::vector<ll> smaller = a;
                smaller.erase(smaller.begin() + i);
                if (differ(smaller)) a = smaller; else ++i;
            }
            auto [l1, c1] = twoPointers(a, budget);
            auto [l2, c2] = bruteForce(a, budget);
            std::print("{}: test {} fails on", name, test);
            for (ll x : a) std::print(" {}", x);
            std::println(" with budget {}: got ({}, {}), want ({}, {})",
                         budget, l1, c1, l2, c2);
            return;
        }
    }
    std::println("{}: 3000 tests, all agree", name);
}

int main() {
    auto [longest, count] = twoPointers({4, 2, 0, 7, 1, 1, 3, 8}, 7);
    std::println("budget 7: longest {}, windows {}", longest, count);
    stress("values 0..9 ", 0);
    stress("values -5..9", -5);

    for (int n : {1'000, 10'000, 100'000}) {
        pointerMoves = 0;
        twoPointers(std::vector<ll>(n, 1), 50);
        std::println("n = {:>6}: {} pointer moves", n, pointerMoves);
    }
}