Ternary Search

Hàm lồi và tam phân trên số thực

Hàm $f$ trên đoạn $[l, r]$ là đơn đỉnh (theo cực tiểu) nếu có $p$ để $f$ giảm ngặt trên $[l, p]$ và tăng ngặt trên $[p, r]$. Lấy $m_1 < m_2$ trong đoạn: nếu $f(m_1) < f(m_2)$ thì đáy không thể nằm bên phải $m_2$, bỏ $(m_2, r]$; ngược lại bỏ $[l, m_1)$. Mỗi vòng đoạn còn $2/3$.

Hàm lồi đơn đỉnh trừ khi có đoạn nằm ngang ở đáy, và đoạn ngang ở đáy không làm sai kết quả (mọi điểm ở đó đều là cực tiểu). Các phép giữ tính lồi hay gặp:

• $|x - a|$, $(x - a)^2$, $c \cdot x$ là lồi; tổng các hàm lồi là lồi.
• $\max$ của các hàm lồi là lồi: thời gian chờ người chậm nhất, khoảng cách tới điểm xa nhất.
• Hàm lồi theo mỗi biến khi cố định biến kia chưa đủ cho tam phân lồng; cần lồi theo cả hai biến cùng lúc, như $\max$ khoảng cách Euclid.

Hàm đơn đỉnh nhưng có đoạn ngang không ở đáy (ví dụ hàm bậc thang) làm tam phân hỏng: $f(m_1) = f(m_2)$ không cho biết đáy ở phía nào.

Trên số thực, không dừng theo sai số $r - l < \varepsilon$: với tọa độ lớn, $\varepsilon$ nhỏ có thể không bao giờ đạt được do làm tròn, vòng lặp chạy mãi. Chạy số vòng cố định: sau $k$ vòng đoạn dài $(r - l)(2/3)^k$, 100 vòng đã nhỏ hơn $10^{-17}$ lần độ dài ban đầu. Khi đề yêu cầu in nhiều chữ số hoặc giá trị lớn, dùng long double.

Ví dụĐiểm Hẹn Nhanh Nhất

Đề. $n \le 6 \cdot 10^4$ người trên trục số, người $i$ ở $x_i$ đi với vận tốc tối đa $v_i$ (tới $10^9$). Chọn điểm hẹn thực $p$ để thời gian người tới cuối cùng, $\max_i |x_i - p| / v_i$, nhỏ nhất.

Lời giải. Mỗi $|x_i - p|/v_i$ lồi theo $p$, nên cực đại của chúng cũng lồi: tam phân trên $[1, 10^9]$.

Bước 1: hàm cần cực tiểu. Thời gian của người tới cuối cùng khi hẹn ở $p$, $O(n)$.

long double f(long double p) {
    long double t = 0;
    for (ll i = 1; i <= n; i++) t = max(t, fabsl(x[i] - p) / v[i]);
    return t;
}

Bước 2: tam phân. Chia $[l, r]$ làm ba. Nếu f(m1) < f(m2) thì cực tiểu không thể nằm bên phải m2 (hàm lồi đã bắt đầu tăng), bỏ $(m2, r]$; ngược lại bỏ $[l, m1)$. Mỗi vòng giữ lại $2/3$ khoảng; 200 vòng thu từ $10^9$ về cỡ $10^{-26}$, dư cho độ chính xác của long double.

for (ll it = 0; it < 200; it++) {
    long double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
    if (f(m1) < f(m2)) r = m2;
    else l = m1;
}

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

const ll N = 6e4 + 5;
ll n, x[N], v[N];

long double f(long double p) {
    long double t = 0;
    for (ll i = 1; i <= n; i++) t = max(t, fabsl(x[i] - p) / v[i]);
    return t;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> x[i];
    for (ll i = 1; i <= n; i++) cin >> v[i];
    long double l = 1, r = 1e9;
    for (ll it = 0; it < 200; it++) {
        long double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
        if (f(m1) < f(m2)) r = m2;
        else l = m1;
    }
    cout << fixed << setprecision(15) << f((l + r) / 2) << '\n';
}

Input3
1 11 21
1 2 1

Output10.000000000000000

$200 \cdot 2 \cdot n = 2{,}4 \cdot 10^7$ phép.

Hàm mục tiêu tính bằng thuật toán khác

Nhiều khi $f(x)$ không có công thức mà phải tính bằng cả một thuật toán: tham lam, Kadane, DP, đường đi ngắn nhất với tham số $x$. Tam phân vẫn dùng được miễn chứng minh được $f$ lồi, thường bằng cách viết $f$ là cực đại (hoặc tổng) của rất nhiều hàm lồi đơn giản, mỗi hàm ứng với một lựa chọn rời rạc. Độ phức tạp là số vòng nhân chi phí một lần tính $f$, nên $f$ phải chạy nhanh.

Ví dụĐộ Lệch Đoạn Liên Tiếp

