CHUYÊN ĐỀ TỐI ƯU HÓA QHĐ VỚI BAO LỒI VÀ TỔNG TRÊN TẬP CON

Lời nói đầu: Trong lĩnh vực lập trình thi đấu và khoa học máy tính, quy hoạch động (QHĐ) là một trong những kỹ thuật nền tảng và mạnh mẽ nhất. Tuy nhiên, các công thức QHĐ ở dạng cơ bản thường có độ phức tạp đa thức bậc cao, chẳng hạn như , khiến chúng không đủ hiệu quả cho các bộ dữ liệu lớn. Chuyên đề này đi sâu vào hai kỹ thuật tối ưu hóa QHĐ nâng cao, cho phép chúng ta phá vỡ các rào cản về thời gian chạy và giải quyết các bài toán tưởng chừng như không thể. Kỹ thuật thứ nhất, Convex Hull Trick (CHT), khai thác các tính chất hình học để tối ưu hóa các công thức QHĐ tuyến tính, giảm độ phức tạp từ xuống còn hoặc thậm chí . Kỹ thuật thứ hai, Sum over Subsets (SOS) DP, sử dụng tư duy tổ hợp và quy hoạch động trên các bit để tăng tốc các bài toán liên quan đến tập con, chuyển đổi độ phức tạp từ xuống . Bằng cách nắm vững hai kỹ thuật này, người đọc sẽ được trang bị những công cụ mạnh mẽ để chinh phục một lớp các bài toán QHĐ phức tạp hơn.

Phần I: Convex Hull Trick (CHT) - Tối Ưu Hóa DP Tuyến Tính

Mục tiêu của phần này là chuyển đổi một bước chuyển trạng thái QHĐ thành hoặc bằng cách khai thác các tính chất hình học. Chúng ta sẽ xây dựng một sự hiểu biết sâu sắc từ những nguyên tắc cơ bản nhất.

A. Nền Tảng Lý Thuyết: Từ Quy Hoạch Động đến Hình Học Phẳng

1. Nhận diện và Phân tích Công thức DP Tuyến tính

Kỹ thuật Convex Hull Trick được áp dụng cho một lớp các bài toán quy hoạch động có công thức chuyển trạng thái mang một cấu trúc đặc biệt. Dạng công thức phổ biến nhất có thể được nhận diện là:

hoặc một dạng tương đương để tìm giá trị lớn nhất (max).[1, 2, 3] Trong công thức này, dp[i] là giá trị tối ưu cần tính cho trạng thái i, và nó được xác định thông qua việc lựa chọn một trạng thái j tối ưu trong số tất cả các trạng thái trước đó. Các mảng a và b là các giá trị cho trước của bài toán.

Một cách tiếp cận trực tiếp và ngây thơ để tính toán dp[i] là sử dụng một vòng lặp duyệt qua tất cả các giá trị j từ 0 đến i-1 bên trong vòng lặp chính duyệt i. Điều này dẫn đến một thuật toán với hai vòng lặp lồng nhau, có độ phức tạp thời gian là . Mặc dù đúng đắn, độ phức tạp này thường quá chậm đối với các giới hạn thời gian trong lập trình thi đấu, nơi N có thể lên tới hoặc .[1, 4] Các bài toán kinh điển như "Batch Scheduling" (IOI 2002) và "Commando" (APIO 2010) là những ví dụ điển hình mà giải pháp sẽ không được chấp nhận do quá thời gian.[5, 6, 7] Điều này thúc đẩy sự cần thiết của một phương pháp tối ưu hóa mạnh mẽ hơn.

2. Phép Biến đổi Sang Không Gian Hình Học: Đường thẳng và Truy vấn Điểm

Bước đột phá để tối ưu hóa công thức trên nằm ở việc thay đổi góc nhìn từ đại số sang hình học. Ta thực hiện một phép biến đổi đơn giản nhưng sâu sắc [4]:

• Đặt hệ số góc .
• Đặt tung độ gốc .
• Đặt biến độc lập .

Với các phép đặt này, biểu thức bên trong phép min trở thành . Công thức quy hoạch động được viết lại hoàn toàn dưới dạng hình học:

Diễn giải một cách hình học, mỗi trạng thái j trước đó không còn đơn thuần là một giá trị dp[j], mà nó định nghĩa một đường thẳng trên mặt phẳng tọa độ Descartes với phương trình .[1, 4, 8] Việc tính toán dp[i] giờ đây tương đương với một bài toán hình học: "Cho một tập hợp các đường thẳng, hãy tìm đường thẳng nào có giá trị y nhỏ nhất tại một hoành độ cụ thể ".[1, 4, 9] Sự chuyển đổi này mở ra cánh cửa để áp dụng các công cụ hình học tính toán mạnh mẽ.

3. Khái niệm Bao Dưới (Lower Envelope) và Sự "Vô Dụng" của các Đường Thẳng Thừa

Khi chúng ta vẽ tất cả các đường thẳng lên mặt phẳng, ta sẽ thấy rằng tại mỗi điểm x trên trục hoành, sẽ có một đường thẳng nằm thấp nhất. Tập hợp các điểm thấp nhất này tạo thành một đường gấp khúc. Đường gấp khúc này được gọi là bao dưới (lower envelope) của tập hợp các đường thẳng.[10, 11, 12, 13] Về mặt toán học, bao dưới là đồ thị của hàm .

