Brute Force

Khi nào đủ nhanh

Mọi lời giải vét cạn có hai phần. Không gian ứng viên là tập những thứ ta sẽ thử, chọn sao cho mỗi đáp án thật ứng với đúng một ứng viên (khi đề yêu cầu đếm) hoặc ít nhất một ứng viên (khi chỉ cần tối ưu). Phép kiểm nhìn một ứng viên và cho biết nó có hợp lệ không, giá trị bao nhiêu. Lời giải đúng khi trả lời được ba câu: ứng viên có phủ hết đáp án không, mỗi đáp án có bị đếm đúng một lần không, phép kiểm có chính xác không.

Phần còn lại là tốc độ. Máy chấm làm được cỡ $10^8$ phép đơn giản mỗi giây: cộng, so sánh, đọc ghi các ô liền nhau của mảng. Phép chia, map, truy cập mảng lớn lộn xộn đều chậm hơn nhiều lần. Quy tắc thực dụng là

và chỉ cỡ vài $10^7$ nếu phép kiểm nặng. Các mốc quen thuộc:

Bảng chỉ là mốc thô; luôn thay số của chính đề, và đừng quên chi phí kiểm. Duyệt $2^{20}$ tập con chỉ là $10^6$ ứng viên, nhưng nếu mỗi tập phải cộng lại $20$ phần tử thì thành $2 \cdot 10^7$ phép, và với $n = 25$ là $2^{25} \cdot 25 \approx 8 \cdot 10^8$, hết ngân sách.

Để nói gọn, ta chỉ giữ phần tăng nhanh nhất theo $n$ và bỏ hằng số nhân: duyệt mọi cặp tốn $\frac{n(n-1)}{2}$ phép, viết là $O(n^2)$, đọc là “bậc $n^2$”; duyệt mọi tập con rồi cộng lại tốn $O(n \cdot 2^n)$; một việc chỉ tốn vài phép, không phụ thuộc $n$, viết là $O(1)$. Ký hiệu này gọi là độ phức tạp thời gian, và từ đây mỗi lời giải đều kèm một câu như vậy.

Ví dụĐiểm Hẹn Ít Mệt Nhất

Đề. $N \le 100$ người ở các vị trí nguyên $X_i \le 100$. Chọn điểm hẹn nguyên $P$ để tổng $(X_i - P)^2$ nhỏ nhất, in tổng đó.

Lời giải. Ứng viên là điểm hẹn $P$. Điểm hẹn ngoài đoạn $[1, 100]$ không bao giờ tốt hơn điểm biên gần nó, vì kéo $P$ về phía mọi người làm mọi khoảng cách nhỏ đi, nên chỉ cần thử $P = 1..100$. Phép kiểm cộng $N$ bình phương. Cả bài $100 \cdot 100 = 10^4$ phép, không cần nghĩ thêm công thức nào.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, x[105];

signed main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> x[i];
    ll ans = 1e18;
    for (ll p = 1; p <= 100; p++) {
        ll cost = 0;
        for (ll i = 1; i <= n; i++) cost += (x[i] - p) * (x[i] - p);
        ans = min(ans, cost);
    }
    cout << ans << '\n';
}

ChạyInput3
1 4 7

Output18

Cặp và bộ ba

Ứng viên đơn giản nhất là một cặp hay một bộ ba, duyệt bằng các vòng for lồng nhau. Đếm các cặp chỉ số $i < j$ có $a_i + a_j = k$:

for (ll i = 1; i <= n; i++)
    for (ll j = i + 1; j <= n; j++)
        if (a[i] + a[j] == k) cnt++;

Điểm đáng nói là cận j = i + 1. Cho $j$ chạy từ đầu thì mỗi cặp bị gặp hai lần dưới dạng $(i, j)$ và $(j, i)$, lại thêm các cặp $i = j$. Cận $j > i$ liệt kê đúng một lần mỗi cặp không thứ tự, tức $\frac{n(n-1)}{2}$ cặp. Nếu đề hỏi cặp có thứ tự thì cho cả hai vòng chạy đủ rồi bỏ $i = j$. Đọc kỹ xem $(i, j)$ và $(j, i)$ là một hay hai, đây là lỗi hay gặp nhất ở bài đếm cặp.

