Chia quà 3

Nguồn: CLUE OJ – Chương 22: Quy hoạch động (tham khảo đề HSG THPT Hậu Giang 2025, có chỉnh sửa) Độ khó: Khá Quy hoạch động Cái túi Bitset

Đề bài

Thầy có nhiều phần quà gồm loại 1 và loại 2, thầy cho đội 1 quà loại 1 và cho đội 2 quà loại 2 theo điều kiện:

• Số lượng thành viên của 2 nhóm chênh lệch không quá 1.
• Chênh lệch giữa tổng các môn của 2 nhóm là ít nhất.

Dữ liệu vào:

• Dòng đầu số $N$ $(2 \le N \le 300)$ cho biết số lượng học sinh.
• Dòng tiếp theo gồm $N$ số cho biết tổng điểm của từng học sinh. Tổng điểm của mỗi học sinh từ $[1 - 600]$.

Kết quả: gồm 1 dòng duy nhất là 2 số nguyên được sắp xếp không giảm thể hiện tổng điểm các thành viên của 2 nhóm.

Subtask:

• 20% điểm đầu tiên có $N \le 20$.
• 40% điểm tiếp theo có $N \le 100$.
• 40% điểm còn lại không có giới hạn gì thêm.

Giới hạn trên CLUE OJ: 2 giây, 256 MB.

Ví dụ – input

5
3 1 2 5 4

Ví dụ – output

7 8

Giải thích ví dụ: 5 bạn có điểm 3, 1, 2, 5, 4 (tổng 15). Nhóm 2 người, nhóm 3 người. Chọn nhóm $\{3, 4\}$ được 7 điểm, nhóm còn lại $\{1, 2, 5\}$ được 8 điểm, chênh lệch chỉ 1 – không thể bằng 0 vì tổng 15 là số lẻ. In 7 8.

Lời mở đầu

Đề hơi "lủng củng" một chút (quà loại 1, loại 2, "tổng các môn"...) nhưng ý chính rất rõ: chia $N$ học sinh thành 2 nhóm, số người hai nhóm chênh nhau không quá 1, sao cho tổng điểm hai nhóm chênh nhau ít nhất, rồi in tổng điểm 2 nhóm theo thứ tự tăng dần. Đây là bài cái túi quen thuộc, nhưng có thêm một chiều: phải đếm số người trong nhóm. Mình sẽ đi đủ 3 nấc: đệ quy thử hết → quy hoạch động bảng → tăng tốc bằng bitset, và chạy thật cả 3 cách trên bộ test của CLUE.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test3 subtaskÝ tưởngdp[j][s]Cách 1Đệ quyCách 2QHĐ bảngCách 3Bitset 100%

Bộ testBộ test chính thức có gì?

Test	$N$	Điểm mỗi bạn	Điểm lớn nhất	Tổng điểm lớn nhất	Chênh lệch đáp án lớn nhất
1–20	5 … 17	Các số ngẫu nhiên nhỏ (≤ 20)	20	178	2
21–40	99	Ngẫu nhiên 1 … 600	598	12.117	1
41–60	99	Tất cả bằng nhau	600	59.400	600
61–80	299	Ngẫu nhiên 1 … 600	600	36.538	1
81–100	299	Tất cả bằng nhau	600	179.400	600

• 100 test, khớp đúng 3 subtask của đề: test 1–20 có $N \le 17$, test 21–60 có $N = 99$, test 61–100 có $N = 299$ (đều là số lẻ, nên luôn có một nhóm đông hơn nhóm kia 1 người).
• Mỗi mức $N$ có 2 kiểu test: điểm ngẫu nhiên, và tất cả các bạn bằng điểm nhau. Kiểu "bằng nhau" là kiểu nặng nhất cho quy hoạch động vì tổng điểm lên tới $299 \cdot 600 = 179\,400$; khi đó đáp án lệch đúng 1 bạn (ví dụ test 100: 89400 90000).
• Với điểm ngẫu nhiên, hai nhóm gần như luôn chia được lệch 0 hoặc 1 điểm.

Ba subtask và số test đúng của từng cách (chạy thật):

Subtask	Điều kiện	Các test	Cách 1 đệ quy	Cách 2 QHĐ bảng	Cách 3 bitset
1 (20%)	$N \le 20$	1 – 20	20/20	20/20	20/20
2 (40%)	$N \le 100$	21 – 60	0/40	40/40	40/40
3 (40%)	$N \le 300$	61 – 100	0/40	28/40	40/40

