Ternary Search

Hàm lồi và tam phân

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 là đơn đỉnh. Nếu có đoạn nằm ngang ở đáy thì cũng không sao, vì 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 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.

Trong hình, dải xanh là đoạn còn lại, chấm đỏ là điểm thấp hơn trong hai điểm chia ba. Kéo vị trí đáy để thử.

Trên số thực, đừ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. Hãy 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.

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)$.

ld f(ld p) {
    ld 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++) {
    ld 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;
#define ll long long
#define ld long double

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

ld f(ld p) {
    ld 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];
    ld l = 1, r = 1e9;
    for (ll it = 0; it < 200; it++) {
        ld 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';
}

ChạyInput3
1 11 21
1 2 1

Output10.000000000000000

Ước lượng phép tính: $200 \cdot 2 \cdot n = 2{,}4 \cdot 10^7$ phép. Hai chỗ có thể bớt: kiểu số và số vòng.

long double chậm hơn double khoảng 3 lần, và 100 vòng cho cùng đáp án như 200 vòng nhưng nhanh gấp đôi. Quy tắc: double với 100 vòng là đủ cho đa số bài; long double chỉ khi đề đòi nhiều chữ số hay tọa độ rất lớn.

Hàm tính bằng thuật toán

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.

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

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

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

ld f(ld x) {
    ld hi = 0, lo = 0, best = 0;
    for (ll i = 1; i <= n; i++) {
        ld b = a[i] - x;
        hi = max(hi, (ld)0) + b;
        lo = min(lo, (ld)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];
    ld l = -1e4, r = 1e4;
    for (ll it = 0; it < 150; it++) {
        ld 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';
}

ChạyInput2
0 2

Output1.000000000000000

Độ phức tạp: 150 vòng, mỗi vòng hai lần $O(n)$.

Miền nguyên

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 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 khỏi phải xử lý “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ề 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;
#define 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';
}

ChạyInput3 2
1 4 9
5 8

Output8

Độ phức tạp: $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.

ld f(ll k) {
    return (ld)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;
#define ll long long
#define ld long double

ll A, B;

ld f(ll k) {
    return (ld)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';
}

ChạyInput20 1

Output12.9442719100

Độ phức tạp: $O(\log 10^{12})$.

Tam phân lồng

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.

ld f(ld x, ld y) {
    ld 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)$.

ld g(ld x) {
    ld l = 0, r = 1000;
    for (ll it = 0; it < 120; it++) {
        ld 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;
#define ll long long
#define ld long double

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

ld f(ld x, ld y) {
    ld 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;
}

ld g(ld x) {
    ld l = 0, r = 1000;
    for (ll it = 0; it < 120; it++) {
        ld 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];
    ld l = 0, r = 1000;
    for (ll it = 0; it < 120; it++) {
        ld 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';
}

ChạyInput4
0 0
0 2
2 0
2 2

Output1.414213562373095

Ước lượng phép tính: $120 \cdot 2 \cdot 120 \cdot 2 \cdot n \approx 2{,}9 \cdot 10^6$ phép.