Thay đổi giá trị (Tin học trẻ toàn quốc 2025 – Vòng chung kết toàn quốc – Bảng C2)

Nguồn: Tin học trẻ toàn quốc 2025 – Chung kết – Bảng C2 Độ khó: Khó Cái túi Lập luận đổi chỗ

Đề bài

🏆

Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng chung kết toàn quốc – Bảng C2. Đề dưới đây mình viết lại theo lời của mình cho dễ hiểu, giữ nguyên ý nghĩa, giới hạn và ví dụ của đề gốc.

Alice là một kỹ sư phần mềm mê đồ công nghệ. Dịp giảm giá cuối năm, cô ghé cửa hàng có $N$ món hàng: món thứ $i$ có nhãn giá $a_i$ (số tiền phải trả) và độ hấp dẫn $b_i$. Alice có đúng $M$ đồng và muốn chọn mua một nhóm món có tổng độ hấp dẫn lớn nhất, với tổng tiền phải trả không vượt quá $M$.

Điều đặc biệt: trước khi thanh toán, Alice được gỡ nhãn giá của không quá $K$ món, rồi dán lại các nhãn này lên chính các món đó theo thứ tự tuỳ ý (mỗi món trong nhóm nhận đúng một nhãn của nhóm). Giá của mỗi món thay đổi theo nhãn mới, còn độ hấp dẫn thì giữ nguyên.

Hỏi nếu tận dụng tối đa việc tráo nhãn này, tổng độ hấp dẫn lớn nhất Alice mua được là bao nhiêu?

Dữ liệu vào: dòng đầu là số bộ dữ liệu $T$ $(1 \le T \le 1000)$. Mỗi bộ gồm:

Dòng 1: ba số $N, M, K$ $(1 \le N \le 5000,\ 1 \le M \le 2 \cdot 10^4,\ 0 \le K \le N)$;
Dòng 2: $N$ số $a_1, \ldots, a_N$ $(1 \le a_i \le 2 \cdot 10^4)$;
Dòng 3: $N$ số $b_1, \ldots, b_N$ $(1 \le b_i \le 10^9)$.

Gọi $S_N$ là tổng các giá trị $N$ của mọi bộ dữ liệu, đảm bảo $S_N \le 5000$.

Kết quả: $T$ dòng, mỗi dòng là tổng độ hấp dẫn lớn nhất của bộ dữ liệu tương ứng.

Subtask:

Subtask 1 ($20\%$): $N, T \le 10$.
Subtask 2 ($20\%$): $S_N \le 200$, $K = 0$.
Subtask 3 ($20\%$): $S_N \le 200$, $K \le 10$.
Subtask 4 ($20\%$): $S_N \le 200$, $K \le 100$.
Subtask 5 ($20\%$): không có ràng buộc gì thêm.

Giới hạn thời gian: 2 giây, bộ nhớ 512 MB. Dữ liệu nhập từ bàn phím, in ra màn hình.

Ví dụ – input

Ví dụ – output

Giải thích: Alice gỡ nhãn của món 1 (giá 3) và món 3 (giá 6) rồi dán đổi chỗ cho nhau. Món 3 giờ chỉ còn giá 3; cô mua món 2 và món 3 với tổng giá $5 + 3 = 8 \le 10$, được độ hấp dẫn $20 + 15 = 35$.

Lời mở đầu

Đây là bài khó nhất bảng C2 vòng chung kết: một bài cái túi (knapsack) quen thuộc nhưng có thêm "phép thuật" tráo nhãn. Chìa khoá là mô hình hoá lại việc tráo nhãn thành các "vai" của từng món, rồi dùng lập luận đổi chỗ (exchange argument) để thu hẹp dạng của phương án tối ưu. Mình sẽ đi từ vét cạn → cái túi thường → QHĐ 2 giai đoạn (80% điểm) → lời giải đầy đủ $O(N \cdot M + N^2)$.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

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ộ test26 test Ý tưởngvai Cách 1vét cạn Cách 2cái túi Cách 3O(NKM)Cách 42 dạng

Bộ testBộ test có gì?

Bộ test trên CLUE gồm 26 test (mình tự sinh theo đúng ràng buộc và tỉ lệ subtask của đề), mỗi test có thể chứa nhiều bộ dữ liệu:

Nhóm	Test	$T$	$S_N$ lớn nhất	$N$ lớn nhất	$K$	$M$ lớn nhất	Đáp án lớn nhất
Subtask 1 (20%)	1–5	1 – 10	100	10	0 – 10	20.000	2.797.895.294
Subtask 2 (20%)	6–10	1 – 50	200	200	0 – 0	20.000	31.198.120.659
Subtask 3 (20%)	11–15	1 – 40	200	200	0 – 10	20.000	29.111.650.702
Subtask 4 (20%)	16–20	1 – 30	200	200	0 – 100	20.000	39.747.761.780
Subtask 5 (20%)	21–26	1 – 1.000	5.000	5.000	0 – 5.000	20.000	1.236.201.216.287

Test 1 là ví dụ của đề. Subtask 5 có test $N = 5000$ với $K = 3$, $K = 1999$, $K = N = 5000$, test $T = 1000$ bộ nhỏ, và các test $K$ rất lớn.
Đáp án tới hơn $10^{12}$ (tổng của hàng nghìn số $b_i \le 10^9$) – phải dùng long long.
Ở các test $K$ lớn, tráo nhãn giúp mua được rất nhiều món: bỏ qua việc tráo nhãn là sai ngay.

Kết quả chạy thật của 4 cách (C++) theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 vét cạn	Cách 2 cái túi thường	Cách 3 QHĐ 2 giai đoạn	Cách 4 2 dạng
Subtask 1 (20%)	$N, T \le 10$	1–5	qua	trượt	qua	qua
Subtask 2 (20%)	$S_N \le 200$, $K = 0$	6–10	1/5 test	qua	qua	qua
Subtask 3 (20%)	$S_N \le 200$, $K \le 10$	11–15	quá thời gian	trượt	qua	qua
Subtask 4 (20%)	$S_N \le 200$, $K \le 100$	16–20	quá thời gian	trượt	qua	qua
Subtask 5 (20%)	không ràng buộc thêm	21–26	quá thời gian	trượt	2/6 test	qua

Lời giải cách 4 (C++) mình đã nộp thử trên hệ thống chấm chính thức của hội thi (tinhoctre.vn) và đạt AC 100/100 điểm.

Ý tưởngTráo nhãn = các "cặp đổi", mỗi món một vai

Tráo nhãn trong một nhóm có lợi thế nào? Gọi $G$ là nhóm bị gỡ nhãn. Các món trong $G$ mà Alice mua nên nhận những nhãn rẻ nhất của $G$. Nhãn đắt của chúng được dán sang các món trong $G$ mà Alice không mua. Vậy mỗi lần "đổi" là một cặp: một món được mua đem nhãn đắt của mình đổi lấy nhãn rẻ của một món không mua. Mỗi cặp dùng 2 món của nhóm nên có tối đa $H = \lfloor K/2 \rfloor$ cặp. (Với cùng tập món mua $S$, cách tốt nhất là ghép món mua đắt thứ $i$ với món không mua rẻ thứ $i$, chừng nào còn có lợi.)

Từ đó mỗi món sẽ đóng đúng một trong 4 vai:

Vai	Ý nghĩa	Trả tiền nhãn của nó?	Được độ hấp dẫn?
Mua	mua với nhãn của chính nó	có ($a_i$)	có ($b_i$)
Góp nhãn	không mua, nhưng nhãn rẻ của nó được dán sang món khác	có ($a_i$)	không
Miễn phí	mua, nhưng nhãn của nó đã đổi đi	không	có ($b_i$)
Bỏ	không liên quan	không	không

Bài toán mới

Gán vai cho các món sao cho số món "góp nhãn" = số món "miễn phí" = $t \le H$, tổng $a$ của các món "mua" và "góp nhãn" không quá $M$; tối đa hoá tổng $b$ của các món "mua" và "miễn phí".

Nhận xét 1 (đổi chỗ). Sắp xếp các món theo $a$ tăng dần. Có phương án tối ưu mà mọi món "góp nhãn" đứng trước mọi món "miễn phí". Thật vậy, nếu món góp nhãn $p$ đắt hơn món miễn phí $s$ ($a_p > a_s$) thì cho $s$ thành "mua", $p$ thành "bỏ": tiền thay đổi $a_s - a_p < 0$, độ hấp dẫn giữ nguyên, lại bớt một cặp – không thiệt gì. (Hiển nhiên thôi: đổi nhãn đắt lấy nhãn còn đắt hơn thì chẳng ai làm.)