Một quan sát quan trọng là không phải tất cả các đường thẳng đều đóng góp vào việc hình thành bao dưới. Một số đường thẳng sẽ luôn nằm hoàn toàn phía trên bao dưới, bất kể giá trị của x là gì. Những đường thẳng này được coi là thừa hoặc "vô dụng" (redundant), vì chúng không bao giờ có thể là lựa chọn tối ưu cho bất kỳ truy vấn nào.[4] Việc xác định và loại bỏ hiệu quả các đường thẳng thừa này chính là chìa khóa để tối ưu hóa thuật toán.

Mặc dù kỹ thuật này được gọi là "Convex Hull Trick", một thuật ngữ chính xác hơn về mặt kỹ thuật là "Lower/Upper Envelope". Tên gọi "Convex Hull Trick" xuất phát từ hai lý do: thứ nhất, hàm bao dưới là một hàm lồi (convex function); thứ hai, có một sự đối ngẫu sâu sắc giữa các đường thẳng trong không gian gốc (primal plane) và các điểm trong không gian đối ngẫu (dual plane). Cụ thể, các đỉnh của bao lồi (convex hull) của tập hợp các điểm trong không gian đối ngẫu tương ứng với các đường thẳng tạo nên bao dưới trong không gian gốc.[4, 11, 14] Việc hiểu rõ mối liên hệ này giúp củng cố nền tảng lý thuyết của thuật toán.

B. Nguyên Lý Thuật Toán: Duy Trì Bao Lồi Hiệu Quả

Sau khi chuyển bài toán sang góc nhìn hình học, mục tiêu của chúng ta là xây dựng và duy trì một cấu trúc dữ liệu biểu diễn bao dưới một cách hiệu quả, chỉ chứa các đường thẳng "hữu ích" và hỗ trợ các thao tác thêm đường thẳng và truy vấn giá trị tối ưu một cách nhanh chóng.

1. Loại bỏ Đường thẳng Thừa: Điều kiện Kiểm tra bằng Tích Chéo (Cross-Product)

Làm thế nào để xác định một đường thẳng là thừa? Xét ba đường thẳng được sắp xếp theo thứ tự hệ số góc giảm dần, tức là . Đường thẳng nằm ở giữa sẽ trở nên thừa nếu nó luôn nằm phía trên hai đường thẳng và trong khoảng mà nó có thể là tối ưu. Về mặt hình học, điều này xảy ra khi giao điểm của và có hoành độ nhỏ hơn giao điểm của và .[1, 4]

Để tránh các vấn đề về sai số làm tròn khi làm việc với số thực (phép chia), chúng ta sẽ biến đổi điều kiện này về dạng chỉ sử dụng phép nhân và phép trừ số nguyên. Hoành độ giao điểm của hai đường thẳng và được cho bởi công thức . Điều kiện để loại bỏ là:

Vì ta đã giả sử , các mẫu số và đều dương. Do đó, ta có thể nhân chéo một cách an toàn mà không làm thay đổi chiều của bất đẳng thức:

Đây là công thức kiểm tra chỉ sử dụng các phép toán số nguyên, rất mạnh mẽ và chính xác.[4] Phép toán này về bản chất là một phép thử hướng (orientation test) hoặc tính tích chéo (cross-product) của hai vector, tương tự như trong các thuật toán tìm bao lồi kinh điển như Graham Scan, dùng để kiểm tra xem ba điểm có tạo thành một khúc cua "lồi" hay "lõm".[15, 16, 17]

2. Truy vấn Tối ưu trên Bao Lồi

Sau khi loại bỏ tất cả các đường thẳng thừa, tập hợp các đường thẳng còn lại tạo thành bao dưới. Một tính chất quan trọng của các đường thẳng trên bao dưới là hệ số góc của chúng có tính đơn điệu (ví dụ, giảm dần đối với bài toán tìm min). Các giao điểm của các đường thẳng kề nhau trên bao dưới cũng xuất hiện theo thứ tự tăng dần trên trục hoành.

Nhờ tính chất này, việc tìm đường thẳng tối ưu cho một điểm truy vấn có thể được thực hiện rất nhanh. Vì các giao điểm phân chia trục hoành thành các khoảng, và trong mỗi khoảng chỉ có một đường thẳng là tối ưu, ta có thể sử dụng tìm kiếm nhị phân để xác định khoảng chứa và từ đó tìm ra đường thẳng tối ưu trong thời gian , với là số lượng đường thẳng trên bao dưới.[1]

C. Các Kỹ Thuật Cài Đặt Chuyên Sâu

Việc lựa chọn cấu trúc dữ liệu và thuật toán cài đặt CHT phụ thuộc hoàn toàn vào tính chất đơn điệu của hệ số góc (tức ) và các điểm truy vấn (tức ). Đây là phần quan trọng nhất, quyết định độ phức tạp cuối cùng của lời giải.[1]

