Wiki › Kỹ năng giải bài › Tối ưu hằng số (Constant Optimization)

Tối ưu hằng số (Constant Optimization)

Làm cùng một thuật toán chạy nhanh hơn vài lần: nhập xuất nhanh, truy cập bộ nhớ thân thiện với cache, tránh phép mod trong vòng lặp trong, bitset, pragma GCC và mẹo riêng cho Python, kèm số đo thật.

huunguyen huunguyen Updated Tháng 11. 17, 2026 Đọc 24 phút 2 lượt xem

Tối ưu hằng số (constant optimization) là làm cho cùng một thuật toán chạy nhanh hơn mà không đổi độ phức tạp: vẫn O(n3), vẫn O(nW), nhưng mỗi "bước" rẻ hơn. Ký hiệu O bỏ qua hằng số, máy chấm thì không. Hai lời giải cùng O(n3) có thể chênh nhau 4 lần chỉ vì thứ tự ba vòng for; đọc 107 số bằng cin mặc định có thể mất vài giây trong khi bộ đọc tự viết chỉ mất khoảng 0,1 giây. Trang này nói khi nào đáng làm, các kỹ thuật cho kết quả lớn nhất, và số đo thật cho từng kỹ thuật.

Khi nào đáng tối ưu hằng số?

Quy tắc số một: thuật toán đúng độ phức tạp trước, hằng số sau. Tối ưu hằng số chỉ giúp được vài lần (thường 2 đến 10 lần, bitset là 64 lần); nó không biến O(n2) với n=106 thành lời giải qua được.

Cách quyết định:

  1. Ước lượng số phép tính từ giới hạn đề bài (xem Ước lượng giới hạn bài toán và Độ phức tạp thời gian). Máy chấm hiện đại làm khoảng 108 đến 109 phép tính đơn giản mỗi giây, tùy loại phép tính.
  2. So với giới hạn thời gian:
Số phép tính ước lượng (1 giây) Kết luận
≤108 Thoải mái, chỉ cần nhập xuất nhanh nếu input lớn
108 đến 5·108 Qua được nếu vòng lặp trong đơn giản và truy cập bộ nhớ tuần tự
5·108 đến 3·109 Vùng của tối ưu hằng số: thứ tự vòng lặp, bỏ %, bitset, mảng phẳng
>3·109 (không dùng bitset được) Gần như chắc chắn cần thuật toán tốt hơn

flowchart TD A[Ước lượng số phép tính T] --> B{"T ≤ 1e8?"} B -- có --> C[Viết code bình thường, nhập xuất nhanh nếu input lớn] B -- không --> D{"T ≤ 3e9 hoặc dùng được bitset?"} D -- không --> E[Tìm thuật toán có độ phức tạp tốt hơn] D -- có --> F[Tối ưu hằng số: bộ nhớ, mod, bitset, I/O]

"Một phép tính" không có giá cố định. Trên máy hiện đại, xếp từ rẻ đến đắt: cộng, trừ, so sánh, phép bit (rẻ nhất) < nhân < truy cập bộ nhớ đã nằm trong cache < phép chia và % (đắt hơn nhân nhiều lần) < truy cập bộ nhớ không nằm trong cache (có thể chậm hơn cộng hàng trăm lần). Phần lớn kỹ thuật dưới đây là tránh hai thứ đắt cuối cùng.

Số đo thật trên máy của người viết

Mọi con số trên trang này là số đo trên máy của người viết: Apple M3 Pro, chạy trong container Linux aarch64 (ảnh máy chấm của CTOJ), g++ 16.2 -O2, Python 3.15.1, PyPy 7.3.23. Mỗi phép đo chạy 2 đến 5 lần, ghi khoảng giá trị điển hình. Máy chấm của bạn sẽ ra số khác; điều đáng tin là tỉ lệ giữa hai cách làm, không phải số mili giây tuyệt đối.