Em nhập một ví dụ nhỏ rồi bấm Tiếp: khung dưới vét cạn tìm phương án tốt nhất, sắp xếp theo giá rồi tô màu vai của từng món – em sẽ thấy các ô cam (góp nhãn) luôn đứng trước các ô tím (miễn phí):

N M K a: b:

Ví dụ nhanh:

Cách 1Vét cạn tập món mua – subtask 1

Với $N \le 10$: duyệt mọi tập $S$ các món mua ($2^N$ tập). Với mỗi tập, chi phí ban đầu là tổng $a$ của $S$; sắp nhãn của các món mua giảm dần, nhãn các món không mua tăng dần, rồi tráo tối đa $H$ cặp đầu tiên khi có lợi (nhãn món mua đắt hơn).

C++▶ Chạy tay từng dòng codeCách 1: duyệt mọi tập món mua, tráo tối đa K/2 cặp nhãn có lợi, kiểm tra ngân sách.

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

Dữ liệu mẫu:

Phần chia món vào in/out và sắp xếp được gộp mỗi phần thành 1 bước.

Không gian$O(N)$

Thời gian$O(2^N \cdot N \log N)$ mỗi bộ

Kết quả chạy thật (mình chỉ chạy test 1–10 vì $N$ lớn thì $2^N$ là không tưởng – thậm chí 1 << n bị tràn khi $n \ge 31$): bản C++ đúng 6/26 test – sai kết quả test 6–9 (test đúng chạy lâu nhất 0,038 giây); mình chỉ chạy thử test 1–10, các test còn lại chắc chắn quá thời gian. Bản Python đúng 6/26 test – quá thời gian test 6–9 (test đúng chạy lâu nhất 0,410 giây); mình chỉ chạy thử test 1–10, các test còn lại chắc chắn quá thời gian. Qua trọn subtask 1 (và test 10 của subtask 2 vì các bộ ở đó có $N \le 16$).

Cách 2Cái túi 0/1 thường – subtask 2

Khi $K = 0$ (hoặc $K = 1$: một món thì chẳng tráo được với ai) bài toán chính là cái túi 0/1 kinh điển: $dp[m]$ = tổng độ hấp dẫn lớn nhất với tổng giá $\le m$; mỗi món duyệt $m$ từ lớn xuống nhỏ.

C++▶ Chạy tay từng dòng codeCách 2: cái túi 0/1 – dp[m] là tổng độ hấp dẫn lớn nhất với tổng giá ≤ m (không tráo nhãn).

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

Dữ liệu mẫu:

Không gian$O(M)$

Thời gian$O(N \cdot M)$

Kết quả chạy thật: bản C++ đúng 5/26 test – sai kết quả test 1–5, 11–26 (test đúng chạy lâu nhất 0,004 giây). Bản Python (dùng numpy cập nhật cả mảng dp một lúc) đúng 5/26 test – sai kết quả test 1–5, 11–26 (test đúng chạy lâu nhất 0,151 giây). Đúng trọn subtask 2 và sai mọi test có tráo nhãn – đúng như dự đoán.

Cách 3QHĐ hai giai đoạn – O(N·K·M)

Dùng nhận xét 1: duyệt các món theo $a$ tăng dần, chia làm hai giai đoạn – giai đoạn 1 chỉ dùng các vai "mua / góp nhãn / bỏ", giai đoạn 2 chỉ dùng "mua / miễn phí / bỏ". Ta được chọn thời điểm chuyển giai đoạn (trước bất kỳ món nào).

$f[c][m]$: đang ở giai đoạn 1, đã có $c$ món góp nhãn, tổng nhãn đã trả $\le m$ → tổng độ hấp dẫn lớn nhất.
$g[c][m]$: đang ở giai đoạn 2, còn $c$ món miễn phí "được nợ" (bằng số món góp nhãn trừ số món miễn phí đã lấy).
Món $(w, v)$: $f[c][m] \leftarrow \max(f[c][m - w] + v$ (mua)$,\ f[c-1][m - w]$ (góp nhãn)$)$; $g[c][m] \leftarrow \max(g[c][m-w] + v$ (mua)$,\ g[c+1][m] + v$ (miễn phí)$)$.
Đáp án: $\max(f[0][M], g[0][M])$ – số món góp nhãn và miễn phí phải bằng nhau.