1. Trường hợp 1 (Dễ nhất): Hệ số góc b[j] và điểm truy vấn a[i] đều đơn điệu

Đây là trường hợp lý tưởng và hiệu quả nhất, thường gặp trong các bài toán QHĐ sau khi đã sắp xếp dữ liệu đầu vào.

• Điều kiện: Hệ số góc đơn điệu (ví dụ: giảm dần) và các điểm truy vấn cũng đơn điệu (ví dụ: tăng dần).[1, 2, 3]
• Hệ quả:
  • Thêm đường thẳng: Do các hệ số góc giảm dần, các đường thẳng mới sẽ luôn được thêm vào một phía của bao lồi (ví dụ, vào cuối danh sách các đường thẳng được sắp xếp theo hệ số góc).
  • Truy vấn: Do các điểm truy vấn tăng dần, chúng di chuyển từ trái sang phải trên trục hoành. Điều này có nghĩa là đường thẳng tối ưu trên bao lồi cũng sẽ dịch chuyển một cách đơn điệu. Con trỏ chỉ vị trí tối ưu sẽ không bao giờ di chuyển ngược lại.
• Cài đặt: Sử dụng một Deque (hàng đợi hai đầu) hoặc một mảng với hai con trỏ để duy trì các đường thẳng trên bao dưới.[1, 3, 8]
  • Thao tác Thêm (Add): Khi có một đường thẳng mới, ta thêm nó vào cuối deque. Trước khi thêm, ta liên tục kiểm tra và loại bỏ các đường thẳng ở cuối deque nếu chúng bị đường thẳng mới làm cho trở nên thừa (sử dụng điều kiện tích chéo đã nêu ở trên).
  • Thao tác Truy vấn (Query): Để tìm đường thẳng tối ưu cho , ta xem xét các đường thẳng từ đầu deque. Ta liên tục loại bỏ đường thẳng ở đầu deque nếu nó không còn là tối ưu. Điều này xảy ra khi đường thẳng thứ hai trong deque cho kết quả tốt hơn đường thẳng đầu tiên tại điểm . Do tính đơn điệu của , một khi đường thẳng ở đầu bị loại bỏ, nó sẽ không bao giờ trở thành tối ưu nữa. Sau khi loại bỏ, đường thẳng tối ưu chính là đường thẳng ở đầu deque.
• Độ phức tạp: Mỗi đường thẳng được thêm vào deque tối đa một lần và bị loại bỏ khỏi deque (từ đầu hoặc cuối) tối đa một lần. Do đó, tổng thời gian cho tất cả các thao tác là . Độ phức tạp cho mỗi bước chuyển trạng thái QHĐ là khấu trừ (amortized).[1]

2. Trường hợp 2: Chỉ điểm truy vấn a[i] đơn điệu

Trường hợp này linh hoạt hơn, khi hệ số góc của các đường thẳng không tuân theo một trật tự nào.

• Điều kiện: Các điểm truy vấn đơn điệu (ví dụ: tăng dần), nhưng hệ số góc không có thứ tự.[1]
• Hệ quả: Một đường thẳng mới có thể có hệ số góc bất kỳ, do đó nó có thể cần được chèn vào giữa bao lồi hiện tại, chứ không chỉ ở một đầu. Cấu trúc dữ liệu deque không còn phù hợp cho việc chèn hiệu quả.
• Cài đặt: Chúng ta cần một cấu trúc dữ liệu có thứ tự, cho phép chèn và xóa hiệu quả. std::set trong C++ (được triển khai bằng cây nhị phân tìm kiếm cân bằng) là một lựa chọn phổ biến. set sẽ lưu các đường thẳng và tự động duy trì chúng theo thứ tự của hệ số góc.[1, 18]
  • Thao tác Thêm (Add): Việc chèn một đường thẳng mới vào set mất với là số đường thẳng hiện có. Sau khi chèn, ta cần tìm các đường thẳng lân cận (trước và sau nó trong set) và thực hiện kiểm tra loại bỏ. Đường thẳng mới có thể làm một hoặc cả hai lân cận trở nên thừa, hoặc chính nó bị thừa bởi các lân cận. Các thao tác này cũng mất .
  • Thao tác Truy vấn (Query): Mặc dù đơn điệu cho phép tối ưu truy vấn bằng con trỏ, một cách tiếp cận tổng quát và dễ cài đặt hơn là thực hiện tìm kiếm nhị phân (binary search) trên các đường thẳng trong set để tìm ra đường thẳng tối ưu cho . Ta có thể tìm kiếm nhị phân trên các giao điểm của các đường thẳng kề nhau để xác định khoảng chứa .
• Độ phức tạp: Mỗi bước QHĐ bao gồm một thao tác thêm và một thao tác truy vấn, cả hai đều mất . Do đó, tổng độ phức tạp của thuật toán là .[1]

3. Trường hợp 3 (Tổng quát nhất): Cả b[j] và a[i] đều không đơn điệu

Đây là trường hợp mạnh mẽ nhất, xử lý các bài toán "online" nơi các đường thẳng và các truy vấn đến một cách tùy ý.