Cận đúng không chỉ tránh đếm trùng mà còn nhanh hơn thấy rõ, dù hai cách cùng là $O(n^2)$:

Vòng lặp đủ làm gấp đôi số cặp và thêm một phép so sánh i != j mỗi bước, nên chậm hơn khoảng gấp đôi. Bớt được nửa số ứng viên là bớt được nửa thời gian.

Khi các biến ràng buộc nhau bằng một đẳng thức, có cách khéo hơn lồng thêm vòng. Đếm bộ $(a, b, c)$ nguyên dương với $a \le b \le c \le N$ và $a^2 + b^2 = c^2$: ba vòng lặp có cỡ $N^3/6$ ứng viên, nhưng khi đã chọn $a$, $b$ thì $c$ buộc phải bằng $\sqrt{a^2 + b^2}$. Ta chỉ duyệt $a$, $b$, suy ra $c$ rồi kiểm $c$ có nguyên và không vượt $N$ không. Quy tắc chung: số vòng lặp bằng số biến thật sự tự do; biến cuối tính từ các biến đã chọn, rồi kiểm đủ điều kiện của nó.

Ví dụBa Số Chạm Tổng

Đề. Cho $K \le 2500$ và $S \le 3K$. Đếm bộ ba có thứ tự $(x, y, z)$ với $0 \le x, y, z \le K$ và $x + y + z = S$.

Lời giải. Ba vòng lặp có $2501^3 \approx 1{,}6 \cdot 10^{10}$ ứng viên, quá chậm. Nhưng $z = S - x - y$ bị xác định khi đã chọn $x, y$: chỉ duyệt hai vòng, tính $z$, và đếm nếu $0 \le z \le K$. Còn $2501^2 \approx 6{,}3 \cdot 10^6$ phép. Bộ ba có thứ tự nên mọi cặp $(x, y)$ đều được xét, không cần cận $y \ge x$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll k, s, ans;

signed main() {
    cin >> k >> s;
    for (ll x = 0; x <= k; x++)
        for (ll y = 0; y <= k; y++) {
            ll z = s - x - y;
            if (z >= 0 && z <= k) ans++;
        }
    cout << ans << '\n';
}

ChạyInput2 2

Output6

Đoạn con

Một đoạn con liên tiếp là một cặp $(l, r)$ với $1 \le l \le r \le n$, có $\frac{n(n+1)}{2}$ đoạn. Nếu với mỗi đoạn ta cộng lại từ $l$ tới $r$, số phép cộng là tổng độ dài mọi đoạn, cỡ $n^3/6$; với $n = 3000$ đó là $4{,}5 \cdot 10^9$, vượt xa $10^8$.

Sự lãng phí lộ ra khi nhìn hai đoạn kề nhau: $[l, r-1]$ và $[l, r]$ chỉ khác đúng phần tử $a_r$, vậy mà ta cộng lại từ đầu. Giữ $l$ cố định, cho $r$ tăng dần và mang theo tổng chạy: tổng $[l, r]$ bằng tổng $[l, r-1]$ cộng $a_r$. Mỗi đoạn tốn $O(1)$, cả bài $\frac{n(n+1)}{2}$ phép.

Nguyên tắc này rộng hơn phép cộng: khi hai ứng viên kề nhau trong thứ tự duyệt chỉ khác nhau một chút, hãy cập nhật trạng thái thay vì dựng lại từ đầu. Trạng thái có thể là tổng, tọa độ, một bảng đếm chữ cái. Nếu trạng thái chỉ xấu đi khi đoạn dài thêm (ví dụ số chữ khác nhau vượt ngưỡng), còn được break khỏi vòng $r$.

Tập con: bitmask

Mỗi phần tử có hai lựa chọn, được chọn hoặc không, nên $n$ phần tử có $2^n$ tập con. Cách duyệt gọn nhất là đếm từ $0$ tới $2^n - 1$ rồi đọc mỗi số dưới dạng $n$ chữ số nhị phân: bit $i$ bằng 1 nghĩa là phần tử $i$ được chọn. Mỗi tập con ứng với đúng một số, gọi là mask. Mục này đánh số phần tử từ 0 để phần tử $i$ ứng với bit $i$ (chữ số nhị phân thứ $i$, đếm từ phải sang, bắt đầu từ 0).