Thí nghiệm Cách chậm Cách nhanh Tăng tốc
Nhân ma trận double 1000×1000 thứ tự ijk: 770 đến 880 ms thứ tự ikj: 210 đến 245 ms ≈3,7 lần
Nhân ma trận mod 109+7, 500×500 % mỗi phép nhân: 87 đến 99 ms mod lười mỗi 16 số hạng: 47 đến 58 ms ≈1,8 lần
Tổng tập con n=2000, W=2·105 mảng char: 210 đến 285 ms bitset: 10 đến 11 ms ≈20 lần
Đọc 107 số (khoảng 99 MB) cin mặc định: 2200 đến 3500 ms fread tự viết: 96 đến 120 ms ≈25 lần
Đọc 107 số scanf: 590 đến 780 ms cin đã tắt đồng bộ: 340 đến 550 ms
In 2·106 dòng ra file endl: 980 đến 1000 ms '\n': 57 đến 60 ms ≈17 lần
106 vector nhỏ, lặp 10 lần vector<vector<int>>: 420 đến 585 ms một mảng phẳng: 7 đến 11 ms ≈50 lần
Python đọc 106 dòng input(): 540 đến 660 ms sys.stdin.buffer.read(): 69 đến 73 ms ≈8 lần
Python in 106 dòng print trong vòng lặp: 360 đến 390 ms "\n".join: 210 đến 240 ms ≈1,7 lần
Python vòng lặp 107 bước biến toàn cục: 1570 đến 1660 ms trong hàm main(): 690 ms ≈2,3 lần
Cùng vòng lặp đó CPython (trong hàm): 690 ms PyPy (trong hàm): 27 ms ≈25 lần

Riêng với cin chưa tắt đồng bộ, khác biệt giữa các hệ thống rất lớn: chạy trực tiếp trên macOS, đọc 107 số mất tới 71 giây (so với 0,55 giây khi đã tắt đồng bộ). Đừng bao giờ dựa vào việc "máy mình chạy nhanh".

Nhập xuất nhanh

Với input vài triệu số trở lên, nhập xuất thường chiếm phần lớn thời gian chạy. Đây là tối ưu rẻ nhất và nên luôn làm.

C++
int main() {
    ios_base::sync_with_stdio(false);  // stop syncing iostream with C stdio
    cin.tie(nullptr);                  // do not flush cout before every cin
    // ... dùng cin/cout như bình thường
}
  • sync_with_stdio(false): mặc định cin/cout phải giữ đồng bộ với scanf/printf (để trộn lẫn được), nên mỗi thao tác rất chậm. Tắt đi thì cin có bộ đệm riêng và nhanh ngang hoặc hơn scanf.
  • cin.tie(nullptr): mặc định trước mỗi lần đọc cin sẽ đẩy (flush) hết cout. Với bài đọc xen kẽ in thì đây là hàng triệu lần flush.
  • Dùng '\n' thay cho endl. endl = xuống dòng cộng flush, mỗi lần flush là một lời gọi hệ thống.

Khi input thật sự lớn (từ 107 số, hoặc đề ghi rõ "dùng cách đọc nhanh"), tự đọc theo khối bằng fread và tự tách số. Đây là chương trình đầy đủ: đọc n rồi n số nguyên (có thể âm), in tổng và giá trị lớn nhất.

C++
#include <bits/stdc++.h>
using namespace std;

// Fast reader: pull 64 KB blocks with fread, parse integers by hand.
static char buf[1 << 16];
static size_t buf_len = 0, buf_pos = 0;

inline int read_byte() {
    if (buf_pos == buf_len) {
        buf_len = fread(buf, 1, sizeof(buf), stdin);
        buf_pos = 0;
        if (buf_len == 0) return -1;  // end of input
    }
    return buf[buf_pos++];
}

inline long long read_int() {
    int c = read_byte();
    while (c != '-' && (c < '0' || c > '9')) c = read_byte();  // skip spaces, newlines
    bool neg = (c == '-');
    if (neg) c = read_byte();
    long long x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = read_byte();
    }
    return neg ? -x : x;
}