• Kỹ thuật: Cây Li-Chao (Li Chao Tree) hoặc Cây Phân Đoạn chứa Bao Lồi (Segment Tree of Hulls). Cây Li-Chao thường được ưa chuộng hơn vì cài đặt đơn giản và hiệu quả trong thực tế.[19, 20, 21, 22]
• Cây Li-Chao (Li Chao Tree):
  • Cấu trúc: Là một cây phân đoạn (segment tree) được xây dựng trên miền giá trị của các điểm truy vấn . Mỗi nút trong cây chỉ lưu trữ một đường thẳng duy nhất, là đường thẳng được coi là "tốt nhất" (ví dụ, thấp nhất tại điểm giữa mid) cho đoạn mà nút đó quản lý.[20, 21, 22]
  • Thao tác Thêm (Add): Để thêm một đường thẳng mới new_line vào cây, ta bắt đầu từ gốc. Tại một nút u quản lý đoạn và đang lưu đường thẳng node_line, ta so sánh new_line và node_line tại điểm giữa mid = (L+R)/2.
    1. Nếu new_line tốt hơn node_line tại mid, ta hoán đổi chúng. new_line bây giờ là đường thẳng cũ node_line.
    2. Bây giờ, node_line (đường thẳng mới tốt hơn tại mid) đã được lưu tại nút u. Đường thẳng new_line (đường thẳng cũ) có thể vẫn tốt hơn node_line ở một trong hai nửa đoạn. Ta kiểm tra giao điểm của chúng. Nếu new_line có khả năng tốt hơn ở nửa trái, ta đệ quy thêm new_line vào con trái. Ngược lại, ta đệ quy vào con phải.[20, 21, 22]
  • Thao tác Truy vấn (Query): Để tìm giá trị tối ưu tại điểm x, ta đi từ gốc xuống nút lá tương ứng với x. Trên đường đi, tại mỗi nút u ta đi qua, ta tính giá trị của đường thẳng node_line được lưu ở nút đó tại điểm x. Kết quả cuối cùng là giá trị tối ưu (min/max) của tất cả các giá trị này.[20, 22, 23]
• Độ phức tạp: Cả hai thao tác thêm và truy vấn đều đi theo một đường từ gốc đến lá của cây. Chiều cao của cây phụ thuộc vào miền giá trị C của các tọa độ x. Do đó, độ phức tạp cho mỗi thao tác là . Tổng độ phức tạp của thuật toán là .[20, 22]

Bảng 1: So sánh các phương pháp cài đặt CHT

D. Lưu ý Thực chiến và Cạm bẫy Cài đặt

Khi triển khai CHT trong các cuộc thi, có một số chi tiết kỹ thuật quan trọng cần được chú ý để đảm bảo tính đúng đắn và hiệu quả.

1. Xử lý Số nguyên và Tránh Sai số Dấu phẩy động: Vấn đề lớn nhất khi làm việc với các bài toán hình học là sai số của các kiểu dữ liệu dấu phẩy động (float, double). Việc tính toán trực tiếp tọa độ giao điểm bằng phép chia có thể dẫn đến kết quả không chính xác. Do đó, một nguyên tắc vàng là luôn ưu tiên sử dụng các phép toán trên số nguyên. Phép kiểm tra loại bỏ đường thẳng thừa bằng cách nhân chéo là một ví dụ điển hình. Nó cho phép so sánh vị trí tương đối của các giao điểm mà không cần tính chính xác tọa độ của chúng, từ đó loại bỏ hoàn toàn sai số.[4]

2. Ngăn ngừa Tràn số: Mặc dù việc sử dụng số nguyên giúp tránh sai số, nó lại có nguy cơ gây ra tràn số. Trong công thức kiểm tra tích chéo, chúng ta nhân các giá trị tọa độ và hệ số góc. Nếu các giá trị này có độ lớn khoảng , tích của chúng có thể lên tới , vượt quá khả năng lưu trữ của kiểu int 32-bit. Do đó, việc sử dụng kiểu dữ liệu long long (64-bit) trong C++ là gần như bắt buộc để chứa các kết quả trung gian này.[8, 18] Trong một số bài toán có giới hạn dữ liệu rất lớn (ví dụ, tọa độ lên tới ), ngay cả long long cũng có thể bị tràn. Trong những trường hợp này, nếu trình biên dịch hỗ trợ (như GCC/Clang), ta có thể sử dụng kiểu __int128 để thực hiện các phép nhân một cách an toàn.[4, 18]

3. Chuyển đổi giữa Bài toán Cực tiểu hóa và Cực đại hóa: Kỹ thuật CHT có thể áp dụng cho cả bài toán tìm min và max. Việc chuyển đổi rất đơn giản: chỉ cần đảo ngược dấu của tất cả các bất đẳng thức trong các phép so sánh.

   • Khi tìm max, ta sẽ duy trì một bao trên (upper envelope), là một đường gấp khúc lõm lên trên.
   • Điều kiện loại bỏ một đường thẳng sẽ đảo ngược lại. Ví dụ, với các hệ số góc giảm dần, thay vì loại bỏ khi (c3 - c1) * (m1 - m2) <= (c2 - c1) * (m1 - m3), ta sẽ loại bỏ nó khi (c3 - c1) * (m1 - m2) >= (c2 - c1) * (m1 - m3).
   • Tương tự, logic truy vấn cũng sẽ đảo ngược để tìm đường thẳng cao nhất thay vì thấp nhất.