(Số test đúng của bản C++, chạy thật với giới hạn 2 giây/test.)

Ý tưởngChỉ cần quan tâm một nhóm

Gọi $tong$ là tổng điểm cả lớp, $k = \lfloor N/2 \rfloor$. Hai nhóm chênh nhau không quá 1 người nên một nhóm có đúng $k$ người, nhóm kia có $N - k$ người (khi $N$ chẵn thì hai nhóm bằng nhau). Nếu nhóm $k$ người có tổng điểm $s$ thì nhóm kia có $tong - s$, chênh lệch là

|s − (tong − s)| = |tong − 2s|

Vậy bài toán chỉ còn: trong các tổng $s$ có thể tạo được bằng cách chọn đúng $k$ bạn, tìm $s$ gần $tong/2$ nhất. Đến đây có 2 hướng: thử hết mọi cách chọn $k$ bạn (cách 1), hoặc lập bảng đánh dấu "tổng nào chọn được" (cách 2, 3):

Trạng thái quy hoạch động

$dp[j][s]$ = true nếu chọn được $j$ bạn (trong các bạn đã xét) có tổng điểm đúng bằng $s$.
Xét thêm bạn có điểm $x$: bạn này hoặc không được chọn (bảng giữ nguyên), hoặc được chọn – khi đó mọi trạng thái $(j-1, s)$ đang true sinh ra trạng thái $(j, s + x)$:

dp[j][s] = dp[j][s] OR dp[j − 1][s − x]

Ban đầu chỉ có $dp[0][0]$ = true (chọn 0 bạn, tổng 0). Xét xong cả $N$ bạn, nhìn hàng $j = k$ để chọn $s$.

Em nhập điểm các bạn rồi bấm Tiếp: mỗi bước là "thêm 1 bạn vào hàng $j$". Ô xanh dương là ô nguồn ở hàng $j - 1$, ô vàng là ô vừa được bật ở hàng $j$ (dịch sang phải đúng $x$ cột):

Điểm các bạn

Ví dụ nhanh:

Cách 1Đệ quy thử mọi cách chọn k bạn (subtask 1)

Với từng bạn, ta có 2 lựa chọn: cho vào nhóm 1 hoặc nhóm 2. Hàm Try(i, cnt, s) đang xét bạn thứ $i$, đã chọn $cnt$ bạn vào nhóm 1 với tổng $s$. Khi đủ $k$ bạn thì tính chênh lệch và cập nhật kỷ lục. Có thêm 1 dòng cắt nhánh: nếu số bạn còn lại không đủ để chọn cho đủ $k$ bạn thì quay lui luôn.

C++▶ Chạy tay từng dòng codeCách 1: Try(i, cnt, s) chọn / bỏ từng bạn, đủ k bạn thì tính chênh lệch.

Dữ liệu vào (stdin) – sửa thoải mái5 3 1 2 5 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Khung "Ngăn xếp lời gọi" cho thấy đang ở tầng đệ quy nào, mỗi tầng đang đi nhánh chọn hay bỏ.

Không gian$O(N)$ (độ sâu đệ quy)

Thời gian$O\left(\binom{N}{N/2}\right)$

Kết quả chạy thật: bản C++ đúng 20/100 test, quá thời gian ở các test 21–100; test đúng chạy lâu nhất 0,004 s. Số cách chọn là $\binom{N}{N/2}$: với $N = 17$ chỉ $\binom{17}{8} = 24\,310$, nhưng với $N = 99$ đã là $\binom{99}{49} \approx 5 \cdot 10^{28}$ – chạy đến hết đời cũng không xong. Bản Python (dùng itertools.combinations) đúng 20/40 test, quá thời gian ở các test 21–40; test đúng chạy lâu nhất 0,021 s (mình chỉ chạy thử 40 test đầu).

Cách 2Quy hoạch động bảng dp[j][s] (subtask 1, 2)

Cài đặt đúng công thức ở phần ý tưởng. Đầy đủ thì trạng thái có 3 chiều $dp[i][j][s]$ (xét $i$ bạn đầu, chọn $j$ bạn, tổng $s$), nhưng hàng $i$ chỉ phụ thuộc hàng $i - 1$ nên ta bỏ chiều $i$ đi, giống bài cái túi 0/1 quen thuộc.

C++▶ Chạy tay từng dòng codeCách 2: bảng dp[j][s] true/false, j giảm dần như cái túi 0/1.