int main() {
    int n = read_int();
    long long total = 0, best = LLONG_MIN;
    for (int i = 0; i < n; i++) {
        long long x = read_int();
        total += x;
        best = max(best, x);
    }
    // Output is small here; for many lines build a string and print once.
    printf("%lld %lld\n", total, best);
}
Python
import sys

def main():
    data = sys.stdin.buffer.read().split()  # read everything once, split into tokens
    n = int(data[0])
    a = list(map(int, data[1:n + 1]))
    sys.stdout.write(f"{sum(a)} {max(a)}\n")

main()

Với input

5
3 -7 10
  -2
4

cả hai chương trình in 8 10. Bộ đọc bỏ qua mọi ký tự không phải chữ số hay dấu -, nên không quan tâm số nằm trên bao nhiêu dòng hay cách nhau bao nhiêu dấu cách.

Python
  • Đọc một lần toàn bộ input: data = sys.stdin.buffer.read().split(), rồi dùng chỉ số chạy trên data. Nhanh hơn input() khoảng 8 lần trên số đo ở trên; sys.stdin.readline nằm giữa (khoảng 145 ms cho 106 dòng).
  • Không gọi print trong vòng lặp lớn. Gom kết quả vào list rồi sys.stdout.write("\n".join(map(str, res)) + "\n").
  • sys.stdin.buffer trả về bytes, int(b"123") vẫn chạy; muốn so sánh với xâu thì phải viết b"YES" hoặc .decode().

Xem thêm Python cho lập trình thi đấu.

Bộ nhớ và cache

Vì sao thứ tự truy cập quan trọng?

CPU không đọc từng biến một từ RAM. Nó đọc cả một dòng cache (cache line) 64 byte, tức 8 số double hoặc 16 số int liền nhau, rồi giữ trong bộ nhớ đệm rất nhanh (cache). Đọc phần tử kế tiếp trong cùng dòng gần như miễn phí; nhảy tới chỗ xa phải chờ RAM, chậm hơn hàng trăm lần một phép cộng. Ngoài ra CPU còn đoán trước (prefetch): thấy bạn đọc tuần tự, nó tải sẵn các dòng tiếp theo.

Mảng hai chiều trong C++ được lưu theo hàng (row-major): a[i][0], a[i][1], ..., a[i][m-1] nằm liền nhau, rồi mới tới hàng i+1. Vậy duyệt theo hàng (chỉ số cuối thay đổi nhanh nhất) là tuần tự, duyệt theo cột là nhảy cách m phần tử mỗi bước.

Ví dụ chạy tay: nhân ma trận ijk và ikj

Cho C=A·B với ma trận 4×4. Trong bộ nhớ, B là 16 ô liền nhau: ô 1..4 là hàng 1, ô 5..8 là hàng 2, v.v.

Cách viết sách giáo khoa ijk tính Cij=∑kAikBkj, vòng trong cùng chạy theo k, nên đọc B1j,B2j,B3j,B4j: một cột của B. Cách ikj đổi chỗ hai vòng trong: cố định Aik, vòng trong cùng chạy theo j và cộng Aik·Bkj vào Cij, nên đọc Bk1,Bk2,Bk3,Bk4: một hàng.

array
B11 B12 B13 B14 B21 B22 B23 B24 B31 B32 B33 B34 B41 B42 B43 B44
step Ma trận B lưu theo hàng: 16 ô liền nhau trong bộ nhớ
step ijk, i = 1, j = 1: vòng k đọc B11, B21, B31, B41, mỗi bước nhảy 4 ô
highlight red 1 5 9 13
step ikj, i = 1, k = 1: vòng j đọc B11, B12, B13, B14, liền nhau
clear
highlight green 1..4