Phần II: Sum over Subsets (SOS) DP - Siêu Tính Toán trên Bitmask

Mục tiêu của phần này là giảm độ phức tạp của các bài toán duyệt tập con hoặc tập cha từ các hàm mũ bậc cao như hoặc xuống còn , một ngưỡng cho phép giải quyết các bài toán với lên tới khoảng 20-24.

A. Nền Tảng Lý Thuyết: Bài toán Tổng trên Tập Con

1. Nhận diện Dạng bài toán và Phân tích Độ phức tạp Ngây thơ

Các bài toán có thể tối ưu bằng SOS DP thường có một trong các dạng sau:

• Sum over Subsets (Tổng trên các tập con): Cho một mảng A có kích thước , được đánh chỉ số bằng các bitmask từ 0 đến . Ta cần tính một mảng F sao cho với mỗi mask, .[24, 25, 26]
• Sum over Supermasks (Tổng trên các tập cha): Tương tự, tính mảng G sao cho với mỗi mask, .[27, 28]
• Các bài toán đếm cặp: Đếm số cặp trong một tập hợp cho trước thỏa mãn các điều kiện về bit như , , v.v. Các bài toán này thường có thể được biến đổi để sử dụng một trong hai dạng trên.[29, 30]

Cách tiếp cận ngây thơ nhất là duyệt qua tất cả các mask và với mỗi mask, duyệt qua tất cả các submask của nó để tính tổng.

// Cách làm O(4^N)
for (int mask = 0; mask < (1 << N); ++mask) {
    for (int sub = 0; sub < (1 << N); ++sub) {
        if ((sub & mask) == sub) { // Kiểm tra sub có phải là tập con của mask
            F[mask] += A[sub];
        }
    }
}

Một cải tiến nhỏ là chỉ duyệt qua các submask thực sự của mask bằng một mẹo bitwise: for (int sub = mask; ; sub = (sub - 1) & mask). Cách này giảm độ phức tạp xuống còn .[25, 26, 31]

2. Giải thích Độ phức tạp qua Nhị thức Newton

Để hiểu tại sao độ phức tạp của cách làm cải tiến là , ta hãy phân tích tổng số thao tác. Tổng số lần lặp của vòng lặp trong cùng là , trong đó là số lượng bit 1 (population count) trong mask.

Trong không gian bit, có mask có chính xác bit 1. Mỗi mask như vậy có tập con. Do đó, tổng số thao tác là:

Sử dụng công thức nhị thức Newton, , ta có thể viết lại tổng trên bằng cách chọn và :

Độ phức tạp vẫn quá chậm khi vượt quá khoảng 18, đòi hỏi một phương pháp hiệu quả hơn.[26, 31]

B. Nguyên Lý Thuật Toán: Quy Hoạch Động theo "Chiều"

1. Tư duy "N-chiều" của Bitmask

Cốt lõi của SOS DP là một sự thay đổi hoàn toàn trong tư duy. Thay vì cố định một mask và duyệt qua các tập con của nó, chúng ta sẽ xử lý bài toán theo từng "chiều" (dimension) một.[25]

Hãy tưởng tượng một bitmask bit như một điểm trong không gian Euclid chiều, với mỗi bit là một tọa độ trên một trục (giá trị 0 hoặc 1). Dưới góc nhìn này, bài toán "Sum over Subsets" trở thành một bài toán quen thuộc hơn: tính tổng tiền tố (prefix sum) trong không gian chiều. Cụ thể, chính là tổng giá trị của tất cả các "điểm" có tọa độ nhỏ hơn hoặc bằng tọa độ của mask ở mọi chiều.[25] Ví dụ, nếu mask có tọa độ , thì sub là tập con của mask nếu tọa độ của sub là thỏa mãn với mọi .

Tư duy này cho phép chúng ta áp dụng kỹ thuật tính tổng tiền tố kinh điển: xử lý tuần tự từng chiều một.

2. Xây dựng Công thức Truy hồi và Phân tích Độ phức tạp

Dựa trên ý tưởng tính tổng tiền tố theo chiều, ta có thể xây dựng một công thức quy hoạch động.

• Định nghĩa trạng thái DP: Gọi là tổng trên các tập con của mask mà chỉ được phép khác mask ở bit đầu tiên (từ bit 0 đến bit ).[24, 25] Mục tiêu của chúng ta là tính cho mọi mask.
• Công thức chuyển trạng thái: Khi tính , ta dựa trên các giá trị đã tính cho bit đầu tiên.
  • Nếu bit thứ i của mask là 0: Bất kỳ tập con nào của mask mà chỉ khác ở bit đầu cũng phải có bit thứ i là 0. Do đó, chúng cũng là tập con của mask chỉ khác ở bit đầu. Vậy:

  • Nếu bit thứ i của mask là 1: Các tập con của mask (xét trong bit đầu) có thể được chia thành hai nhóm không giao nhau:
    1. Các tập con có bit thứ i là 1: Chúng chính là các tập con của mask mà chỉ khác ở bit đầu. Tổng của chúng là .
    2. Các tập con có bit thứ i là 0: Chúng chính là các tập con của mask với bit i bị tắt, tức là mask ^ (1<<i). Tổng của chúng là . Kết hợp hai nhóm này, ta có:
    [24, 25, 32]