Ba phép trên bit đủ cho mục này: 1 << n là $2^n$; mask >> i dịch các chữ số nhị phân của mask sang phải $i$ chỗ, đưa bit $i$ về hàng cuối; x & 1 giữ lại đúng chữ số cuối của x. Chẳng hạn $13 = 1101_2$: 13 >> 2 là $11_2 = 3$, rồi 3 & 1 bằng 1, nên bit 2 của 13 đang bật.

for (ll mask = 0; mask < (1 << n); mask++) {
    ll sum = 0;
    for (ll i = 0; i < n; i++)
        if (mask >> i & 1) sum += a[i];
    if (sum == s) ways++;
}

Có $2^n$ mask, mỗi mask cộng tối đa $n$ phần tử, tốn $O(n \cdot 2^n)$: với $n = 20$ là khoảng $2 \cdot 10^7$ phép. Biểu thức mask >> i & 1 đúng vì >> ưu tiên cao hơn &. Chỗ dễ sai là các cách viết gần giống: == ưu tiên cao hơn &, nên mask & (1 << i) == 1 được hiểu là mask & ((1 << i) == 1).

Khi $n$ gần giới hạn, phép kiểm tính từ đầu là phần đắt nhất. Tổng của mask suy ra được từ tổng của mask đã tắt bit 1 thấp nhất, mask đó nhỏ hơn nên đã tính xong. Trong dòng dưới, mask & (mask - 1) chính là mask đã tắt bit 1 thấp nhất, còn __builtin_ctz(mask) cho vị trí của bit đó:

for (ll mask = 1; mask < (1 << n); mask++) sum[mask] = sum[mask & (mask - 1)] + a[__builtin_ctz(mask)];

Mỗi mask còn $O(1)$, đổi lại $2^n$ ô nhớ. Với $n = 22$, khác biệt đo được:

Suy từ mask nhỏ hơn nhanh khoảng 10 lần, đúng bằng số phép cộng bớt được ở mỗi mask. Phép kiểm càng rẻ, $n$ càng đẩy lên được cao.

Vài biến thể: mỗi phần tử có ba lựa chọn thì có $3^n$ cấu hình, duyệt bằng số viết ở cơ số 3; muốn tập đúng $k$ phần tử thì lọc bằng __builtin_popcount(mask) == k (hàm đếm số bit 1); khi $20 < n \le 40$ thì chia đôi tập rồi ghép lại (bài 1.1).

Ví dụChia Táo Thành Hai Nhóm

Đề. $n \le 20$ quả táo nặng $p_i \le 10^9$. Chia hết táo thành hai nhóm (một nhóm có thể rỗng) sao cho chênh lệch tổng hai nhóm nhỏ nhất.

Lời giải. Mỗi cách chia ứng với tập các quả thuộc nhóm 1, tức một mask. Gọi $T$ là tổng mọi quả và $s$ là tổng nhóm 1 thì chênh lệch là $|T - 2s|$. Hai cách chia $(G_1, G_2)$ và $(G_2, G_1)$ cho cùng chênh lệch, nên ghim quả cuối vào nhóm 2 và chỉ duyệt mask của $n - 1$ quả đầu: $2^{19} \cdot 19 \approx 10^7$ phép. Tổng tới $2 \cdot 10^{10}$ nên dùng long long.

Tham lam “xếp quả nặng nhất còn lại vào nhóm đang nhẹ hơn” không đúng: với $5, 5, 4, 3, 3$ nó cho $9$ và $11$, trong khi $\{5, 5\}$ và $\{4, 3, 3\}$ cùng tổng $10$. Vét cạn không phụ thuộc vào cảm giác như vậy.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, p[25], tot;