Với n=4 thì cả ma trận nằm vừa cache nên không thấy khác biệt. Với n=1000, mỗi hàng là 8000 byte: ở ijk, mỗi bước của vòng trong rơi vào một dòng cache khác, và 1000 dòng của một cột bị đẩy ra khỏi cache trước khi được dùng lại cho cột kế tiếp. Ở ikj, mỗi dòng cache tải về được dùng đủ 8 số, và trình biên dịch còn vector hóa được vòng trong (dùng lệnh SIMD cộng vài số một lúc) vì nó tuần tự và không có phụ thuộc giữa các bước.

Hai cách ra cùng kết quả và cùng n3 phép nhân. Số đo trên máy của người viết (n=1000, double, -O2):

Thứ tự Thời gian
ijk (đọc cột của B) 770 đến 880 ms
ikj (đọc hàng của B và C) 210 đến 245 ms
ijk (chậm)
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
        double s = 0;
        for (int k = 0; k < n; k++)
            s += A[i][k] * B[k][j];   // B is read down a column
        C[i][j] = s;
    }
ikj (nhanh)
// C must be zero-initialized
for (int i = 0; i < n; i++)
    for (int k = 0; k < n; k++) {
        double a = A[i][k];           // hoisted out of the inner loop
        for (int j = 0; j < n; j++)
            C[i][j] += a * B[k][j];   // B and C are read along a row
    }

Cùng ý đó áp dụng cho mọi vòng lặp lồng nhau trên mảng 2 chiều: Floyd-Warshall (vòng k ngoài cùng, rồi i, rồi j), quy hoạch động trên bảng, tổng tiền tố 2 chiều. Nếu bắt buộc phải đọc theo cột, có thể chuyển vị ma trận một lần (O(n2)) rồi đọc theo hàng.

Các mẹo bố trí bộ nhớ khác
  • Tránh vector<vector<T>> cho bảng lớn. Mỗi hàng là một vùng nhớ cấp phát riêng: tốn thêm một con trỏ và một lần cấp phát mỗi hàng, các hàng không liền nhau. Dùng mảng tĩnh static int dp[N][M] hoặc mảng phẳng vector<int> a(n * m) với a[i * m + j]. Số đo ở trên: tạo 106 vector nhỏ chậm hơn mảng phẳng khoảng 50 lần.
  • Danh sách kề dạng phẳng (CSR). Với đồ thị 106 đỉnh, thay vector<vector<int>> adj bằng hai mảng: start[u] và to[], cạnh của u nằm ở to[start[u] .. start[u+1]-1]. Dựng bằng đếm bậc rồi cộng dồn.
  • Struct of arrays (SoA) thay cho array of structs (AoS). Nếu vòng lặp nóng chỉ đọc trường x của một struct {int x, y, z, w;}, mỗi dòng cache chỉ chứa 4 giá trị x hữu ích. Tách thành int x[N], y[N], ... thì một dòng cache chứa 16 giá trị x.
  • Kiểu dữ liệu nhỏ nhất đủ dùng. Giá trị ≤255 thì unsigned char, ≤32767 thì short, không cần long long thì dùng int. Mảng nhỏ đi một nửa là số dòng cache cần tải cũng giảm một nửa, và còn tránh vượt giới hạn bộ nhớ. Nhưng không tiết kiệm bằng cách để tràn số: tính toán trung gian vẫn phải đủ rộng.
  • Cấp phát một lần. v.reserve(n) trước khi push_back n lần để tránh cấp phát lại và sao chép. Không tạo vector hay string mới bên trong vòng lặp nóng; khai báo ngoài vòng và clear() (giữ nguyên dung lượng).

Tránh phép chia và % trong vòng lặp trong

Phép % với số chia là biến (không phải hằng lúc biên dịch) tốn vài chục chu kỳ, phép nhân chỉ vài chu kỳ. Khi MOD là hằng const, trình biên dịch tự đổi % thành nhân và dịch bit, nhưng vẫn đắt hơn phép cộng nhiều.