• Độ phức tạp: Ta có "chiều" (bit) để xử lý và mask. Mỗi bước chuyển trạng thái mất . Do đó, tổng độ phức tạp của thuật toán là .

C. Kỹ Thuật Cài Đặt Tối Ưu

1. Phiên bản Lặp (Iterative) và Tối ưu Bộ nhớ

Quan sát công thức truy hồi, ta thấy rằng việc tính toán cho chiều i chỉ phụ thuộc vào kết quả từ chiều i-1. Điều này cho phép chúng ta loại bỏ chiều i ra khỏi mảng DP và thực hiện tính toán tại chỗ (in-place), giảm bộ nhớ từ xuống .[25, 30] Đây là phiên bản cài đặt phổ biến nhất và hiệu quả nhất.

Code Template (Sum over Subsets):

// Giả sử mảng F đã được khởi tạo với F[mask] = A[mask]
for (int i = 0; i < N; ++i) { // Duyệt qua từng "chiều" (bit) từ 0 đến N-1
    for (int mask = 0; mask < (1 << N); ++mask) {
        // Nếu bit thứ i của mask được bật
        if (mask & (1 << i)) {
            // Cộng dồn giá trị từ mask có bit i bị tắt
            F[mask] += F[mask ^ (1 << i)];
        }
    }
}

[24, 25, 33]

2. Giải thích Tầm quan trọng của Thứ tự Vòng lặp

Thứ tự của các vòng lặp trong phiên bản lặp là cực kỳ quan trọng và không thể hoán đổi. Vòng lặp duyệt qua các bit (chiều) i phải nằm ở bên ngoài, và vòng lặp duyệt qua các mask phải nằm ở bên trong.[25, 30]

Lý do nằm ở bản chất của việc tính tổng tiền tố theo từng chiều. Khi chúng ta đang xử lý chiều i, thuật toán yêu cầu rằng tất cả các giá trị phải đã được tính toán một cách đầy đủ và chính xác đối với tất cả các chiều trước đó (từ 0 đến ).

• Khi vòng lặp i ở ngoài, nó đảm bảo một trật tự xử lý tuần tự qua các chiều. Khi đến chiều i, ta có thể chắc chắn rằng giá trị đã bao gồm tất cả các đóng góp từ các tập con chỉ khác biệt ở các bit từ 0 đến . Do đó, việc cộng dồn F[mask] += F[mask ^ (1 << i)] là đúng đắn.
• Nếu ta đảo ngược thứ tự vòng lặp (vòng lặp mask ở ngoài), khi đang xử lý một mask cụ thể, ta sẽ cố gắng cập nhật nó bằng cách sử dụng các giá trị cho các i khác nhau. Tuy nhiên, các giá trị này có thể vẫn đang ở trạng thái trung gian, chưa được cập nhật đầy đủ cho tất cả các chiều, dẫn đến kết quả cuối cùng bị sai.

D. Các Biến Thể và Mở Rộng Nâng Cao

Sức mạnh của SOS DP không chỉ dừng lại ở bài toán tổng trên tập con cơ bản. Kỹ thuật này có thể được mở rộng và biến đổi để giải quyết nhiều vấn đề khác.

1. Sum over Supermasks: Tính tổng trên Tập Cha

Bài toán này yêu cầu tính . Logic tương tự như SOS, nhưng thay vì "kéo" giá trị từ các tập con lên, ta "đẩy" giá trị từ các tập cha xuống. Để đảm bảo tính đúng đắn khi tính tại chỗ, vòng lặp mask bên trong phải duyệt ngược từ về 0. Điều này đảm bảo rằng khi ta cập nhật (đang xét), giá trị mà ta sử dụng đã là giá trị cuối cùng.

Code Template (Sum over Supermasks):

// Khởi tạo F[mask] = A[mask]
for (int i = 0; i < N; ++i) {
    for (int mask = (1 << N) - 1; mask >= 0; --mask) { // Duyệt mask ngược
        // Nếu bit thứ i của mask bị tắt
        if (!(mask & (1 << i))) {
            // Cộng dồn giá trị từ tập cha có thêm bit i
            F[mask] += F[mask | (1 << i)];
        }
    }
}

[28]

2. Mở rộng cho các Toán tử khác (min, max, gcd, xor)

Tư duy quy hoạch động theo chiều của SOS DP có thể áp dụng cho bất kỳ toán tử hai ngôi ⊕ nào có tính giao hoán và kết hợp. Ví dụ, để tìm giá trị lớn nhất trên tất cả các tập con, ta chỉ cần thay phép += bằng max.

Điều này cũng đúng với các toán tử như min, gcd, xor, &, |, mở ra một loạt các ứng dụng đa dạng.[30]

3. Phép Biến đổi Ngược (Inverse Transform) và Mối liên hệ với Nguyên lý Bao hàm - Loại trừ