C++▶ Chạy tay từng dòng codeCách 3: QHĐ 2 giai đoạn trên các món đã sắp theo giá – f (mua / góp nhãn), g (mua / miễn phí).

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

Dữ liệu mẫu:

Mỗi ô (c, m) có 2 bước (2 lựa chọn); bước "g = max(g, f)" gộp cả hai vòng lặp. Ví dụ đề khoảng 250 bước – em bấm Tự chạy nhé.

Thứ tự duyệt giống cái túi 0/1: $m$ giảm dần để mỗi món chỉ dùng một lần; ở $f$ duyệt $c$ giảm dần (vì $f[c]$ lấy từ $f[c-1]$ cũ), ở $g$ duyệt $c$ tăng dần (vì $g[c]$ lấy từ $g[c+1]$ cũ, cùng $m$).
Bảng có $(H + 1) \times (M + 1)$ ô, mỗi món cập nhật cả bảng: $O(N \cdot H \cdot M)$.

Không gian$O(K \cdot M)$

Thời gian$O(N \cdot K \cdot M)$

Kết quả chạy thật: bản C++ đúng 22/26 test, chậm nhất 0,957 giây; mình chỉ chạy thử test 1–21, 24, các test còn lại chắc chắn quá thời gian. Bản Python (numpy) đúng 21/26 test – quá thời gian test 16 (test đúng chạy lâu nhất 1,566 giây); mình chỉ chạy thử test 1–21, 24, các test còn lại chắc chắn quá thời gian. Cách 3 qua trọn subtask 1 – 4 (80% điểm), và cả test 21 ($K = 3$) lẫn test 24 của subtask 5. Với các test $K$ hàng nghìn, chỉ riêng bảng $f, g$ đã cần tới hàng trăm MB và $N \cdot H \cdot M$ lên tới $10^{11}$ – không thể chạy kịp.

Cách 4Hai dạng phương án tối ưu – O(N·M + N²)

Ta "ép" phương án tối ưu thêm nữa bằng lập luận đổi chỗ (vẫn sắp $a$ tăng dần, bằng giá thì $b$ giảm dần). Gọi "được trả nhãn" là vai mua hoặc góp nhãn.

Dạng A – còn dư lượt tráo ($t < H$): các món được trả nhãn là một tiền tố $[1..s]$. Nếu có món $u$ không được trả nhãn đứng trước món $v$ được trả nhãn ($a_u \le a_v$), ta luôn sửa được mà không thiệt: $u$ "bỏ", $v$ "góp nhãn" → đổi vai cho nhau; $u$ "bỏ", $v$ "mua" → $u$ góp nhãn, $v$ miễn phí (dùng thêm 1 lượt tráo – được vì còn dư); $u$ "miễn phí", $v$ "mua" → đổi vai cho nhau. Lặp lại tới khi các món được trả nhãn là một tiền tố, hoặc đã dùng hết $H$ lượt (sang dạng B). Với tiền tố $[1..s]$ cố định, giá trị là $\sum_{i \le s} b_i$, rồi lần lượt đổi món có $b$ nhỏ nhất trong tiền tố (thành góp nhãn) lấy món có $b$ lớn nhất ngoài tiền tố (thành miễn phí), chừng nào còn có lợi và chưa quá $H$ cặp.

Dạng B – dùng đủ $H$ lượt ($t = H$). Gọi $p$ là vị trí món góp nhãn cuối cùng, $q$ là vị trí món miễn phí đầu tiên ($p < q$ theo nhận xét 1).

Trước $p$ không có món "bỏ" (nếu có, cho nó góp nhãn thay món ở $p$ – rẻ hơn). Vậy tiền tố $[1..p]$ được trả nhãn hết, chi phí đúng $C_p = a_1 + \ldots + a_p$, và $H$ món góp nhãn nên là $H$ món có $b$ nhỏ nhất trong tiền tố: giá trị $SB_p - \text{botK}[p]$.
Sau $q$ không có món "mua" (nếu có, đổi vai với món miễn phí ở $q$ – rẻ hơn). Vậy hậu tố $[q..N]$ chỉ gồm miễn phí và bỏ: lấy $H$ món có $b$ lớn nhất – giá trị $\text{topK}[q]$.
Đoạn giữa $(p, q)$ chỉ có "mua" và "bỏ": đúng là cái túi 0/1 thường với ngân sách $M - C_p$.