Cộng thì không cần %. Nếu a,b∈[0,MOD) thì a+b<2·MOD, chỉ cần trừ một lần:

int add_mod(int a, int b) {      // a, b in [0, MOD)
    int s = a + b;               // < 2 * MOD < 2^31, no overflow
    return s >= MOD ? s - MOD : s;  // one compare instead of %
}

Mod lười (lazy mod) cho tổng các tích. Với MOD=109+7, mỗi tích a·b<MOD2≈1,0·1018, còn unsigned long long chứa được tới 264−1≈1,84·1019. Vậy cộng dồn được 16 tích (cộng thêm phần dư cũ <MOD) mà không tràn:

16·MOD2+MOD≈1,6·1019<1,84·1019.

Chỉ lấy dư sau mỗi 16 số hạng thay vì sau mỗi số hạng:

const unsigned long long MOD = 1000000007;
// C[i][j] starts at 0; A and B entries are already in [0, MOD)
for (int i = 0; i < n; i++)
    for (int k0 = 0; k0 < n; k0 += 16) {
        int k1 = min(n, k0 + 16);
        for (int k = k0; k < k1; k++) {
            unsigned long long a = A[i][k];
            for (int j = 0; j < n; j++) C[i][j] += a * B[k][j];  // no % here
        }
        for (int j = 0; j < n; j++) C[i][j] %= MOD;  // reduce once per 16 terms
    }

Số đo (n=500): một % mỗi phép nhân mất 87 đến 99 ms, mod lười mất 47 đến 58 ms, kết quả giống hệt.

Hai kỹ thuật nâng cao hơn, dùng khi số chia thay đổi lúc chạy hoặc cần nhân mod cực nhiều lần: Barrett reduction (tính trước ⌊264/m⌋, đổi phép chia thành một phép nhân 128 bit và một phép trừ) và Montgomery multiplication (biểu diễn số ở dạng a·Rmodm để phép rút gọn chỉ còn nhân và dịch bit). Cả hai thường thấy trong thư viện FFT/NTT; với đa số bài, const MOD cộng mod lười là đủ.

Không rẽ nhánh và mẹo bit

CPU chạy theo dây chuyền và đoán trước nhánh if. Đoán sai tốn khoảng 10 đến 20 chu kỳ. Nhánh có kết quả ngẫu nhiên (ví dụ if (a[i] > x) trên dữ liệu ngẫu nhiên) bị đoán sai khoảng một nửa số lần.

  • Viết mn = min(mn, x), s += (a[i] > x) (cộng giá trị bool) thay vì if: trình biên dịch dùng lệnh chọn có điều kiện, không rẽ nhánh.
  • Sắp xếp dữ liệu trước khi lọc làm nhánh dễ đoán hơn (nếu việc sắp xếp được dùng lại cho việc khác).
  • Phép bit thay cho phép số học, với x≥0:
int x = 44;                         // 101100 in binary
printf("%d\n", x & 1);              // parity: 0
printf("%d\n", x >> 1);             // x / 2 for x >= 0: 22
printf("%d\n", x & -x);             // lowest set bit: 4
printf("%d\n", __builtin_popcount(x));  // number of set bits: 3
printf("%d\n", __builtin_ctz(x));       // trailing zeros: 2
printf("%d\n", 31 - __builtin_clz(x));  // floor(log2 x): 5

Với số 64 bit dùng __builtin_popcountll, __builtin_ctzll, __builtin_clzll. __builtin_ctz(0) và __builtin_clz(0) không xác định, phải kiểm tra x≠0 trước.

Lưu ý: với số hằng (ví dụ x / 2, x % 8), trình biên dịch đã tự đổi sang phép bit khi bật -O2. Mẹo bit có ích khi bạn biết điều trình biên dịch không biết (ví dụ x≥0, hay số chia là lũy thừa của 2 nhưng nằm trong biến).

Bitset: chia 64 lần

