Bitmask DP, Segment Tree và Advanced Graph — mấy thứ mình ước học đúng cách từ đầu
Mình viết bài này vì tuần trước có một bạn hỏi: "anh học Bitmask DP như thế nào mà hiểu được, em đọc tutorial nào cũng thấy nó giải thích xong nhưng vẫn không biết làm."
Câu hỏi đó làm mình ngồi nghĩ lại khá lâu. Vì thật ra hồi mình học, cũng bị đúng cái cảm giác đó — đọc xong thấy OK, rồi mở bài mới ra vẫn không biết bắt đầu từ đâu. Mất cả năm mới thật sự thấy thoải mái với mấy thứ này.
Bài này không phải tutorial. Mình chỉ viết lại những thứ mình nghĩ là mình học sai, học chậm, hoặc hiểu nhầm lâu hơn cần thiết.
Bitmask DP
N ≤ 20
Đây là rule mình vẫn dùng mỗi ngày khi đọc đề: thấy N ≤ 20 là nghĩ ngay đến Bitmask.
Lý do thì đơn giản — 2^20 xấp xỉ một triệu, kết hợp thêm O(N) hoặc O(N²) bên trong vẫn chạy được. Nhưng N = 25 hay 30 mà không có gì tối ưu thêm thì thường chết rồi, đừng cố.
Ngoài N nhỏ còn có mấy từ khóa hay gặp trong đề: "đi qua tất cả", "mỗi phần tử dùng đúng một lần", "chọn tập con", "thứ tự quan trọng". Những từ đó ngầm nói không gian trạng thái là tập hợp, và tập hợp thì encode bằng bitmask.
Phần thật sự khó không phải bit manipulation
Mình mất khá lâu để nhận ra điều này.
Hồi mới học, mình cứ nghĩ phần khó là mấy cái &, |, >> trông lạ. Sau này mới hiểu: cái đó quen tay trong vài tuần là xong. Phần thật sự khó là định nghĩa state.
Cụ thể là: state phải giữ đúng những gì ảnh hưởng đến quyết định tương lai, không nhiều hơn không ít hơn.
Mình từng có thói quen nhét quá nhiều thứ vào state. Kiểu: vị trí hiện tại, node trước đó, số bước đã đi, loại cạnh cuối cùng đã dùng, tổng cost tích lũy... Kết quả là complexity nổ, memory nổ, và tệ hơn là mình không còn hiểu code của mình đang làm gì nữa. WA xong debug không biết bắt đầu từ đâu vì state quá nhiều chiều.
Bài TSP (Traveling Salesman Problem) là ví dụ kinh điển nhất. Đi qua N thành phố mỗi cái đúng một lần, quay về gốc, tổng cost nhỏ nhất.
State đúng là dp[mask][u] — đã thăm đúng các thành phố trong mask, đang đứng ở u. Chỉ vậy thôi. Không cần biết đã đi theo thứ tự gì, vì tương lai chỉ phụ thuộc vào đã đi đâu và đang ở đâu.
Câu hỏi mình hay tự hỏi khi thiết kế state: "Nếu bỏ thông tin X ra, có bài toán con nào bị tính sai không?" Nếu không — thì X không cần ở trong state.
Một lỗi mình hay gặp và gặp mãi là thứ tự ưu tiên toán tử. mask >> i & 1 nhìn ổn nhưng thực ra C++ parse thành mask >> (i & 1), hoàn toàn không phải ý định. Phải viết (mask >> i) & 1.
Lỗi kia là 1 << i với int khi i có thể lên 31 hoặc 32. Signed overflow là UB trong C++. Sau lần đầu bị bug này mình gần như mặc định viết 1LL << i cho tất cả bitmask.
Submask enumeration
for (int sub = mask; sub; sub = (sub - 1) & mask)
Lần đầu thấy cái này mình không hiểu tại sao nó dừng đúng chỗ. Trace tay vài lần mới thấy: nó đi qua tất cả submask theo thứ tự giảm dần, và khi về 0 thì điều kiện sub false nên dừng — tức là 0 không được xét. Nếu cần xét cả empty set thì phải thêm case riêng sau vòng lặp.
Cái này quan trọng vì cho phép làm partition DP kiểu:
dp[mask] = min over all sub of (dp[sub] + dp[mask ^ sub])
Complexity tổng cộng khi enumerate submask qua tất cả mask là O(3^N), không phải O(4^N) như mình nghĩ lần đầu. Proof: mỗi bit của mỗi mask có 3 khả năng — không có trong mask, có trong mask nhưng không trong sub, có trong cả hai. N bit độc lập → 3^N. Khi N = 20 thì 3^20 ≈ 3.5 tỷ — thường hơi chặt, nên thực tế phải estimate kỹ hơn chứ không phải cứ N ≤ 20 là dùng được.
SOS DP giải cùng bài toán trong O(N · 2^N) bằng cách DP theo từng bit một thay vì enumerate trực tiếp. Khi N = 20–22 thì sự khác biệt giữa O(3^N) và O(N · 2^N) là khá lớn.
Mình sẽ không giải thích chi tiết SOS DP ở đây vì bài này sẽ quá dài — nếu bạn chưa biết thì search "SOS DP codeforces blog" có bài viết rất tốt.
Meet in the Middle
N khoảng 35–40 thì 2^N quá lớn, nhưng 2^(N/2) ổn. Chia bài thành hai nửa, solve từng nửa, rồi combine.
Phần chia đôi thường không khó. Phần combine mới là chỗ cần nghĩ. Với subset sum thì two-pointer hoặc binary search. Với bài khác có thể phức tạp hơn nhiều.
Mình hay bị mắc ở bước combine — không phải vì không biết kỹ thuật, mà vì không nghĩ kỹ về thứ gì cần match với thứ gì. Thường phải ngồi vẽ ra cụ thể thì mới thấy.
Segment Tree
Mình sẽ nói thẳng một điều trước: đừng dùng Segment Tree khi Fenwick Tree đủ. Fenwick code ngắn hơn, constant factor nhỏ hơn, ít bug hơn. Cho hầu hết bài point update + range sum query thì Fenwick hoàn toàn đủ. Không hiểu sao nhiều người cứ mặc định Segment Tree cho mọi bài range.
Segment Tree cần thiết khi:
- Range update mà không chỉ là add (ví dụ range assign, hoặc range assign + add mixed)
- Node cần lưu thông tin phức tạp hơn một con số (maximum subarray sum, số lần đổi dấu, segment nào đó khớp pattern...)
- Persistent queries
- Hoặc bài cần merge thông tin theo cách Fenwick không support
Cách mình nghĩ về Segment Tree
Mỗi node lưu thông tin của một đoạn [l, r]. Thông tin đó phải tính được từ thông tin của [l, mid] và [mid+1, r]. Đó là tất cả.
Nghe đơn giản nhưng nó có một hệ quả quan trọng: muốn implement biến thể nào, bạn chỉ cần trả lời hai câu — (1) node lưu gì, và (2) merge như thế nào. Nếu trả lời được hai câu này thì về cơ bản tự viết được.
Bài hay nhất để luyện cái này theo mình là maximum subarray sum trên range. Node cần lưu bốn thứ: sum, pref (max prefix), suff (max suffix), best (max subarray). Merge:
pref(parent) = max(pref(left), sum(left) + pref(right))
suff(parent) = max(suff(right), sum(right) + suff(left))
best(parent) = max(best(left), best(right), suff(left) + pref(right))
sum(parent) = sum(left) + sum(right)
Mình học merge này bằng thuộc lòng mấy tháng trước khi thật sự hiểu từng dòng. Lúc hiểu ra thì hơi ngượng vì thực ra không có gì phức tạp — chỉ là case analysis xem max subarray đi qua giữa hay không.
Lazy Propagation
Đây là phần làm nhiều người ám nhất. Mình cũng vậy — mất cả buổi tối một lần vì quên push lazy trước khi đi xuống con.
Ý tưởng cốt lõi là: khi update một đoạn, không cần đi xuống từng lá ngay. "Ghi nợ" vào node, đẩy xuống sau khi cần. Rule đơn giản: trước khi đi xuống con, luôn push lazy trước.
Phần thật sự khó không phải push — là composition. Khi node đã có pending lazy A, rồi nhận thêm operation B, hai cái này combine như thế nào?
Ví dụ range assign rồi range add: lazy cuối cùng là assign(v) rồi add(delta) — tức là giá trị cuối là v + delta. Nếu có thêm một assign nữa sau đó thì lazy cũ bị override hoàn toàn. Nếu bạn không phân tích rõ composition thì rất dễ ra kết quả sai mà không biết tại sao, vì test nhỏ tay thường không trigger đúng case.
Mình không có cách giải thích ngắn gọn hơn cho phần composition — chỉ là phải ngồi vẽ ra các case và verify từng thứ.
Euler Tour
Tree query khó vì không có "range" tự nhiên. Euler Tour fix bằng cách đánh lại index theo DFS order — subtree của u trở thành đoạn liên tục [tin[u], tout[u]]. Sau đó query subtree = range query bình thường.
HLD làm tương tự nhưng cho path query. Ý tưởng là phân tích path thành O(log N) đoạn liên tục, mỗi đoạn query bằng Segment Tree.
Cách HLD đảm bảo O(log N) đoạn: khi đi theo heavy edge (cạnh xuống con có subtree lớn nhất) thì không tạo thêm đoạn mới. Khi đi qua light edge thì tạo thêm một đoạn, nhưng mỗi lần đi qua light edge subtree size giảm ít nhất một nửa. Suy ra số light edge trên bất kỳ path nào là O(log N).
Implementation HLD dài, nhiều mảng, dễ off-by-one. Mình mỗi lần code lại vẫn phải mất 30–45 phút debug. Không có cách nào khác ngoài luyện nhiều lần đến khi quen tay.
Persistent Segment Tree
Khi update, thay vì sửa node cũ thì clone tất cả node trên path từ root xuống, tạo root mới. Node không thay đổi thì share với version cũ.
Mỗi update: O(log N) node mới. Có thể query bất kỳ version nào cũ.
Ứng dụng mình gặp nhiều nhất: k-th order statistics trên range [l, r] — build persistent segment tree sau mỗi lần insert, rồi với query [l, r] thì dùng version r trừ version l-1.
Advanced Graph
DSU on Tree (Small to Large)
Tên này misleading — thực ra không liên quan gì mấy đến DSU kiểu union-find. Nhiều người gọi là "small to large merging" và mình thấy tên đó chính xác hơn.
Idea: khi merge thông tin từ các con lên cha, luôn merge con nhỏ vào con lớn. Giữ lại cấu trúc của con có subtree lớn hơn, thêm từng phần tử của con nhỏ vào.
Tại sao O(N log N): mỗi phần tử chỉ bị move tối đa O(log N) lần, vì mỗi lần bị move thì nó gia nhập một cấu trúc có size ít nhất gấp đôi.
Cái hay là idea "small to large" này xuất hiện ở nhiều chỗ khác — weighted union trong DSU, offline divide and conquer, merge sort trees. Proof cũng giống nhau. Hiểu một lần thì apply được nhiều nơi.
Heavy-Light Decomposition
Đã giải thích proof ở trên rồi (phần Euler Tour). Phần này chỉ thêm: HLD thường bị trình bày quá phức tạp trong tutorial, làm người học bị overwhelm bởi implementation trước khi hiểu tại sao nó đúng. Nên học proof trước, implementation sau.
Còn lại thì... thật ra chỉ là bookkeeping nhiều mảng. Không có gì đặc biệt về mặt idea sau khi đã hiểu proof.
Centroid Decomposition
Mình thích thuật toán này hơn HLD về mặt "elegance", dù không chắc đây là cách đánh giá đúng.
Centroid của cây là node mà khi xóa, tất cả component còn lại đều có size ≤ N/2. Mọi cây đều có centroid.
Centroid decomposition: chọn centroid, xóa, đệ quy trên mỗi component. Chiều sâu decomposition tree là O(log N).
Property quan trọng nhất: mọi path trên cây đều đi qua centroid của component chứa nó tại một tầng nào đó trong decomposition. Nhờ đó, thay vì xét tất cả cặp path, chỉ cần xét path đi qua từng centroid.
Dấu hiệu dùng: bài hỏi về path với constraint khoảng cách, hoặc "count pairs of nodes thỏa mãn X". Mình thường mất khá lâu để nhận ra khi nào dùng cái này — không có shortcut nào ngoài làm nhiều bài.
2-SAT
Bài toán satisfiability với mỗi clause có đúng 2 literal. Giải được trong O(N + M) bằng SCC.
Model: mỗi biến x có hai node: x và ¬x. Clause (a OR b) tương đương ¬a → b và ¬b → a. Chạy SCC.
Bài có nghiệm ↔ không có biến nào mà x và ¬x cùng SCC.
Phần mình tốn thời gian nhất khi học 2-SAT là translate các ràng buộc trong đề thành implication. Đề thường không viết thẳng "a implies b" mà viết kiểu "nếu chọn A thì không được chọn B" hoặc "ít nhất một trong hai phải đúng". Cần luyện để recognize nhanh.
Một ví dụ hay gặp: bài scheduling với N task, mỗi task có hai time slot, và một số cặp task không thể cùng time slot. Translate: nếu task i chọn slot 1 thì task j không được chọn slot 1, tức là i_slot1 → j_slot2 và j_slot1 → i_slot2. Sau đó 2-SAT cho đáp án.
0-1 BFS
Edge weight chỉ 0 hoặc 1 — dùng deque thay priority queue. Weight 0 thì push_front, weight 1 thì push_back. O(V + E).
Mình hay gặp dạng này trong bài mà "teleport miễn phí" hoặc "đổi hướng cost 1 còn đi thẳng cost 0". Nhận ra dạng này thì dùng 0-1 BFS thay Dijkstra cho đơn giản hơn và nhanh hơn.
Dijkstra state expansion
Đây là dạng mình gặp khá thường: đồ thị gốc không đủ mô tả bài toán vì có thêm "global state" nào đó.
Ví dụ: có K coupon giảm giá, mỗi coupon dùng một lần giảm một cạnh về 0. State (node, k_coupons_used) — build graph với N × (K+1) node rồi chạy Dijkstra bình thường.
Khi gặp bài có cảm giác "Dijkstra nhưng có thêm điều kiện gì đó", thường là expand state là xong.
SCC và condensation
Sau khi condensation, graph trở thành DAG. DAG thì DP được. Đây là lý do SCC quan trọng ngoài 2-SAT.
Nhiều bài reachability hoặc optimization trên graph có cycle thực ra giải được bằng: SCC → condensation → DP trên DAG. Mình hay miss dạng này vì không nhận ra graph gốc có thể condensed.
Mấy thứ khác
Đọc editorial quá sớm
Mình đã làm điều này rất nhiều hồi trước và nghĩ đó là cách học hiệu quả vì "không mất thời gian". Thực ra không phải vậy.
Khi mở editorial sau 15 phút chưa nghĩ ra gì, não chưa có gì để "anchor" thông tin mới vào. Đọc xong hiểu logic, thấy "à đúng rồi", nhưng 3 ngày sau gặp bài tương tự vẫn không tự nghĩ ra được.
Sau khi nhận ra điều này mình cố ít nhất 45–60 phút trước khi mở editorial. Không phải vì nghĩ sẽ tự solve được — mà vì khoảng thời gian đó não đang thử các approach sai, hiểu tại sao sai, và map ra "không gian các thứ không work". Khi đó mở editorial ra, solution "stick" hơn nhiều.
Upsolve sau contest theo cùng lý do. Speed contest luyện tốc độ, upsolve mới là lúc thật sự học.
Brute force + random test
Khi WA mà không biết tại sao, việc thông minh nhất thường là viết brute force O(N³) hoặc O(N!), random generate input nhỏ, chạy song song với solution chính, so sánh output.
Mình tốn thời gian debug bằng tay nhiều lần trước khi học cách này. Bây giờ khi gặp WA khó tái hiện, việc đầu tiên là viết brute force — thường mất 10–20 phút nhưng tiết kiệm được vài tiếng.
Complexity estimate
Thấy N = 2 × 10^5 và time limit 2 giây thì roughly 2 × 10^8 operations. O(N log N) OK. O(N√N) thường qua nhưng không chắc. O(N²) chết.
Estimate complexity trước khi code, không phải sau khi TLE.
Học proof
Không cần thiết ở level thấp. Càng lên cao càng cần — vì không hiểu tại sao một technique đúng thì không có khả năng adapt nó cho bài không fit hoàn toàn vào template.
Tại sao HLD O(log N)? Tại sao small-to-large O(N log N)? Tại sao Dijkstra greedy đúng? Những proof này không quá phức tạp và hiểu chúng giúp nhiều hơn mình nghĩ trước đây.
Viết đến đây thấy bài này khá dài và có vài chỗ lan man. Thôi kệ, đó là những thứ mình thật sự nghĩ và thật sự từng gặp. Nếu có điểm nào chưa rõ hoặc mình giải thích sai thì comment, mình sẽ sửa.
All rights reserved