Đề. Dãy $n \le 2 \cdot 10^5$ số trong $[-10^4, 10^4]$. Chọn số thực $x$, trừ $x$ khỏi mọi phần tử; độ lệch là trị tuyệt đối lớn nhất của tổng một đoạn con. Tìm độ lệch nhỏ nhất.

Lời giải. Với mỗi đoạn cố định, $|\text{tổng} - x \cdot len|$ lồi theo $x$; cực đại trên mọi đoạn vẫn lồi. Tam phân trên $[-10^4, 10^4]$ như ví dụ trước, chỉ khác cách tính $f$.

Bước 1: $f(x)$ bằng Kadane hai chiều. Trên dãy $a_i - x$: hi là tổng lớn nhất của đoạn kết thúc tại $i$, lo là nhỏ nhất. max(hi, 0) + b bỏ phần trước nếu nó âm, như Kadane thường; lo đối xứng. best là trị tuyệt đối lớn nhất của tổng một đoạn con.

long double f(long double x) {
    long double hi = 0, lo = 0, best = 0;
    for (ll i = 1; i <= n; i++) {
        long double b = a[i] - x;
        hi = max(hi, (long double)0) + b;
        lo = min(lo, (long double)0) + b;
        best = max(best, max(hi, -lo));
    }
    return best;
}

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

const ll N = 2e5 + 5;
ll n, a[N];

long double f(long double x) {
    long double hi = 0, lo = 0, best = 0;
    for (ll i = 1; i <= n; i++) {
        long double b = a[i] - x;
        hi = max(hi, (long double)0) + b;
        lo = min(lo, (long double)0) + b;
        best = max(best, max(hi, -lo));
    }
    return best;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    long double l = -1e4, r = 1e4;
    for (ll it = 0; it < 150; it++) {
        long double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
        if (f(m1) < f(m2)) r = m2;
        else l = m1;
    }
    cout << fixed << setprecision(15) << f((l + r) / 2) << '\n';
}

Input2
0 2

Output1.000000000000000

150 vòng, mỗi vòng hai lần $O(n)$.

Miền nguyên: chặt nhị phân trên hiệu kề

Trên số nguyên, $f$ lồi khi và chỉ khi hiệu $d(k) = f(k + 1) - f(k)$ không giảm. Cực tiểu là $k$ nhỏ nhất có $d(k) \ge 0$, tìm bằng mẫu chặt nhị phân l, r, res quen thuộc, mỗi bước tính $f$ hai lần. Cách này tránh hẳn các chi tiết “dừng khi còn ba phần tử rồi vét” của tam phân nguyên.

Với hàm có giá trị thực (như $A/\sqrt{k+1}$), hiệu kề tính bằng long double có thể sai dấu ở gần đáy, nơi hai giá trị gần như bằng nhau; khi đó $f$ tại điểm tìm được vẫn đủ gần cực tiểu theo sai số đề cho.

Ví dụNgưỡng Điều Chỉnh Chung

Đề. Hai dãy $a$ (dài $n$) và $b$ (dài $m$), $n, m \le 10^5$, phần tử tới $10^9$. Mỗi thao tác tăng hay giảm một phần tử 1 đơn vị. Cần đạt $\min(a) \ge \max(b)$ với ít thao tác nhất.

Lời giải. Chọn ngưỡng $t$: kéo mọi $a_i < t$ lên $t$, đẩy mọi $b_j > t$ xuống $t$. Chi phí $f(t) = \sum \max(0, t - a_i) + \sum \max(0, b_j - t)$ là tổng các hàm lồi. Với hàm lồi trên số nguyên, hiệu kề $f(t + 1) - f(t)$ không giảm, nên chặt nhị phân trên hiệu kề thay cho tam phân.

Bước 1: chi phí một ngưỡng. $O(n + m)$; chi phí tới $2 \cdot 10^5 \cdot 10^9$, dùng long long.

ll f(ll t) {
    ll s = 0;
    for (ll i = 1; i <= n; i++)
        if (a[i] < t) s += t - a[i];
    for (ll j = 1; j <= m; j++)
        if (b[j] > t) s += b[j] - t;
    return s;
}

Bước 2: chặt hiệu kề. $t$ nhỏ nhất có f(t + 1) - f(t) >= 0: từ đó hàm không còn giảm, nên $t$ là cực tiểu.

while (l <= r) {
    ll mid = (l + r) / 2;
    if (f(mid + 1) - f(mid) >= 0) res = mid, r = mid - 1;
    else l = mid + 1;
}

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

const ll N = 1e5 + 5;
ll n, m, a[N], b[N];

ll f(ll t) {
    ll s = 0;
    for (ll i = 1; i <= n; i++)
        if (a[i] < t) s += t - a[i];
    for (ll j = 1; j <= m; j++)
        if (b[j] > t) s += b[j] - t;
    return s;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll j = 1; j <= m; j++) cin >> b[j];
    ll l = 1, r = 1e9, res = 1e9;
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (f(mid + 1) - f(mid) >= 0) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << f(res) << '\n';
}