std::bitset<N> gói N giá trị đúng/sai vào ⌈N/64⌉ từ máy 64 bit. Các phép |, &, ^, <<, >>, count() xử lý 64 phần tử mỗi lệnh. Bất cứ vòng lặp nào có dạng "với mọi j, b[j] = b[j] OR/AND c[j + d]" đều tăng tốc khoảng 64 lần.

Ví dụ kinh điển là bài tổng tập con: can[s] cho biết có tập con nào tổng bằng s. Thêm vật nặng x: can[s] |= can[s - x] với mọi s, viết bằng bitset chỉ là can |= can << x.

const int W = 200000;
bitset<W + 1> can;
can[0] = 1;
for (int x : w) can |= can << x;  // 64 sums per machine word

Số đo (n=2000 vật, W=2·105, tức 4·108 cặp): mảng char mất 210 đến 285 ms, bitset mất 10 đến 11 ms. Độ phức tạp từ O(nW) thành O(nW/64). Chi tiết và các ứng dụng khác (đếm tam giác, bao đóng bắc cầu, ghép xâu) xem trang Bitset.

#pragma của GCC

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
  • optimize("O3,unroll-loops"): bật mức tối ưu -O3 và trải vòng lặp cho file này, kể cả khi máy chấm biên dịch với -O2. Hiệu quả không đảm bảo: trên máy của người viết, vòng ikj ở trên chạy 324 đến 335 ms với pragma so với 344 đến 389 ms không có, nằm trong sai số đo. Nó có ích hơn với vòng lặp ngắn mà -O2 không vector hóa.
  • target("avx2,..."): cho phép trình biên dịch dùng lệnh SIMD 256 bit và lệnh đếm bit phần cứng. Có thể tăng tốc vài lần cho vòng lặp tính toán thuần (và làm __builtin_popcount, bitset::count nhanh hơn).

Cảnh báo, theo thứ tự nghiêm trọng:

  1. Máy chấm có thể không hỗ trợ. avx2 chỉ có trên CPU x86 đời mới. Trên CPU ARM (như máy của người viết), dòng target("avx2") gây lỗi biên dịch: pragma or attribute 'target("avx2")' is not valid. Trên CPU x86 cũ không có AVX2, chương trình biên dịch được nhưng chết khi chạy (illegal instruction, báo là RTE). Muốn biết máy chấm có hỗ trợ không, nộp thử một chương trình in __builtin_cpu_supports("avx2").
  2. Pragma phải đặt trước mọi #include, nếu không các hàm trong thư viện chuẩn không được áp dụng, và GCC có thể báo lỗi kiểu inlining failed ... target specific option mismatch khi hàm được biên dịch với hai bộ tùy chọn khác nhau.
  3. -O3 có thể làm chương trình chậm đi (mã to hơn, tràn cache lệnh) và khiến những lỗi hành vi không xác định (tràn số int có dấu, đọc ngoài mảng) lộ ra khác với -O2.
  4. Không có pragma nào cứu được thuật toán sai độ phức tạp. Dùng như bước cuối, sau khi đã làm mọi thứ khác.

Đệ quy và vòng lặp

  • Mỗi lời gọi hàm đệ quy tốn thời gian (lưu thanh ghi, tạo khung stack) và bộ nhớ stack. DFS đệ quy trên đường thẳng 106 đỉnh có thể tràn stack (báo RTE hoặc "segmentation fault") trên máy chấm có stack nhỏ.
  • Với quy hoạch động, cách lặp từ dưới lên (bottom-up) thường nhanh hơn đệ quy có nhớ (memoization) vài lần: không có lời gọi hàm, không kiểm tra "đã tính chưa", và truy cập bảng tuần tự.
  • Khi đệ quy quá sâu, chuyển sang DFS bằng stack tự quản lý (vector<int> làm ngăn xếp) hoặc duyệt theo thứ tự BFS rồi xử lý ngược.
  • Python: giới hạn đệ quy mặc định là 1000. sys.setrecursionlimit(10**6) chỉ nâng giới hạn của Python, không nâng stack của hệ điều hành, nên vẫn có thể chết. Với Python, hầu như luôn nên viết lặp.