signed main() {
    cin >> n;
    for (ll i = 0; i < n; i++) {
        cin >> p[i];
        tot += p[i];
    }
    ll ans = 1e18;
    for (ll mask = 0; mask < (1 << (n - 1)); mask++) {
        ll s = 0;
        for (ll i = 0; i < n - 1; i++)
            if (mask >> i & 1) s += p[i];
        ans = min(ans, abs(tot - 2 * s));
    }
    cout << ans << '\n';
}

ChạyInput5
3 2 7 4 1

Output1

Hoán vị

Khi ứng viên là một thứ tự (thứ tự thăm các thành phố, cách xếp $n$ người vào $n$ ghế) thì có $n!$ ứng viên, tăng nhanh hơn $2^n$ rất nhiều: $8! = 40\,320$, $10! \approx 3{,}6 \cdot 10^6$, $12! \approx 4{,}8 \cdot 10^8$. Vét cạn hoán vị chỉ dùng được khi $n \le 10$ hoặc $11$, và phép kiểm phải rẻ.

C++ có sẵn next_permutation(first, last): biến dãy thành hoán vị đứng ngay sau nó theo thứ tự từ điển và trả về true; nếu dãy đã giảm dần thì trả về false. Bắt đầu từ dãy tăng dần rồi gọi liên tục sẽ đi qua mọi hoán vị đúng một lần. Dãy có phần tử trùng thì hàm chỉ đi qua các hoán vị phân biệt.

Hàm làm ba việc: tìm vị trí $i$ lớn nhất có $a_i < a_{i+1}$ (điểm gãy), đổi $a_i$ với số nhỏ nhất lớn hơn nó trong phần đuôi, rồi đảo phần đuôi cho tăng dần. Đuôi sau điểm gãy giảm dần, tức đã là cách xếp lớn nhất của nó; muốn lớn hơn ít nhất thì phải tăng $a_i$ lên giá trị nhỏ nhất có thể rồi xếp phần còn lại nhỏ nhất có thể.

Hai quy tắc khi dùng: phải sắp tăng dần trước, vì hàm chỉ đi tiếp từ vị trí hiện tại; và viết do { ... } while (next_permutation(...)), vì vòng while đặt điều kiện trước sẽ bỏ qua hoán vị đầu tiên.

Ví dụHoán Vị Cột Số

Đề. $n \le 8$ xâu, mỗi xâu đúng $k \le 8$ chữ số. Chọn một hoán vị các vị trí và áp dụng cho mọi xâu, rồi đọc mỗi xâu như một số. Tìm hiệu nhỏ nhất giữa số lớn nhất và số nhỏ nhất.

Lời giải. Ứng viên là hoán vị của $k$ cột, có $8! = 40\,320$ cái. Với mỗi hoán vị, dựng lại $n$ số rồi lấy lớn nhất trừ nhỏ nhất: $n \cdot k = 64$ phép. Cả bài khoảng $2{,}6 \cdot 10^6$ phép. Số có tới 8 chữ số, vẫn vừa int, nhưng dùng ll cho chắc.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, k, p[10];
string s[10];

signed main() {
    cin >> n >> k;
    for (ll i = 0; i < n; i++) cin >> s[i];
    for (ll j = 0; j < k; j++) p[j] = j;
    ll ans = 1e18;
    do {
        ll lo = 1e18, hi = -1e18;
        for (ll i = 0; i < n; i++) {
            ll v = 0;
            for (ll j = 0; j < k; j++) v = v * 10 + s[i][p[j]] - '0';
            lo = min(lo, v);
            hi = max(hi, v);
        }
        ans = min(ans, hi - lo);
    } while (next_permutation(p, p + k));
    cout << ans << '\n';
}

ChạyInput2 2
01
10

Output9

Sinh ứng viên

Đôi khi ứng viên tốt nhất lại chính là đáp án. Có hai cách dùng.

Thử đáp án tăng dần. Tìm số nhỏ nhất $x \ge a$ có tổng chữ số chia hết cho 4: cho $x$ chạy từ $a$ lên tới khi thỏa. Cách này chỉ nhanh khi chứng minh được đáp án nằm sát $a$. Ở đây mười số cùng phần đầu, khác nhau ở chữ số cuối, có tổng chữ số là mười số nguyên liên tiếp, nên đáp án luôn cách $a$ không quá $6$ đơn vị. Cận này cũng có thể tìm ra bằng cách cho vét cạn chạy trên mọi $a$ nhỏ rồi lấy khoảng cách lớn nhất.