Input3 2
1 4 9
5 8

Output8

$30$ bước chặt, mỗi bước $O(n + m)$.

Ví dụMột Lần Điều Chỉnh

Đề. Chọn số nguyên $k \ge 0$ để $kB + A/\sqrt{k + 1}$ nhỏ nhất, với $A, B \le 10^{18}$. In giá trị nhỏ nhất, sai số $10^{-6}$.

Lời giải. $Bk$ tuyến tính, $A/\sqrt{k+1}$ lồi, tổng lồi theo $k$. Đáy gần $(A/2B)^{2/3}$, không vượt $10^{12}$, nên chặt hiệu kề như ví dụ trước trên $[0, 2 \cdot 10^{12}]$, khoảng 41 bước.

Bước 1: tính bằng số thực. $kB$ tới $2 \cdot 10^{30}$ không vừa long long, và $A/\sqrt{k + 1}$ là số thực, nên dùng long double.

long double f(ll k) {
    return (long double)k * B + A / sqrtl(k + 1);
}

Gần đáy, hai giá trị kề nhau gần như bằng nhau và hiệu có thể sai dấu do làm tròn; điểm tìm được vẫn nằm sát cực tiểu, sai số giá trị nhỏ hơn nhiều so với $10^{-6}$.

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

ll A, B;

long double f(ll k) {
    return (long double)k * B + A / sqrtl(k + 1);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> A >> B;
    ll l = 0, r = 2e12, res = 2e12;
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (f(mid + 1) - f(mid) >= 0) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << fixed << setprecision(10) << f(res) << '\n';
}

Input20 1

Output12.9442719100

$O(\log 10^{12})$.

Tam phân lồng nhau

Hàm hai biến $f(x, y)$ lồi theo cả hai biến cùng lúc thì $g(x) = \min_y f(x, y)$ cũng lồi. Tam phân ngoài trên $x$, mỗi lần tính $g(x)$ bằng một tam phân trong trên $y$. Chi phí là tích số vòng hai tầng nhân chi phí một lần tính $f$, nên giữ số vòng vừa đủ.

Ví dụĐường Tròn Bao Nhỏ Nhất

Đề. $n \le 50$ điểm nguyên trong $[0, 1000]^2$. Tìm bán kính nhỏ nhất của đường tròn chứa mọi điểm.

Lời giải. Với tâm $(x, y)$, bán kính cần là khoảng cách tới điểm xa nhất, một hàm lồi hai biến. Tâm tối ưu nằm trong hình vuông chứa các điểm. Tam phân lồng: vòng ngoài theo $x$, vòng trong theo $y$.

Bước 1: hàm hai biến. Bình phương khoảng cách tới điểm xa nhất. Bình phương đạt cực tiểu cùng chỗ với khoảng cách và vẫn lồi theo từng biến, nên khỏi gọi sqrt trong vòng lặp.

long double f(long double x, long double y) {
    long double d = 0;
    for (ll i = 1; i <= n; i++) d = max(d, (x - px[i]) * (x - px[i]) + (y - py[i]) * (y - py[i]));
    return d;
}

Bước 2: tam phân trong. Với $x$ cố định, $g(x) = \min_y f(x, y)$.

long double g(long double x) {
    long double l = 0, r = 1000;
    for (ll it = 0; it < 120; it++) {
        long double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
        if (f(x, m1) < f(x, m2)) r = m2;
        else l = m1;
    }
    return f(x, (l + r) / 2);
}

Bước 3: tam phân ngoài trên $x$ dùng g. $g$ lồi vì $f$ lồi theo cả hai biến cùng lúc. Cuối cùng lấy căn để ra bán kính.

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

ll n, px[55], py[55];

long double f(long double x, long double y) {
    long double d = 0;
    for (ll i = 1; i <= n; i++) d = max(d, (x - px[i]) * (x - px[i]) + (y - py[i]) * (y - py[i]));
    return d;
}

long double g(long double x) {
    long double l = 0, r = 1000;
    for (ll it = 0; it < 120; it++) {
        long double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
        if (f(x, m1) < f(x, m2)) r = m2;
        else l = m1;
    }
    return f(x, (l + r) / 2);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> px[i] >> py[i];
    long double l = 0, r = 1000;
    for (ll it = 0; it < 120; it++) {
        long double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
        if (g(m1) < g(m2)) r = m2;
        else l = m1;
    }
    cout << fixed << setprecision(15) << sqrtl(g((l + r) / 2)) << '\n';
}

Input4
0 0
0 2
2 0
2 2

Output1.414213562373095

$120 \cdot 2 \cdot 120 \cdot 2 \cdot n \approx 2{,}9 \cdot 10^6$ phép.