Dữ liệu vào (stdin) – sửa thoải mái4 2 7 4 1

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Mỗi bước của vòng s dừng ở dòng if (gộp với dòng for). Ô xanh dương: dp[j − 1][s − a[i]] đang đọc, ô có viền cam: dp[j][s] đang xét, ô vàng: vừa bật.

1. Vì sao $j$ phải giảm dần? Khi cập nhật $dp[j]$ ta đọc $dp[j-1]$. Nếu $j$ tăng dần thì $dp[j-1]$ có thể vừa được bật bởi chính bạn $i$ → bạn $i$ bị chọn 2 lần. Đi từ $j$ lớn xuống thì $dp[j-1]$ vẫn là giá trị "trước khi xét bạn $i$". (Vòng $s$ đi xuôi hay ngược đều được vì $dp[j]$ và $dp[j-1]$ là 2 hàng khác nhau.)
2. $j$ chỉ cần chạy tới $\min(i, k)$: xét $i$ bạn thì không thể chọn quá $i$ bạn, và ta không cần nhóm quá $k$ người.
3. Bảng bool dp[155][180005] chiếm khoảng 27 MB, nằm trong giới hạn 256 MB.

Không gian$O(N \cdot S)$ với $S$ = tổng điểm

Thời gian$O(N \cdot \frac{N}{2} \cdot S)$

Kết quả chạy thật: bản C++ đúng 88/100 test, quá thời gian ở các test 81–83, 85–86, 89–90, 92, 94, 96–97, 100; test đúng chạy lâu nhất 1,653 s. Với $N = 99$: $99 \cdot 49 \cdot 59\,400 \approx 2{,}9 \cdot 10^8$ phép tính, vẫn kịp. Với $N = 299$ và các test "bằng điểm nhau" (tổng tới $179\,400$): $299 \cdot 149 \cdot 179\,400 \approx 8 \cdot 10^9$ – quá 2 giây. Một số test ở mức này vẫn qua vì tổng điểm nhỏ hơn nhiều.

Cách 3Tăng tốc bằng bitset (full điểm)

Nhìn kỹ vòng lặp trong cùng của cách 2: với mỗi $s$, nếu bit $s - x$ của hàng $j-1$ bật thì bật bit $s$ của hàng $j$. Nói cách khác: lấy cả hàng $j - 1$, dịch sang phải $x$ vị trí, rồi OR vào hàng $j$. Nếu lưu mỗi hàng là một bitset, phép dịch + OR này máy làm 64 bit một lúc, nên vòng $s$ nhanh hơn khoảng 64 lần:

dp[j] |= dp[j − 1] << x

(<< trên bitset dịch bit $s$ thành bit $s + x$ – chính là "chọn thêm bạn có $x$ điểm".)

C++▶ Chạy tay từng dòng codeCách 3: mỗi hàng là 1 bitset, cả vòng s thay bằng 1 lệnh dịch bit rồi OR.

Dữ liệu vào (stdin) – sửa thoải mái5 3 1 2 5 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Mỗi lần chạy dòng dp[j] |= ... là cả một hàng được cập nhật cùng lúc – ô vàng là các bit vừa bật.

Không gian$O(N \cdot S / 8)$ byte

Thời gian$O(N \cdot \frac{N}{2} \cdot S / 64)$

Kết quả chạy thật: bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0,229 s. Bản Python dùng số nguyên lớn của Python làm bitset (phép << và | trên số nguyên lớn cũng xử lý theo từng khối bit nên rất nhanh) đúng 100/100 test; test đúng chạy lâu nhất 0,197 s.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Ghi chú
1. Đệ quy thử mọi cách chọn	C++	20/100	0,004 s	Quá thời gian ở test 21–100
	Python (test 1–40)	20/40	0,021 s	Quá thời gian ở test 21–40
2. QHĐ bảng dp[j][s]	C++	88/100	1,653 s	Quá thời gian ở test 81–83, 85–86, 89–90, 92, 94, 96–97, 100
3. QHĐ + bitset	C++	100/100	0,229 s	Full điểm
	Python	100/100	0,197 s	Full điểm

Ghi chú của mình: cả 3 cách đều được chấm trên đủ 100 test của CLUE (bản Python vét cạn chỉ chạy thử test 1–40). Đệ quy chỉ ăn subtask 1; quy hoạch động bảng ăn thêm subtask 2 và một phần subtask 3; muốn trọn điểm phải dùng bitset (hoặc số nguyên lớn trong Python). Bài học: khi trạng thái QHĐ là true/false và công thức chỉ là "dịch rồi OR", hãy nghĩ ngay tới bitset.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