Sinh ứng viên thay vì lọc. Đếm các số không vượt $N \le 10^9$ chỉ gồm chữ số $4$ và $7$. Duyệt từng số $1..N$ rồi kiểm chữ số mất cỡ $10^{10}$ phép. Nhưng số như vậy rất ít: dưới $10^9$ chỉ có $2 + 4 + \dots + 2^9 = 1022$ số. Thay vì lọc cả miền giá trị, ta sinh trực tiếp: từ một số đã dựng, nối thêm chữ số $4$ hoặc $7$. Khi số vừa dựng đã vượt $N$ thì nối thêm chỉ làm nó lớn hơn, nên bỏ cả nhánh. Số ứng viên giờ bằng số đối tượng hợp lệ, không phải độ lớn của miền giá trị. Hàm tự gọi lại chính nó, đây là hình hài đầu tiên của quay lui (bài 0.8).

Mỗi nút trong hình dưới là một số đã dựng; nối thêm 4 hoặc 7 cho hai nút con.

Bớt ứng viên

Lời giải vét cạn đúng rồi mới tới chuyện nhanh. Có bốn cách bớt việc, phần lớn đã gặp ở trên:

• Cận chặt, break đúng chỗ. Cho $j$ bắt đầu từ $i + 1$, thoát vòng khi $a^2 + b^2 > N^2$. Mỗi break phải dựa trên một tính đơn điệu có thật; một break sai bỏ sót đáp án một cách lặng lẽ.
• Dừng sớm. Khi chỉ cần một đáp án, hay đáp án đầu tiên theo một thứ tự, duyệt theo thứ tự ấy và dừng ngay khi gặp.
• Gộp ứng viên đối xứng. Hai ứng viên luôn cho cùng kết quả thì chỉ duyệt một, như ghim một quả táo vào nhóm 2 để giảm từ $2^n$ xuống $2^{n-1}$.
• Phép kiểm rẻ. Kiểm “tổng hai số có nguyên tố không” bằng chia thử tốn cỡ $\sqrt{2 \cdot 10^6} \approx 1400$ phép; một sàng Eratosthenes (bài 0.9) dựng trước cho câu trả lời bằng một lần đọc mảng.

Còn một cách mạnh hơn, không có công thức chung: dùng một nhận xét toán học để chứng minh chỉ một phần nhỏ ứng viên có thể là đáp án, rồi chỉ duyệt phần đó.

Ví dụBa Số Có Tận Cùng Bằng 3

Đề. Mảng $n \le 2 \cdot 10^5$ số nguyên dương. Có chọn được ba phần tử ở ba vị trí khác nhau mà tổng có chữ số hàng đơn vị là $3$ không? Tổng $n$ qua các test không quá $2 \cdot 10^5$.

Lời giải. Duyệt bộ ba trên cả mảng là $n^3/6 \approx 10^{15}$, không thể. Nhận xét: chữ số cuối của tổng chỉ phụ thuộc chữ số cuối của từng số, và một bộ ba dùng mỗi chữ số cuối nhiều nhất ba lần. Vậy với mỗi chữ số cuối $0..9$ chỉ cần giữ lại tối đa ba phần tử, còn lại không quá $30$ số. Duyệt mọi bộ ba $i < j < k$ của $30$ số là $\frac{30 \cdot 29 \cdot 28}{6} = 4060$ phép mỗi test. Đây là vét cạn trên một không gian đã được thu hẹp có chứng minh.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll t, n, cnt[10], v[35], m;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        memset(cnt, 0, sizeof cnt);
        m = 0;
        for (ll i = 1; i <= n; i++) {
            ll x;
            cin >> x;
            if (cnt[x % 10] < 3) {
                cnt[x % 10]++;
                v[++m] = x % 10;
            }
        }
        bool ok = false;
        for (ll i = 1; i <= m; i++)
            for (ll j = i + 1; j <= m; j++)
                for (ll k = j + 1; k <= m; k++)
                    if ((v[i] + v[j] + v[k]) % 10 == 3) ok = true;
        cout << (ok ? "YES" : "NO") << '\n';
    }
}

