Tổng Quan Kỳ Thi Olympic & Kỹ Thuật Chia Khối Căn Bậc Hai (Sqrt Decomposition)
Các kỳ thi Olympic Tin học cấp 3 (Olympic Truyền thống 30/4, Duyên Hải & Đồng Bằng Bắc Bộ, Trại hè Hùng Vương, Tuyển chọn đội tuyển Quốc tế APIO/IOI) đòi hỏi trình độ tư duy thuật toán vượt xa kỳ thi HSG thông thường. Ở đẳng cấp này, thí sinh phải làm chủ các kỹ thuật nâng cao có khả năng xử lý bài toán truy vấn động phức tạp mà Segment Tree truyền thống không thể cài đặt đơn giản.
Tư Tưởng Cốt Lõi Chia Khối
Chia mảng $N$ phần tử thành các khối (blocks) kích thước $B \approx \sqrt{N}$. Có khoảng $N / B \approx \sqrt{N}$ khối. Mỗi truy vấn trên đoạn $[L, R]$ sẽ bao gồm:
• Các khối nằm trọn vẹn ở giữa: tính nhanh qua thông tin tiền xử lý của khối ($O(1)$ mỗi khối).
• Phần đầu (khối chứa $L$) và phần đuôi (khối chứa $R$): duyệt trực tiếp từng phần tử (tối đa $2B$ bước).
Tổng thời gian mỗi truy vấn là $O(\sqrt{N})$.
Ưu Thế Trong Đề Thi Olympic
Sqrt Decomposition có thể giải quyết các bài toán mà phép toán không có tính kết hợp hoặc không nghịch đảo (như đếm số phần tử xuất hiện $\ge K$ lần, mode frequency, tìm phần tử trung vị), hoặc kết hợp tái cấu trúc khối (Rebuilding blocks) sau mỗi $\sqrt{N}$ truy vấn chèn/xóa phần tử.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int BLOCK_SIZE = 450; // xấp xỉ sqrt(200000)
int a[MAXN];
long long block_sum[MAXN / BLOCK_SIZE + 5];
int n, q;
void update(int idx, int val) {
int b = idx / BLOCK_SIZE;
block_sum[b] += 1LL * val - a[idx];
a[idx] = val;
}
long long query(int l, int r) {
long long sum = 0;
int b_l = l / BLOCK_SIZE;
int b_r = r / BLOCK_SIZE;
if (b_l == b_r) {
for (int i = l; i <= r; ++i) sum += a[i];
} else {
// Phần đầu khối chứa L
for (int i = l; i < (b_l + 1) * BLOCK_SIZE; ++i) sum += a[i];
// Các khối nguyên vẹn ở giữa
for (int b = b_l + 1; b < b_r; ++b) sum += block_sum[b];
// Phần đuôi khối chứa R
for (int i = b_r * BLOCK_SIZE; i <= r; ++i) sum += a[i];
}
return sum;
}Kiến thức bổ sung • Điều kiện áp dụng và lưu ý Olympic
Điều kiện và giới hạn: Với tổng đoạn, xây dựng tổng từng khối O(N), cập nhật điểm O(1), truy vấn O(B+N/B). Chọn B xấp xỉ căn N tối ưu về bậc cho truy vấn; bài toán mode/median cần thiết kế thông tin khối riêng, không tự động đạt O(căn N). Khi có chèn/xóa, chi phí khấu hao O(căn N) chỉ đúng nếu thao tác thường và cách rebuild thực sự đáp ứng cận đó.
Bài Tập Trắc Nghiệm Thuật Toán (Bài 1)
Câu 1.1: Cho mảng có kích thước $N = 10^5$. Để thời gian trả lời mỗi truy vấn và thời gian cập nhật tổng thể tối ưu nhất trong kỹ thuật Sqrt Decomposition, kích thước mỗi khối $B$ nên được chọn xấp xỉ bao nhiêu?
Câu 1.2: Trong bài toán có $Q$ truy vấn cập nhật điểm và truy vấn tổng đoạn với mảng $N$ phần tử, khi nào thí sinh Olympic nên chọn Sqrt Decomposition thay vì Segment Tree?
Câu 1.3: Kỹ thuật "Rebuilding Blocks" (Tái cấu trúc mảng định kỳ) sau mỗi $sqrt{N}$ truy vấn chèn hoặc xóa phần tử trong Sqrt Decomposition đảm bảo độ phức tạp trung bình của mỗi thao tác là bao nhiêu?
Câu 1.4: Để tính chỉ số khối (0-indexed) của phần tử tại vị trí $i$ với kích thước khối $B$, công thức chuẩn là:
Thuật Toán Mo (Mo's Algorithm) & Kỹ Thuật Xử Lý Truy Vấn Offline
Thuật toán Mo (Mo's Algorithm) là một kỹ thuật thần thánh giải quyết các bài toán truy vấn trên đoạn $[L, R]$ không có thao tác cập nhật (Offline Queries). Bằng cách sắp xếp lại thứ tự trả lời các truy vấn dựa trên chỉ số khối của $L$, thuật toán tận dụng kết quả của đoạn $[curL, curR]$ trước đó để dịch chuyển con trỏ sang $[L, R]$ mới với chi phí cực thấp: $O((N + Q) sqrt{N})$.
Quy Tắc Sắp Xếp Truy Vấn Mo & Tối Ưu Ziczac (Hilbert Curve)
Truy vấn $Q_i = (L_i, R_i, id)$. Ta nhóm các truy vấn theo khối của $L$: $block(L_i) = L_i / B$.
• Nếu hai truy vấn có $block(L_a)
eq block(L_b)$: sắp xếp theo $block(L)$.
• Nếu cùng khối $block(L)$: sắp xếp theo $R$.
Mẹo tối ưu Ziczac (thứ tự Hilbert là kỹ thuật khác): Nếu $block(L)$ là số lẻ, sắp $R$ tăng dần; nếu $block(L)$ là số chẵn, sắp $R$ giảm dần (đúng theo bộ so sánh ở ví dụ). Thứ tự ziczac thường giảm số bước dịch chuyển con trỏ $R$, nhưng không bảo đảm tăng tốc cố định 2 lần. Thứ tự Hilbert là một cách sắp xếp khác.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int BLOCK = 450;
struct Query {
int l, r, id;
bool operator<(const Query& other) const {
int b1 = l / BLOCK, b2 = other.l / BLOCK;
if (b1 != b2) return b1 < b2;
return (b1 & 1) ? r < other.r : r > other.r; // Ziczac optimization
}
};
int a[MAXN], cnt[MAXN], ans[MAXN]; // a[] sẽ được nén tọa độ về [0, số giá trị khác nhau - 1]
int distinct_cnt = 0;
void add(int val) {
if (cnt[val] == 0) distinct_cnt++;
cnt[val]++;
}
void remove(int val) {
cnt[val]--;
if (cnt[val] == 0) distinct_cnt--;
}
void solve() {
int n, q;
cin >> n >> q;
for (int i = 0; i < n; ++i) cin >> a[i];
vector<int> values(a, a + n);
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
for (int i = 0; i < n; ++i)
a[i] = lower_bound(values.begin(), values.end(), a[i]) - values.begin();
vector<Query> queries(q);
for (int i = 0; i < q; ++i) {
cin >> queries[i].l >> queries[i].r;
queries[i].l--; queries[i].r--; // 0-indexed
queries[i].id = i;
}
sort(queries.begin(), queries.end());
int curL = 0, curR = -1;
for (const auto& q : queries) {
while (curL > q.l) { curL--; add(a[curL]); }
while (curR < q.r) { curR++; add(a[curR]); }
while (curL < q.l) { remove(a[curL]); curL++; }
while (curR > q.r) { remove(a[curR]); curR--; }
ans[q.id] = distinct_cnt;
}
for (int i = 0; i < q; ++i) cout << ans[i] << "\n";
}Kiến thức bổ sung • Điều kiện áp dụng và lưu ý Olympic
Điều kiện và ví dụ: Mo cơ bản áp dụng cho truy vấn offline khi có thể thêm/xóa phần tử ở hai đầu và duy trì đáp án hiệu quả. Với B, chi phí di chuyển xấp xỉ O(N²/B+QB), tối ưu B phụ thuộc N và Q; còn cần O(Q log Q) để sắp xếp. Mảng giá trị âm/lớn cần nén tọa độ (đã bổ sung trong code). Mo with updates và Mo on trees cần xử lý chiều thời gian, LCA và parity riêng.
Bài Tập Trắc Nghiệm Thuật Toán (Bài 2)
Câu 2.1: Độ phức tạp thời gian tổng cộng của thuật toán Mo với $N$ phần tử và $Q$ truy vấn (khi mỗi thao tác thêm/xóa phần tử mất $O(1)$) là:
Câu 2.2: Thuật toán Mo KHÔNG THỂ áp dụng trực tiếp trong trường hợp nào sau đây?
Câu 2.3: Trong phiên bản "Mo với thao tác cập nhật" (Mo with Updates / 3D Mo), mỗi truy vấn được biểu diễn bởi bộ ba $(L, R, T)$ với $T$ là thời điểm sửa đổi. Độ phức tạp thời gian khi chọn kích thước khối $B = N^{2/3}$, giả sử có $Q=O(N)$ truy vấn và $O(N)$ cập nhật, mỗi bước di chuyển con trỏ/thời gian đều $O(1)$, là:
Câu 2.4: Để áp dụng thuật toán Mo giải bài toán truy vấn đường đi giữa 2 nút $(u, v)$ trên cây (Mo on Trees), ta cần kỹ thuật nào để chuyển đường đi trên cây thành đoạn liên tiếp trên mảng 1D?
Cây Phân Đoạn Bền Vững (Persistent Segment Tree)
Persistent Segment Tree (Cây phân đoạn bền vững / Cây phân đoạn lưu lịch sử) là một trong những cấu trúc dữ liệu xuất sắc nhất của lập trình thi đấu Olympic. Mỗi khi thực hiện một cập nhật, thay vì ghi đè lên cây cũ, ta tạo ra một phiên bản cây mới (Version). Nhờ kỹ thuật Node Sharing (Chia sẻ nút), mỗi cập nhật chỉ tạo thêm đúng $O(log N)$ nút mới, cho phép truy vấn trạng thái của cây ở bất kỳ thời điểm nào trong lịch sử!
Bài Toán Kinh Điển: Range K-th Smallest Query (Online)
Tìm phần tử nhỏ thứ $K$ trong đoạn $[L, R]$ bất kỳ trong $O(\log N)$.
• Nén tọa độ các giá trị mảng.
• Cây phiên bản $i$ lưu cây đếm tần số (Frequency Segment Tree) của tiền tố từ $1$ đến $i$.
• Để truy vấn đoạn $[L, R]$, ta xét cây tại thời điểm $R$ và cây tại thời điểm $L - 1$. Vì hai cây có cấu trúc giống hệt nhau, số phần tử rơi vào nhánh con trái ở đoạn $[L, R]$ chính là count = tree[root_R].left.val - tree[root_{L-1}].left.val!
• Nếu $K \le count$: ta rẽ sang nhánh trái; ngược lại: rẽ sang nhánh phải với $K - count$.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
struct Node {
int count = 0;
int left_child = 0, right_child = 0;
};
Node tree[MAXN * 40]; // Mỗi cập nhật tạo thêm log2(N) nút
int roots[MAXN], node_cnt = 0;
int update(int prev_root, int l, int r, int val) {
int cur = ++node_cnt;
tree[cur] = tree[prev_root]; // Sao chép thông tin nút cũ
tree[cur].count++;
if (l == r) return cur;
int mid = l + (r - l) / 2;
if (val <= mid) {
// Tạo nút con trái mới, tái sử dụng nút con phải cũ
tree[cur].left_child = update(tree[prev_root].left_child, l, mid, val);
} else {
// Tạo nút con phải mới, tái sử dụng nút con trái cũ
tree[cur].right_child = update(tree[prev_root].right_child, mid + 1, r, val);
}
return cur;
}
// Tìm phần tử nhỏ thứ K trong đoạn [L, R]
int query(int u, int v, int l, int r, int k) {
if (l == r) return l;
int count_left = tree[tree[v].left_child].count - tree[tree[u].left_child].count;
int mid = l + (r - l) / 2;
if (k <= count_left) {
return query(tree[u].left_child, tree[v].left_child, l, mid, k);
} else {
return query(tree[u].right_child, tree[v].right_child, mid + 1, r, k - count_left);
}
}Kiến thức bổ sung • Điều kiện áp dụng và lưu ý Olympic
Điều kiện và ví dụ: Range k-th yêu cầu 1 ≤ L ≤ R ≤ N, 1 ≤ k ≤ R-L+1; giá trị trả về của hàm query là chỉ số đã nén, phải ánh xạ ngược về giá trị gốc. root[0]=0, mỗi phần tử tạo root[i] bằng update(root[i-1],...). Cần cấp phát đủ nút và kiểm tra giới hạn bộ nhớ. Mã phía trên là phần lõi, chưa phải chương trình nhập/xuất hoàn chỉnh.
Bài Tập Trắc Nghiệm Thuật Toán (Bài 3)
Câu 3.1: Mỗi thao tác cập nhật điểm trong Persistent Segment Tree trên dải giá trị kích thước $N$ sẽ tạo thêm bao nhiêu nút mới trên bộ nhớ?
Câu 3.2: Với bài toán có $N = 2 imes 10^5$ phần tử và cần thực hiện $N$ lần cập nhật Persistent Segment Tree, kích thước mảng tĩnh khai báo số nút tree[] an toàn là khoảng bao nhiêu để tránh tràn chỉ số mảng nút (và phải kiểm tra giới hạn bộ nhớ của đề)?
Câu 3.3: Điểm khác biệt quan trọng nhất giữa Persistent Segment Tree và việc tạo một cây Segment Tree mới hoàn toàn sau mỗi thao tác là gì?
Câu 3.4: Để tìm số nhỏ thứ $K$ trên đường đi từ nút $u$ đến nút $v$ trên một cây bất kỳ trong $O(log N)$, ta áp dụng Persistent Segment Tree trên cây bằng công thức bốn gốc cây nào?
Phân Tách Cây Nặng - Nhẹ (Heavy-Light Decomposition - HLD)
Heavy-Light Decomposition (HLD) là kỹ thuật phân rã một cây bất kỳ thành tập hợp các chuỗi đường đi không giao nhau (Disjoint Chains), gọi là các Chuỗi nặng (Heavy Chains). Nhờ đó, đường đi giữa hai đỉnh bất kỳ trên cây chỉ cắt ngang qua tối đa $O(log N)$ chuỗi nặng! Bằng cách gán chỉ số trên cây vào một Cây phân đoạn (Segment Tree), HLD cho phép cập nhật và truy vấn đường đi trên cây trong thời gian $O(log^2 N)$.
Cạnh Nặng (Heavy Edge) & Nút Con Nặng
Với mỗi nút $u$, nút con $v$ có kích thước cây con lớn nhất được chọn theo quy tắc nút con có cây con lớn nhất (không bắt buộc lớn hơn một nửa kích thước cây cha) làm Heavy Child. Cạnh nối $u o v$ là cạnh nặng (Heavy Edge). Các cạnh nối tới các nút con còn lại là cạnh nhẹ (Light Edge). Vì kích thước cây con giảm ít nhất một nửa mỗi khi đi qua một cạnh nhẹ, trên bất kỳ đường đi nào từ gốc đến lá chỉ có tối đa $le log_2 N$ cạnh nhẹ!
Truy Vấn Đường Đi Giữa $(u, v)$ Bằng HLD
Gọi head[u] là đỉnh đầu của chuỗi nặng chứa $u$. Nếu $u$ và $v$ không cùng chuỗi nặng (head[u] != head[v]), ta chọn đỉnh có head sâu hơn, truy vấn đoạn từ head đến đỉnh đó trên Segment Tree, rồi nhảy lên cha của head. Lặp lại quá trình cho đến khi $u$ và $v$ cùng thuộc 1 chuỗi nặng, chỉ cần 1 truy vấn đoạn cuối cùng giữa $u$ và $v$.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
vector<int> adj[MAXN];
int parent_node[MAXN], depth[MAXN], sz[MAXN], heavy[MAXN];
int head[MAXN], pos[MAXN], cur_pos = 0;
// DFS 1: Tính kích thước cây con và tìm nút con nặng (heavy child)
void dfs_sz(int u, int p, int d) {
parent_node[u] = p; depth[u] = d;
sz[u] = 1; heavy[u] = -1;
int max_c = 0;
for (int v : adj[u]) {
if (v != p) {
dfs_sz(v, u, d + 1);
sz[u] += sz[v];
if (sz[v] > max_c) {
max_c = sz[v];
heavy[u] = v;
}
}
}
}
// DFS 2: Phân tách chuỗi nặng và đánh số pos[] liên tiếp cho Segment Tree
void dfs_hld(int u, int h) {
head[u] = h;
pos[u] = ++cur_pos;
if (heavy[u] != -1) {
dfs_hld(heavy[u], h); // Cùng chuỗi nặng với u
}
for (int v : adj[u]) {
if (v != parent_node[u] && v != heavy[u]) {
dfs_hld(v, v); // Bắt đầu một chuỗi nặng mới với gốc là v
}
}
}Kiến thức bổ sung • Điều kiện áp dụng và lưu ý Olympic
Chứng minh: Heavy child là con có cây con lớn nhất, không bắt buộc chiếm hơn nửa cây cha. Mọi light child có size không vượt quá (size[parent]-1)/2, nên có O(log N) cạnh nhẹ trên đường gốc-lá. Với phép cộng không giao hoán (ví dụ ghép chuỗi), cần giữ đúng thứ tự các đoạn trên đường u-v. DFS đệ quy sâu N có thể tràn stack, nên cân nhắc DFS lặp.
Bài Tập Trắc Nghiệm Thuật Toán (Bài 4)
Câu 4.1: Trên một đường đi bất kỳ từ một nút tới gốc trên cây $N$ đỉnh đã phân tách bằng HLD, số lượng cạnh nhẹ (Light edges) tối đa có thể gặp phải là bao nhiêu?
Câu 4.2: Khi kết hợp HLD với một cây Segment Tree thường, độ phức tạp thời gian để thực hiện một truy vấn cập nhật đoạn giá trị hoặc tìm giá trị lớn nhất trên đường đi giữa hai đỉnh $(u, v)$ là:
Câu 4.3: Trong cấu trúc HLD, các đỉnh thuộc cùng một cây con gốc $u$ (Subtree of $u$) có tính chất gì trên mảng chỉ số vị trí pos[]?
Câu 4.4: Để tìm Tổ tiên chung gần nhất LCA của hai đỉnh $(u, v)$ bằng HLD, ta dừng bước nhảy khi nào?
Phân Tách Trọng Tâm Cây (Centroid Decomposition)
Centroid Decomposition (Chia để trị trọng tâm cây) là phương pháp chia để trị tối thượng để giải quyết các bài toán đếm hoặc tối ưu hóa đường đi trên cây (ví dụ: đếm số cặp đỉnh có khoảng cách bằng $K$, khoảng cách $le K$, hoặc đường đi có trọng số thỏa mãn điều kiện) trong thời gian $O(N log N)$ hoặc $O(N log^2 N)$.
Định Nghĩa Trọng Tâm (Centroid) Của Cây
Trọng tâm của cây $N$ đỉnh là một đỉnh $C$ mà khi loại bỏ $C$, mỗi thành phần liên thông còn lại có kích thước không vượt quá $lfloor N / 2
floor$. Mỗi cây luôn tồn tại ít nhất 1 và nhiều nhất 2 trọng tâm.
Khi xây dựng Cây trọng tâm (Centroid Tree) bằng cách chọn trọng tâm làm gốc rồi đệ quy với các thành phần con, chiều cao của cây trọng tâm được đảm bảo tối đa là $le log_2 N$!
Kiến thức bổ sung • Điều kiện áp dụng và lưu ý Olympic
Điều kiện: Centroid là đỉnh mà khi xóa đi mọi thành phần có kích thước không quá N/2. Độ sâu phân rã O(log N); tổng thời gian xây dựng thông thường O(N log N). Với bài toán khoảng cách, cần tránh đếm đôi các cặp thuộc cùng một nhánh con khi gộp tại centroid. Truy vấn động gần nhất cần lưu khoảng cách đến các tổ tiên centroid và hỗ trợ xóa hợp lệ.
Bài Tập Trắc Nghiệm Thuật Toán (Bài 5)
Câu 5.1: Một cây có $N$ đỉnh. Chiều cao lớn nhất của cây phân rã trọng tâm (Centroid Tree) là bao nhiêu?
Câu 5.2: Khi giải bài toán đếm số cặp đỉnh $(u, v)$ có khoảng cách bằng $K$ trên cây bằng Centroid Decomposition, ta chia các đường đi qua trọng tâm $C$ thành 2 loại nào?
Câu 5.3: Thuật toán tìm trọng tâm của một cây con kích thước $S$ bằng duyệt DFS có độ phức tạp thời gian là:
Câu 5.4: Trong bài toán Dynamic Centroid Tree (cây trọng tâm động) xử lý $Q$ truy vấn đổi màu đỉnh và tìm khoảng cách từ đỉnh $v$ đến đỉnh đỏ gần nhất, mỗi truy vấn mất thời gian bao nhiêu?
Tối Ưu Hóa Quy Hoạch Động (Convex Hull Trick & D&C Optimization)
Trong các kỳ thi chọn học sinh giỏi quốc gia và Olympic, việc tìm ra công thức quy hoạch động $O(N^2)$ chỉ là bước khởi đầu. Để đạt điểm trọn vẹn khi $N ge 2 imes 10^5$, thí sinh phải tối ưu từ $O(N^2)$ xuống $O(N log N)$ hoặc $O(N)$. Hai phương pháp tối ưu hóa kinh điển nhất là Convex Hull Trick (CHT / Li Chao Tree) và Chia để trị (Divide & Conquer Optimization).
Convex Hull Trick (CHT)
Áp dụng cho công thức DP dạng: $dp[i] = min_{j < i} { dp[j] + b[j] imes a[i] } + c[i]$.
Đặt đường thẳng $y = m_j cdot x + c_j$ với hệ số góc $m_j = b[j]$ và hằng số $c_j = dp[j]$, tại hoành độ $x = a[i]$. Bài toán chuyển thành tìm giá trị nhỏ nhất trong tập hợp các đường thẳng!
• Nếu hệ số góc $m_j$ đơn điệu: dùng Deque bao lồi trong $O(N)$.
• Nếu hệ số góc không đơn điệu: dùng Cây Li Chao (Li Chao Tree) hoặc std::set (Dynamic CHT) trong $O(N log N)$.
Tối Ưu Chia Để Trị (D&C Optimization)
Áp dụng cho bài toán chia mảng thành $K$ phần: $dp[i][j] = min_{k < j} { dp[i - 1][k] + C(k + 1, j) }$.
Điều kiện: Hàm điểm thỏa mãn Bất đẳng thức tứ giác (Quadrangle Inequality), dẫn tới tính đơn điệu của điểm cắt tối ưu: $opt[i][j] le opt[i][j + 1]$.
Áp dụng đệ quy chia để trị tính điểm giữa $mid$, giới hạn vùng tìm kiếm cho nửa trái và nửa phải, giảm thời gian từ $O(K imes N^2)$ xuống $O(K imes N log N)$.
Kiến thức bổ sung • Điều kiện áp dụng và lưu ý Olympic
Điều kiện bắt buộc: Deque CHT tuyến tính chỉ khi thứ tự hệ số góc và thứ tự hoành độ truy vấn thích hợp; hệ số góc trùng nhau phải loại đường kém hơn. D&C DP optimization yêu cầu điểm tối ưu đơn điệu, không thể suy ra chỉ từ hình dạng công thức. Knuth optimization cần các giả thiết riêng (Monge/tứ giác và tính đơn điệu phù hợp). Li Chao hỗ trợ đường thẳng toàn miền O(log miền); chèn đoạn thẳng thường cần thêm hệ số log.
Bài Tập Trắc Nghiệm Thuật Toán (Bài 6)
Câu 6.1: Khi hệ số góc của các đường thẳng $m_j$ và hoành độ truy vấn $x_i$ đều tăng dần theo chỉ số, kỹ thuật Convex Hull Trick cài đặt bằng hàng đợi hai đầu (Deque) đạt độ phức tạp thời gian là bao nhiêu?
Câu 6.2: Cây Li Chao (Li Chao Tree) là cấu trúc cây phân đoạn dùng để giải bài toán gì trong $O(log( ext{Range}))$ mỗi thao tác?
Câu 6.3: Điều kiện cần để áp dụng Tối ưu hóa Chia Để Trị (D&C Optimization) cho bảng quy hoạch động 2 chiều là gì?
Câu 6.4: Kỹ thuật tối ưu Knuth Optimization áp dụng cho quy hoạch động trên đoạn (Interval DP) rút ngắn độ phức tạp từ $O(N^3)$ xuống bao nhiêu?
Mạng Luồng Cực Đại (Max Flow & Min Cut) - Thuật Toán Dinic
Mạng luồng (Network Flow) là một trong những chuyên đề phân loại thí sinh mạnh nhất tại các kỳ thi Olympic Tin học và kỳ thi Tuyển chọn Đội tuyển Quốc tế (TST). Định lý nổi tiếng Max-Flow Min-Cut Theorem (Luồng cực đại bằng Lát cắt hẹp nhất) biến hàng loạt bài toán tưởng như tối ưu tổ hợp phức tạp thành bài toán tìm lát cắt trên đồ thị.
Vì Sao Thuật Toán Dinic Là Chuẩn Mực Trong Thi Olympic?
Thuật toán Ford-Fulkerson hoặc Edmonds-Karp ($O(V cdot E^2)$) quá chậm đối với các đồ thị lớn. Thuật toán Dinic sử dụng:
1. Đồ thị phân tầng (Level Graph) dựng bằng BFS trong $O(V + E)$ gán nhãn khoảng cách từ nguồn $S$.
2. Luồng chặn (Blocking Flow) tìm đường tăng luồng bằng DFS chỉ đi qua các cạnh thỏa mãn $level[v] = level[u] + 1$, kết hợp kỹ thuật Current Arc Pointer bỏ qua các cạnh đã bão hòa.
Độ phức tạp tổng thể là $O(V^2 E)$ trong trường hợp tổng quát, và siêu nhanh $O(E sqrt{V})$ trên đồ thị đơn vị (Unit Network / Bipartite Matching)!
Kiến thức bổ sung • Điều kiện áp dụng và lưu ý Olympic
Phân biệt quan trọng: Dinic tổng quát O(V²E); mạng mọi cạnh dung lượng 1 (unit capacities) có cận O(E√E), còn unit network có cận O(E√V). Unit network có điều kiện cấu trúc ngoài dung lượng 1; mạng ghép cặp hai phía thỏa điều kiện. Cạnh ngược trong đồ thị thặng dư cho phép hoàn tác luồng; min-cut lấy các đỉnh còn đi tới được từ nguồn sau khi đạt max-flow.
Bài Tập Trắc Nghiệm Thuật Toán (Bài 7)
Câu 7.1: Theo Định lý Luồng cực đại - Lát cắt hẹp nhất (Max-Flow Min-Cut Theorem), giá trị của luồng cực đại từ nguồn $S$ đến đích $T$ luôn luôn:
Câu 7.2: Khi áp dụng thuật toán Dinic trên unit network (không chỉ đơn thuần mọi cạnh có dung lượng 1) hoặc giải bài toán Cặp ghép cực đại đồ thị hai phía, độ phức tạp thời gian đạt được là:
Câu 7.3: Trong đồ thị thặng dư (Residual Graph) của bài toán luồng cực đại, cạnh ngược tương ứng với cạnh $u o v$ có dung lượng ban đầu bằng bao nhiêu?
Câu 7.4: Để tìm các đỉnh thuộc tập $S$ trong lát cắt hẹp nhất $(S, T)$ sau khi chạy xong thuật toán Dinic, ta thực hiện thao tác nào?
Cặp Ghép Cực Đại & Bài Toán Luồng Chi Phí Nhỏ Nhất (Min-Cost Max-Flow - MCMF)
Nâng cấp từ bài toán luồng cực đại thông thường, Min-Cost Max-Flow (MCMF - Luồng cực đại chi phí nhỏ nhất) giải quyết bài toán vận tải và gán việc tối ưu: mỗi cạnh không chỉ có dung lượng $cap$ mà còn mang chi phí đơn vị $cost$. Mục tiêu là tìm luồng có giá trị lớn nhất sao cho tổng chi phí $sum f_e imes cost_e$ là nhỏ nhất.
Thuật Toán SPFA + Đường Tăng Luồng
Mỗi bước, thay vì tìm đường tăng luồng bất kỳ bằng BFS, ta tìm đường đi ngắn nhất từ $S$ đến $T$ theo trọng số chi phí $cost$ bằng thuật toán SPFA (Shortest Path Faster Algorithm). Do cạnh ngược có chi phí $-cost$, SPFA có thể xử lý cạnh âm nếu không có chu trình âm có thể tiếp cận trong bài toán đường đi ngắn; thời gian xấu nhất của SPFA có thể rất lớn.
Tối Ưu Tiềm Năng Johnson (Primal-Dual)
Để tăng tốc độ từ SPFA lên Dijkstra với priority_queue, thuật toán Primal-Dual sử dụng hàm thế năng (Potential function $h[u]$). Chi phí mới của cạnh $cost'_{u,v} = cost_{u,v} + h[u] - h[v] ge 0$, cho phép chạy Dijkstra trong $O((V+E) log V)$ mỗi lần tìm đường tăng (với hàng đợi ưu tiên), sau khi khởi tạo thế năng hợp lệ và cập nhật thế năng sau mỗi lần chạy; cần bảo đảm chi phí rút gọn không âm trên các cạnh thặng dư có thể dùng.
Kiến thức bổ sung • Điều kiện áp dụng và lưu ý Olympic
Điều kiện: MCMF với đường tăng ngắn nhất cần xử lý chi phí âm, không có chu trình âm thích hợp trong bước tìm đường và có thế năng hợp lệ khi dùng Dijkstra. SPFA không có bảo đảm thời gian nhanh trong trường hợp xấu. Hungarian O(N³) giải bài toán gán tối ưu trên ma trận chi phí vuông; Hopcroft–Karp O(E√V) tìm ghép cực đại hai phía không trọng số.
Bài Tập Trắc Nghiệm Thuật Toán (Bài 8)
Câu 8.1: Trong mạng thặng dư của bài toán Luồng cực đại chi phí nhỏ nhất (MCMF), cạnh ngược của cạnh $u o v$ có chi phí đơn vị bằng bao nhiêu?
Câu 8.2: Định lý Konig phát biểu mối quan hệ gì trên Đồ thị hai phía (Bipartite Graph)?
Câu 8.3: Thuật toán Hungarian (Thuật toán Hungary) giải bài toán Phân công công việc (Assignment Problem) trên đồ thị hai phía đầy đủ $N imes N$ với độ phức tạp tối ưu là:
Câu 8.4: Trong đồ thị tổng quát (không phải đồ thị hai phía), thuật toán Blossom (Thuật toán Hoa nở của Edmonds) giải bài toán Cặp ghép cực đại bằng cách xử lý thành phần nào?
Xử Lý Xâu Nâng Cao: Tự Động Aho-Corasick & Suffix Automaton (SAM)
Nếu KMP chỉ so khớp được 1 xâu mẫu đơn lẻ, thì Aho-Corasick Automaton là sự kết hợp kỳ diệu giữa cây Trie và thuật toán KMP, cho phép tìm kiếm đồng thời hàng vạn xâu mẫu trong văn bản chỉ với một lần duyệt duy nhất trong $O(N + sum |P_i|)$. Bên cạnh đó, Suffix Automaton (SAM) là cấu trúc đồ thị tối thượng biểu diễn toàn bộ các xâu con của một chuỗi trong không gian tuyến tính $O(N)$.
Aho-Corasick Automaton
1. Xây dựng cây Trie chứa tập hợp các từ khóa.
2. Dùng BFS để xây dựng các liên kết thất bại (Suffix Link / Fail Link) tương tự mảng $pi$ của KMP: trỏ từ nút $u$ tới nút biểu diễn tiền tố dài nhất trùng với hậu tố của đường đi tới $u$.
3. Kết hợp quy hoạch động trên đồ thị trạng thái để giải các bài toán xâu ký tự phức tạp (đếm số xâu độ dài $L$ không chứa bất kỳ từ cấm nào trong từ điển).
Suffix Automaton (SAM)
Đồ thị có hướng không chu trình (DAG) biểu diễn mọi xâu con của xâu $S$ độ dài $N$. Với xâu không rỗng độ dài $N$, SAM có tối đa $2N-1$ trạng thái (với $N\ge 2$; $N=1$ có 2 trạng thái) và tối đa $3N-4$ chuyển trạng thái trong cận chuẩn cho $N\ge 3$; lưu ý trường hợp $N$ rất nhỏ. Xây dựng online từng ký tự trong $O(N)$, giải quyết mọi bài toán về xâu con: đếm số xâu con phân biệt, tìm xâu con chung dài nhất của nhiều xâu, tìm xâu con nhỏ thứ $K$ theo thứ tự từ điển trong $O(N)$.
Kiến thức bổ sung • Điều kiện áp dụng và lưu ý Olympic
Điều kiện: Aho–Corasick xây trie, failure links và lan truyền đầu ra; độ phức tạp phụ thuộc tổng độ dài mẫu, văn bản, kích thước bảng chuyển và số lần khớp được xuất ra. SAM đếm số xâu con phân biệt bằng tổng (len[v]−len[link[v]]) trên các trạng thái khác gốc; đếm số lần xuất hiện cần cộng dồn theo độ dài giảm dần. Số trạng thái/chuyển có ngoại lệ ở xâu rất ngắn.
Bài Tập Trắc Nghiệm Thuật Toán (Bài 9)
Câu 9.1: Liên kết thất bại (Fail link / Suffix link) trong thuật toán Aho-Corasick từ nút $u$ trỏ tới nút nào trên cây Trie?
Câu 9.2: Với một xâu ký tự có độ dài $N$, cấu trúc Suffix Automaton (SAM) chứa tối đa bao nhiêu trạng thái (đỉnh)?
Câu 9.3: Để đếm số lượng xâu con phân biệt của xâu $S$ độ dài $N$ bằng Suffix Automaton trong $O(N)$, ta tính tổng đại lượng nào trên các trạng thái?
Câu 9.4: Ứng dụng phổ biến nhất của Aho-Corasick kết hợp với Quy hoạch động (Aho-Corasick DP) trong các đề thi Olympic là gì?
Toán Olympic: Biến Đổi Fourier Nhanh (FFT), Cơ Sở Xor & Chiến Lược 5 Tiếng
Chuyên đề chốt hạ hoàn thiện năng lực dự thi Olympic Quốc tế (IOI / APIO / TST). Thí sinh sẽ nắm vững Fast Fourier Transform (FFT / NTT) nhân đa thức bậc $N$ trong $O(N log N)$, Cơ sở không gian vectơ Xor (Linear Basis) và chiến lược phân bổ thể lực trong 5 tiếng thi đấu liên tục.
Fast Fourier Transform (FFT & NTT)
Nhân hai đa thức bậc $N$ trong $O(N log N)$ thay vì $O(N^2)$ bằng cách chuyển từ biểu diễn hệ số sang biểu diễn giá trị tại các căn đơn vị phức (Roots of Unity), nhân từng tọa độ trong $O(N)$, rồi biến đổi IFFT ngược lại. Khi làm việc với số nguyên modulo $998244353$ ($= 119 imes 2^{23} + 1$), sử dụng Number Theoretic Transform (NTT) với căn nguyên thủy để tránh sai số số thực.
Cơ Sở Tuyến Tính Xor (Linear Basis)
Biểu diễn không gian sinh bởi phép toán XOR của tập hợp các số nguyên. Cơ sở chứa tối đa 64 vectơ độc lập đối với số nguyên không dấu 64-bit (hoặc 60 nếu dữ liệu chỉ dùng các bit 0..59). Cho phép chèn số mới trong $O(60)$, tìm giá trị XOR lớn nhất của một tập con trong $O(60)$, và đếm số tập con có XOR bằng $X$.
Bản Đồ Chiến Thuật 300 Phút (5 Tiếng) Kỳ Thi Olympic / IOI / APIO
Kiến thức bổ sung • Điều kiện áp dụng và lưu ý Olympic
Điều kiện: FFT trên số thực có sai số làm tròn; NTT dùng modulo và căn nguyên thủy thích hợp. Với 998244353 = 119·2²³+1, kích thước biến đổi lũy thừa hai không vượt 2²³. XOR basis 64-bit có tối đa 64 vectơ độc lập; nếu hạng r trên n phần tử thì mỗi giá trị XOR khả đạt có đúng 2^(n−r) tập con biểu diễn (khi đếm tập con theo chỉ số). Cần phân biệt đếm tập con với đếm giá trị XOR phân biệt.
Bài Tập Trắc Nghiệm Thuật Toán (Bài 10)
Câu 10.1: Thuật toán Biến đổi Fourier nhanh (FFT) nhân hai đa thức bậc $N$ đạt độ phức tạp thời gian là:
Câu 10.2: Vì sao trong lập trình thi đấu, modulo $998244353$ thường xuyên được chọn làm modulo cho các bài toán Number Theoretic Transform (NTT)?
Câu 10.3: Số lượng phần tử tối đa trong một Cơ sở tuyến tính Xor (Linear Basis) xây dựng từ một tập hợp các số nguyên không âm 64-bit (kiểu unsigned long long) là bao nhiêu?
Câu 10.4: Trong các kỳ thi chấm trực tuyến với hệ thống CMS (IOI, APIO) cho phép nộp bài nhiều lần và biết điểm ngay (Full Feedback), chiến lược nộp bài khôn ngoan nhất là gì?
Sẵn Sàng Chinh Phục Huy Chương Olympic Tin Học Quốc Tế & Khu Vực!
Bạn đã hoàn thành trọn vẹn 10 chuyên đề thuật toán Olympic đỉnh cao nhất: từ kỹ thuật chia khối căn bậc hai (Sqrt Decomposition), thuật toán Mo, Cây phân đoạn bền vững (Persistent Segment Tree), Heavy-Light Decomposition (HLD), Centroid Decomposition, tối ưu quy hoạch động (Convex Hull Trick), Mạng luồng cực đại Dinic, Min-Cost Max-Flow, máy tự động Aho-Corasick, Suffix Automaton đến biến đổi FFT và cơ sở tuyến tính Xor. Hãy tiếp tục mài giũa ý chí thi đấu trên Codeforces Div.1, AtCoder Grand Contest và các kỳ thi thử thách VNOI Cup để vươn tầm thế giới!