Đây là một trong những ứng dụng mạnh mẽ nhất của SOS DP.

• Bài toán: Cho mảng kết quả , hãy khôi phục lại mảng A ban đầu.
• Cài đặt: Phép biến đổi ngược chỉ đơn giản là đảo ngược phép toán của phép biến đổi thuận. Nếu phép thuận dùng +=, phép ngược sẽ dùng -=.[34, 35] Code Template (Inverse SOS):

  // Mảng F chứa kết quả Sum over Subsets, ta muốn tìm lại A
  for (int i = 0; i < N; ++i) {
      for (int mask = 0; mask < (1 << N); ++mask) {
          if (mask & (1 << i)) {
              F[mask] -= F[mask ^ (1 << i)];
          }
      }
  }
  // Sau vòng lặp, mảng F chính là mảng A ban đầu
  

  Copy
• Nền tảng lý thuyết: Phép biến đổi ngược này không phải là một mẹo ngẫu nhiên. Nó là một ứng dụng trực tiếp của Nguyên lý Bao hàm - Loại trừ trên dàn (lattice) các tập con. Công thức toán học tường minh cho việc khôi phục A là:
  Đây chính là Phép biến đổi Mobius trên tập hợp các tập con.[36, 37, 38] Đoạn mã trên là một cách cực kỳ hiệu quả để tính toán công thức bao hàm-loại trừ phức tạp này trong thời gian . Việc hiểu rõ mối liên hệ này cho phép chúng ta giải quyết các bài toán đếm phức tạp bằng cách chuyển chúng về dạng SOS DP, thực hiện các phép toán trên không gian biến đổi, sau đó dùng phép biến đổi ngược để quay về kết quả cuối cùng.

Bảng 2: So sánh các biến thể của SOS DP

Phần III: Phân Tích Bài Tập Kinh Điển và Thực Hành

Lý thuyết sẽ trở nên vững chắc hơn khi được áp dụng vào các bài toán cụ thể. Phần này sẽ phân tích sâu hai bài toán kinh điển, một cho CHT và một cho SOS DP, để minh họa cách nhận diện, biến đổi và giải quyết chúng.

A. Phân tích sâu bài toán CHT: "Commando" (APIO 2010) [5]

Bài toán "Commando" là một ví dụ mẫu mực cho việc áp dụng CHT để tối ưu hóa một bài toán QHĐ có công thức chuyển trạng thái dạng bậc hai.

1. Xây dựng công thức QHĐ: Gọi dp[i] là tổng hiệu quả điều chỉnh lớn nhất có thể đạt được khi phân chia i người lính đầu tiên thành các đơn vị. Để tính dp[i], ta xét đơn vị cuối cùng bao gồm các người lính từ j+1 đến i (với ). Phần còn lại (từ 1 đến j) đã được phân chia một cách tối ưu với tổng hiệu quả là dp[j].

   • Công thức chuyển trạng thái là: .
   • Hiệu quả của đơn vị cuối là , với .

2. Biến đổi về dạng : Công thức trên có vẻ phức tạp, nhưng ta có thể biến đổi nó về dạng tuyến tính phù hợp cho CHT.

   • Sử dụng mảng tổng tiền tố , ta có .
   • Thay vào công thức QHĐ: .
   • Khai triển bình phương và nhóm lại các số hạng:
   • Tách các số hạng chỉ phụ thuộc vào i ra khỏi max:
   • Sắp xếp lại các số hạng bên trong max để có dạng : .[39]
   • Đến đây, ta đã thành công đưa bài toán về dạng CHT. Với mỗi i, ta cần tìm j để tối đa hóa một hàm tuyến tính của . Ta có:
     • Biến truy vấn:
     • Hệ số góc:
     • Tung độ gốc:

3. Phân tích tính đơn điệu và lựa chọn phương pháp cài đặt CHT:

   • Điểm truy vấn : Vì các giá trị trong đề bài là dương, mảng tổng tiền tố là một dãy tăng nghiêm ngặt. Do đó, các điểm truy vấn là đơn điệu.
   • Hệ số góc :
     • là dãy tăng dần.
     • Hệ số trong đề bài được cho là số âm. Do đó, là một hằng số dương.
     • Vì vậy, là một dãy tăng dần.
   • Kết luận: Ta có hệ số góc tăng dần và điểm truy vấn tăng dần. Đây là trường hợp đơn điệu kép (Trường hợp 1). Mặc dù đây là bài toán max với hệ số góc tăng dần, nó hoàn toàn tương tự trường hợp min với hệ số góc giảm dần. Do đó, ta có thể sử dụng phương pháp Deque để giải quyết bài toán này với độ phức tạp tổng thể là .[8, 40]

B. Phân tích sâu bài toán SOS DP: "Jzzhu and Numbers" (Codeforces 449D) [41]

Bài toán này yêu cầu đếm số lượng tập con không rỗng của một dãy số cho trước sao cho phép toán AND trên tất cả các phần tử của tập con đó bằng 0.

