Sắc Lệnh Giáo Dục

Hướng tiếp cận

Bài toán yêu cầu chọn $d$ hoạt động để bảo vệ nhằm tối đa hóa tổng giá trị học sinh an toàn. Ta đổi góc nhìn: thay vì chọn $d$ hoạt động bảo vệ, ta chọn $b=k-d$ hoạt động bị cấm, và tối thiểu hóa tổng giá trị học sinh bị đình chỉ.

Một học sinh bị đình chỉ khi và chỉ khi tập hoạt động của họ là tập con của tập bị cấm. Bài toán trở thành: chọn tập $B$ có $b$ phần tử sao cho ${\sum }_{i:A_i\subseteq B}{v}_i$ là nhỏ nhất.

Nhận xét quan trọng

1. Biểu diễn bitmask: Với $k\le 20$, mỗi tập hoạt động có thể biểu diễn bằng một bitmask. Tập hợp tất cả $2^k$ bitmask có thể được duyệt qua.

2. Tổng trên tập con (Sum Over Subsets — SOS): Gọi $f[\text{mask}]$ là tổng giá trị của tất cả học sinh có tập hoạt động đúng bằng $\text{mask}$. Ta cần tính $g[\text{mask}]={\sum }_{s\subseteq \text{mask}}f[s]$ — tổng giá trị các học sinh mà tập hoạt động là tập con của $\text{mask}$.

3. SOS DP: Phép biến đổi trên có thể tính trong $O(k·2^k)$ bằng kỹ thuật SOS DP (tương tự biến đổi Zeta trên poset tập con).

4. Đáp án: Duyệt qua tất cả mask $B$ có $\text{popcount}(B)=b=k-d$ phần tử, tìm $B$ cho $g[B]$ nhỏ nhất. Kết quả là $\text{total}-ming[B]$.

Thuật toán

1. Đọc input, tính $f[\text{mask}]$ cho mỗi bitmask (gộp giá trị các học sinh có cùng tập hoạt động).

2. Tính SOS DP:

   g = copy of f
   for bit = 0 to k-1:
       for mask = 0 to 2^k - 1:
           if mask has bit set:
               g[mask] += g[mask XOR (1 << bit)]
   

   Sau bước này, $g[\text{mask}]$ chứa tổng $f[s]$ với mọi $s\subseteq \text{mask}$.

3. Duyệt tất cả mask $B$ có đúng $k-d$ bit 1, tìm $ming[B]$.

4. In ra $\text{total}-ming[B]$.

Độ phức tạp

• Thời gian: $O(n+k·2^k)$. Với $k=20$, ta có $20\times 2^{20}\approx 2\times {10}^7$ phép tính cho SOS DP, cộng thêm $2^{20}\approx {10}^6$ cho bước duyệt cuối.
• Bộ nhớ: $O(2^k+n)$. Mảng $f$ và $g$ có kích thước $2^k$.