Python: những gì làm chậm và cách sửa

Python chậm hơn C++ khoảng 30 đến 100 lần với vòng lặp thuần. Các mẹo sau giúp lấy lại một phần:

  • Đặt code trong hàm main(). Biến cục bộ được tra theo chỉ số, biến toàn cục được tra trong từ điển. Số đo: vòng 107 bước chạy 690 ms trong hàm so với khoảng 1600 ms ở mức toàn cục.
  • Gán hàm dùng nhiều vào biến cục bộ: rd = sys.stdin.readline, app = res.append trước vòng lặp, để khỏi tra thuộc tính mỗi lần.
  • Dùng hàm dựng sẵn chạy bằng C: sum, max, sorted, map, str.join, collections.Counter, itertools.accumulate. Một lời gọi sum(a) nhanh hơn nhiều so với vòng for cộng tay.
  • List comprehension gọn hơn vòng for có append. Trên Python 3.13 và 3.15 người viết đo thấy chênh lệch không đáng kể (107 phần tử: 1146 ms so với 1121 ms), nên hãy dùng vì dễ đọc, đừng trông chờ nó cứu một lời giải quá chậm.
  • PyPy (nếu máy chấm có) chạy vòng lặp thuần nhanh hơn CPython hàng chục lần nhờ biên dịch JIT. Số đo: vòng lặp ở trên còn 27 ms. Nhưng PyPy chậm hơn với code dựa nhiều vào thư viện C, và đệ quy sâu tốn bộ nhớ hơn.
  • numpy thường không có trên máy chấm thi đấu. Đừng viết lời giải phụ thuộc vào nó.
  • Mảng số lớn: bytearray hoặc array('i') gọn hơn list nhiều (mỗi phần tử list là một con trỏ tới đối tượng int riêng).

Độ phức tạp

Mọi kỹ thuật trên trang này giữ nguyên độ phức tạp thời gian, chỉ đổi hằng số, trừ bitset (chia đúng cho 64, độ dài từ máy):

  • Đổi thứ tự vòng lặp, mod lười, không rẽ nhánh, pragma: cùng số phép tính, mỗi phép rẻ hơn. Nhân ma trận vẫn O(n3) thời gian, O(n2) bộ nhớ.
  • Nhập xuất nhanh: vẫn O(kích thước input), nhưng mỗi byte chỉ tốn vài lệnh thay vì một lời gọi hàm có khóa đồng bộ. Bộ đọc fread dùng thêm O(1) bộ nhớ (bộ đệm 64 KB); cách sys.stdin.buffer.read().split() của Python giữ toàn bộ input trong bộ nhớ, tức O(kích thước input).
  • Bitset: tổng tập con từ O(nW) thành O(nW/64) thời gian, bộ nhớ từ W byte thành W/8 byte, vì mỗi phép dịch và OR xử lý 64 vị trí trong một lệnh.
  • Mảng phẳng thay vector<vector>: cùng O(nm) bộ nhớ, nhưng bớt n lần cấp phát và n con trỏ.