ChạyInput3
5
10 21 32 44 55
4
10 20 40 80
3
1 1 1

OutputYES
NO
YES

Bộ kiểm

Lời giải nhanh thường tinh vi và dễ sai; vét cạn thì đơn giản tới mức khó sai. Hai chương trình cùng giải một đề phải cho cùng đáp án trên mọi đầu vào, nên chỉ cần một bộ sinh test nhỏ ngẫu nhiên và một phép so sánh:

1. Viết brute đơn giản nhất có thể.
2. Sinh test với $n$ và giá trị đều nhỏ, vì lỗi thường lộ ngay ở dữ liệu nhỏ: $n = 1$, số âm, số bằng nhau.
3. Chạy hàng nghìn test, dừng ở test đầu tiên hai bên khác nhau.
4. Đọc test ấy bằng mắt: nó nhỏ nên lỗi thường hiện ra ngay.

Vét cạn còn hai việc nữa. Một là lấy điểm: nhiều đề chia subtask, subtask đầu có giới hạn nhỏ chính là dành cho vét cạn. Hai là tìm quy luật: chạy brute trên nhiều đầu vào nhỏ rồi nhìn kết quả để đoán công thức hay một cận, như cận $6$ ở mục trước.

Thử với bài Đoạn Có Tổng Lớn Nhất: tìm tổng lớn nhất của một đoạn con liên tiếp không rỗng, $N \le 2 \cdot 10^5$. Vét cạn mọi đoạn là $O(N^2)$, quá chậm. Cách $O(N)$ duyệt dãy một lần: giữ cur là tổng lớn nhất của đoạn kết thúc tại vị trí hiện tại (cur trước đó âm thì bỏ, bắt đầu lại từ phần tử này), và ans là lớn nhất của các cur. Khởi tạo ans phải là $-\infty$ chứ không phải $0$, vì đoạn không được rỗng: dãy toàn số âm có đáp án âm.

Lỗi khởi tạo ans = 0 không lộ ra ở test mẫu, nhưng bộ kiểm tìm ra ngay. Chương trình dưới chạy brute (mọi đoạn) và fast (cách trên) trên 20000 dãy ngắn ngẫu nhiên, lần lượt với hai giá trị khởi tạo:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, a[10];

ll brute() {
    ll best = -1e18;
    for (ll l = 1; l <= n; l++) {
        ll sum = 0;
        for (ll r = l; r <= n; r++) {
            sum += a[r];
            best = max(best, sum);
        }
    }
    return best;
}

ll fast(ll init) {
    ll cur = 0, best = init;
    for (ll i = 1; i <= n; i++) {
        cur = max(cur, 0LL) + a[i];
        best = max(best, cur);
    }
    return best;
}

signed main() {
    mt19937 rng(2024);
    for (ll init : {0LL, (ll)-1e18}) {
        bool ok = true;
        for (ll t = 1; t <= 20000 && ok; t++) {
            n = rng() % 6 + 1;
            for (ll i = 1; i <= n; i++) a[i] = (ll)(rng() % 11) - 5;
            if (brute() != fast(init)) {
                cout << "ans = " << init << ": sai ở test " << t << ", dãy";
                for (ll i = 1; i <= n; i++) cout << ' ' << a[i];
                cout << ", đúng là " << brute() << ", in ra " << fast(init) << '\n';
                ok = false;
            }
        }
        if (ok) cout << "ans = " << init << ": 20000 test đều khớp\n";
    }
}

Outputans = 0: sai ở test 4, dãy -3, đúng là -3, in ra 0
ans = -1000000000000000000: 20000 test đều khớp

Phản ví dụ nhỏ hết mức: dãy một phần tử $-3$. Hạt giống 2024 cố định nên lần chạy nào cũng cho cùng dãy test, lỗi tái hiện được. Khi bài lớn hơn, người ta tách thành ba chương trình (sinh test, brute, fast) và một script so đầu ra, nhưng nguyên tắc vẫn như trên.