Tính dạng B gọn trong $O(N \cdot M)$ bằng mẹo QHĐ nhiều điểm xuất phát: một mảng $L[m]$ duy nhất, duyệt $i = 0..N$:

Thêm món $i$ vào cái túi: $L[m] = \max(L[m], L[m - a_i] + b_i)$ – món $i$ thuộc đoạn giữa.
"Mở" điểm xuất phát $p = i$: $L[m] = \max(L[m], SB_i - \text{botK}[i])$ với mọi $m \ge C_i$.
Cập nhật đáp án với hậu tố bắt đầu từ $q = i + 1$: $L[M] + \text{topK}[i+1]$.

Vì phép "thêm món vào cái túi" giống hệt nhau với mọi điểm xuất phát, gộp tất cả vào một mảng (lấy max) vẫn đúng. $\text{botK}, \text{topK}$ tính bằng hàng đợi ưu tiên giữ $H$ số nhỏ nhất / lớn nhất. Dạng A tính trong $O(N^2)$ bằng cách duy trì hai danh sách đã sắp xếp. Đáp án là max của cả hai dạng (mỗi giá trị tính ra đều là một phương án hợp lệ, nên lấy max không bao giờ vượt quá đáp án thật).

C++▶ Chạy tay từng dòng codeCách 4: dạng A (trả nhãn một tiền tố) + dạng B (đủ H cặp: tiền tố bắt buộc + cái túi đoạn giữa + hậu tố miễn phí).

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

Dữ liệu mẫu:

Mỗi vòng heap tính botK/topK và mỗi lần cập nhật cái túi cho một món được gộp thành 1 bước.

Dạng A: khi $s$ tăng, món $s$ chuyển từ hậu tố sang tiền tố: chèn vào pre (tăng dần), xoá khỏi suf (giảm dần). Vòng for t cộng các hiệu suf[t] - pre[t] khi còn dương – hiệu này giảm dần nên dừng ở hiệu đầu tiên không dương.
Dạng B chỉ làm khi $2H \le N$ (cần đủ $H$ món góp nhãn và $H$ món miễn phí). Với $H = 0$: botK, topK đều bằng 0 và dạng B chính là cái túi thường – nên cách 4 cũng tự xử lý $K \le 1$.
Giá trị "không hợp lệ" là NEG = LLONG_MIN / 4 (đủ âm, cộng thêm vẫn không tràn).

Không gian$O(N + M)$

Thời gian$O(N \cdot M + N^2)$

Kết quả chạy thật: bản C++ đúng 26/26 test, chậm nhất 0,092 giây. Bản Python (numpy cho phần cái túi) đúng 26/26 test, chậm nhất 0,642 giây. Ngoài bộ test, mình còn đối chiếu cách 4 với cách 1 (vét cạn) và cách 3 trên 300 bộ ngẫu nhiên nhỏ – khớp hoàn toàn.

Tổng kếtKết quả

Cách	C++	Python
1. Vét cạn $2^N$	6/26 test	6/26 test
2. Cái túi thường (bỏ qua tráo nhãn)	5/26 test	5/26 test
3. QHĐ hai giai đoạn $O(NKM)$	22/26 test	21/26 test
4. Hai dạng $O(NM + N^2)$	26/26 test	26/26 test

Ghi chú của mình: cách 3 đã đủ 80% số điểm và chỉ cần một nhận xét đổi chỗ đơn giản – trong phòng thi đây là mục tiêu rất đáng làm. Cách 4 (C++ chậm nhất 0,092 giây trên giới hạn 2 giây) cần thêm hai nhận xét đổi chỗ nữa để biết phương án tối ưu chỉ có hai dạng; bản C++ của cách này đã đạt 100 điểm trên hệ thống chấm chính thức. Bài học: với bài tối ưu có "phép biến đổi" lạ, hãy mô hình hoá thành vai của từng phần tử rồi sắp xếp + đổi chỗ để thu hẹp không gian tìm kiếm.

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 😇

Lập Trình Thuật Toán