⚠️ Lỗi thường gặp

  • Tối ưu hằng số cho thuật toán sai độ phức tạp. Triệu chứng: sau cả ngày chỉnh code vẫn TLE ở test lớn. Cách tránh: ước lượng số phép tính trước; nếu vượt 3·109 mà không dùng được bitset thì tìm thuật toán khác.
  • Trộn cin với scanf/printf sau khi đã sync_with_stdio(false). Triệu chứng: output sai thứ tự hoặc đọc mất dữ liệu. Cách tránh: đã tắt đồng bộ thì chỉ dùng một loại nhập xuất trong cả chương trình.
  • Bài tương tác (interactive) với cin.tie(nullptr) hoặc bộ đọc fread. Triệu chứng: chương trình bị treo hoặc TLE vì câu hỏi chưa được gửi đi. Cách tránh: trong bài tương tác, flush sau mỗi câu hỏi (cout << ... << endl hoặc cout.flush()), và không đọc theo khối lớn vì fread sẽ chờ dữ liệu chưa tới.
  • Tràn số khi mod lười. Triệu chứng: kết quả sai ngẫu nhiên khi n lớn. Cách tránh: tính chặn trên trước (k·MOD2+MOD<264), dùng unsigned long long, và đảm bảo các phần tử đầu vào đã nằm trong [0,MOD). Mod âm: trong C++ (-3) % 5 == -3, cần cộng thêm MOD.
  • Bộ đọc tự viết không xử lý số âm hoặc kết thúc file. Triệu chứng: đọc ra rác hoặc lặp vô hạn khi hết input. Cách tránh: dùng mẫu ở trên (có xử lý - và trả -1 khi hết), kiểm tra trên input có xuống dòng kiểu Windows (\r\n).
  • Kích thước mảng là lũy thừa của 2. Triệu chứng: duyệt theo cột trên mảng [1024][1024] chậm bất thường. Trên macOS, cách ijk với n=1024 mất khoảng 4,7 giây so với 1,6 đến 2,4 giây với n=1000, vì các phần tử cách nhau đúng 2k byte tranh nhau cùng một nhóm ô cache. Cách tránh: duyệt theo hàng; nếu buộc phải đi theo cột, khai báo [1024][1025].
  • Dùng #pragma GCC target("avx2") mà không biết CPU máy chấm. Triệu chứng: CE trên máy ARM, RTE "illegal instruction" trên máy x86 cũ. Cách tránh: kiểm tra trước bằng một lần nộp thử, hoặc không dùng.
  • Đo thời gian với -O0 hoặc trong IDE ở chế độ debug. Triệu chứng: tối ưu một chỗ mà máy chấm không thấy khác, hoặc ngược lại. Cách tránh: đo với đúng cờ biên dịch của máy chấm (thường là -O2), chạy vài lần, so sánh tỉ lệ.
  • Thu nhỏ kiểu dữ liệu quá tay. Triệu chứng: WA vì short hay int tràn ở phép tính trung gian. Cách tránh: chỉ thu nhỏ kiểu của mảng lưu trữ, ép sang kiểu rộng khi tính (1LL * a[i] * b[j]).

Bài tập luyện

Các bài sau có giới hạn được đặt sao cho lời giải đúng độ phức tạp vẫn cần chú ý hằng số.

  • Quản lý nhiệm vụ (bgts1025_c) (Dễ) Thuật toán chỉ là duyệt từng hàng và cộng dồn, nhưng input tới 5·107 số (khoảng 150 MB): bài luyện đọc nhanh theo khối.
  • Vùng sáng ảnh (dhvts1025_d) (Khó) Max trên cửa sổ trượt 2 chiều cho ảnh tới 2,5·107 điểm; cần đọc nhanh và lưu mỗi ô bằng 1 byte để vừa thời gian và bộ nhớ.
  • Xếp ba lô (dhbb18_knapsack) (Rất khó) Hai túi với sức chứa khác nhau; một trường hợp quy về tổng tập con với W1≤5000 giải bằng bitset.
  • Tổng ngẫu nhiên (tst18_rsum) (Rất khó) Tới 109 lần truy cập mảng theo chuỗi chỉ số (a·i+b)modsize; phải tách thành nhiều làn độc lập để CPU chạy song song và thay % bằng phép nhân với nghịch đảo số thực.
  • Phá hủy đường (destroads) (Rất khó) BFS từ mọi đỉnh cho bảng khoảng cách 3000×3000 rồi duyệt mọi cặp (i,j); dùng tính đối xứng d[j][t]=d[t][j] để vòng trong đọc theo hàng, thân thiện với cache.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0