1. Sử dụng Nguyên lý Bao hàm - Loại trừ để chuyển đổi bài toán: Đếm trực tiếp số tập con có AND bằng 0 là rất khó. Thay vào đó, ta sử dụng Nguyên lý Bao hàm - Loại trừ (PIE).
   • Gọi là tập các số trong dãy đầu vào.
   • Gọi là số lượng tập con không rỗng sao cho là một tập cha của mask (tức là ).
   • Điều kiện "AND của tập con là tập cha của mask" tương đương với việc "mọi phần tử trong tập con đó đều là tập cha của mask".
   • Số lượng tập con có AND bằng 0 chính là kết quả của công thức PIE:

.[28, 41]

1. Áp dụng SOS DP (Sum over Supermasks) để tính toán: Bây giờ, bài toán quy về việc tính cho mọi mask.

   • Đầu tiên, ta cần đếm số lượng các phần tử trong dãy là tập cha của một mask cho trước. Gọi count[mask] là số lượng phần tử sao cho là tập cha của mask.
   • Ta có thể tính mảng count này một cách hiệu quả bằng kỹ thuật Sum over Supermasks DP trong , với là số bit (trong bài này là 20, vì ).[28]

     // Khởi tạo dp[val] = số lần xuất hiện của val trong mảng input
     for (int i = 0; i < 20; ++i) {
         for (int mask = (1 << 20) - 1; mask >= 0; --mask) {
             if (!((mask >> i) & 1)) {
                 dp[mask] += dp[mask | (1 << i)];
             }
         }
     }
     // Sau vòng lặp, dp[mask] chính là count[mask]
     

     Copy

2. Tổng hợp kết quả cuối cùng:

   • Với một mask cố định, ta đã biết có count[mask] số trong dãy là tập cha của mask.
   • Số tập con không rỗng có thể tạo thành từ count[mask] số này là . Mọi tập con như vậy đều sẽ có AND là một tập cha của mask. Do đó, .
   • Cuối cùng, ta áp dụng công thức PIE đã có:

   • Độ phức tạp tổng thể của lời giải bị chi phối bởi bước SOS DP, là , với là số lượng phần tử trong dãy ban đầu và là số bit. Đây là một lời giải hiệu quả và phù hợp với giới hạn của bài toán.[41]

C. Hướng dẫn Luyện tập

• Convex Hull Trick:

  • Bắt đầu: Tìm các bài toán mà hệ số góc và điểm truy vấn đều đơn điệu để làm quen với việc cài đặt bằng deque. Ví dụ: "Batch Scheduling" (IOI 2002) [6], "Acquire" (USACO Mar08).[4]
  • Nâng cao: Chuyển sang các bài toán chỉ có điểm truy vấn đơn điệu hoặc không có tính đơn điệu nào, yêu cầu sử dụng std::set hoặc Cây Li-Chao. Các bài toán trên Codeforces có tag cht hoặc dp optimization là nguồn luyện tập phong phú. Ví dụ: "Bear and Bowling 4" (CF660F) [18], "Levels and Regions" (CF673E).[18]

• Sum over Subsets DP:

  • Bắt đầu: Giải các bài toán đếm cơ bản. Ví dụ: Cho một tập các số, với mỗi mask, đếm xem có bao nhiêu số trong tập là tập con của mask. Bài "Compatible Numbers" (CF165E) là một khởi đầu tốt.[24]
  • Nâng cao: Tìm các bài toán yêu cầu kết hợp SOS DP với các kỹ thuật khác như bao hàm - loại trừ ("Jzzhu and Numbers" - CF449D) [42], hoặc các bài toán phức tạp hơn trên các nền tảng như AtCoder, CodeChef. Bài toán "Legacy" (CF786B), mặc dù giải bằng cây phân đoạn trên cây phân đoạn, nhưng có tư tưởng xây dựng đồ thị trên các khoảng, gần gũi với việc tối ưu hóa trên các cấu trúc tập hợp.[43]

Kết luận

Convex Hull Trick và Sum over Subsets DP là hai minh chứng tiêu biểu cho vẻ đẹp và sức mạnh của việc tối ưu hóa thuật toán. CHT biến đổi một vấn đề QHĐ đại số thành một bài toán hình học về việc tìm bao của một tập hợp đường thẳng, cho phép giảm độ phức tạp từ bậc hai xuống gần như tuyến tính. SOS DP, mặt khác, nhìn nhận các bitmask như những chiều trong không gian và áp dụng nguyên lý của tổng tiền tố để giải quyết các bài toán duyệt tập con một cách hiệu quả phi thường.

Việc nắm vững không chỉ cách cài đặt mà còn cả bản chất lý thuyết đằng sau các kỹ thuật này — tính chất hình học của bao lồi, sự đối ngẫu, hay tư duy không gian N-chiều của bitmask và mối liên hệ với nguyên lý bao hàm - loại trừ — sẽ cung cấp cho các lập trình viên một lợi thế cạnh tranh đáng kể. Chúng không chỉ là những công cụ để giải quyết một lớp bài toán cụ thể, mà còn là những ví dụ điển hình về tư duy sáng tạo, khả năng nhìn nhận vấn đề dưới nhiều lăng kính khác nhau để tìm ra lời giải tối ưu và thanh lịch.