Cakes (Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Nam – Bảng B, C1, C2)

Nguồn: Tin học trẻ 2025 Độ khó: Khá Quy hoạch động Floyd Cửa sổ trượt

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Nam – Bảng B, Bảng C1 và Bảng C2 (bài Cakes). Đề bên dưới do mình viết lại bằng lời của mình cho dễ hiểu (giữ đúng nghĩa, đúng số liệu và ví dụ của đề gốc).

Alice có $N$ chiếc bánh xếp thành một hàng, mỗi chiếc thuộc một trong $T$ loại (đánh số $1..T$). Một dãy bánh gọi là đẹp nếu mọi đoạn liên tiếp dài nhất gồm các bánh cùng loại đều có độ dài ít nhất $K$.

Alice muốn đổi loại bánh ở một số vị trí để dãy trở nên đẹp. Mỗi lần đổi một chiếc bánh từ loại $i$ sang loại $j$ tốn chi phí $C_{i,j}$. Một chiếc bánh có thể được đổi nhiều lần liên tiếp (ví dụ $i \to k$ rồi $k \to j$), khi đó chi phí là tổng các lần đổi; giữ nguyên loại thì không tốn gì.

Yêu cầu: tìm tổng chi phí nhỏ nhất để biến dãy ban đầu thành dãy đẹp.

Dữ liệu vào:

Dòng 1: ba số nguyên $N, T, K$ ($1 \le N, K \le 10^5$; $1 \le T \le 100$).
$T$ dòng tiếp theo: dòng thứ $i$ gồm $T$ số nguyên không âm $C_{i,1}, C_{i,2}, \dots, C_{i,T}$ ($C_{i,j} \le 10^6$).
Dòng cuối: $N$ số nguyên $A_1, A_2, \dots, A_N$ ($1 \le A_i \le T$) – loại của từng chiếc bánh.

Kết quả: một số nguyên là chi phí nhỏ nhất.

Subtask:

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

Giới hạn thời gian: 1 giây. 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: dãy ban đầu là 1 2 2 1 1, cần mọi khối cùng loại dài ít nhất $K = 2$ – hiện tại đã đẹp rồi? Chưa! Khối 1 đầu tiên chỉ dài 1. Đổi hai bánh ở vị trí 2 và 3 từ loại 2 sang loại 1, mỗi chiếc tốn $C_{2,1} = 1$, được dãy 1 1 1 1 1 (một khối dài 5) với tổng chi phí $2$.

Lời mở đầu

Bài này có một câu chuyện thú vị mà mình muốn kể trước: lần đầu làm, mình hiểu đề là "đổi bánh loại $i$ sang loại $j$ thì tốn đúng $C_{i,j}$" (đổi trực tiếp một lần), viết quy hoạch động đúng hoàn toàn theo cách hiểu đó, nộp lên bộ chấm chính thức và chỉ được… 4 điểm. Đọc lại đề gốc mới thấy chữ "chi phí mỗi lần thay đổi" – tức là một chiếc bánh được đổi nhiều lần, và đổi $i \to k \to j$ có thể rẻ hơn đổi thẳng $i \to j$! Thêm đúng 5 dòng thuật toán Floyd vào đầu chương trình, nộp lại: 100 điểm. Bài học: đọc kỹ từng chữ của đề.

Phần còn lại của bài là một bài quy hoạch động "chia dãy thành các khối" kinh điển, mình đi từ $O(N^2 T)$ (50 điểm) tới $O(NT)$ (full).

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ộ test20 test Bẫy đềđổi nhiều bước Ý tưởngchia khối Cách 1O(N²T) – 50đ Cách 2O(NT) – 100đ Tổng kếtkết quả

Bộ testBộ test có gì?

Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ subtask của đề: 20 test (test 1 là ví dụ của đề). Trong mọi test, $C_{i,i} = 0$ và luôn có $K \le N$.

Nhóm	Test	$N$ lớn nhất	$T$ lớn nhất	Các giá trị $K$	Test có "đổi nhiều bước" rẻ hơn đổi trực tiếp	Đáp án lớn nhất
Subtask 1	1–4	100	20	2, 7, 13, 100	test 2, 4	90.000.000
Subtask 2	5–8	100.000	100	2	test 5, 7–8	33.334.000.000
Subtask 3	9–14	500	100	1, 3, 17, 37, 251, 500	test 9, 11–13	489.000.000
Subtask 4	15–20	100.000	100	3, 77, 317, 1.000, 50.001, 100.000	test 16–18	98.922.000.000

Có tới 12/20 test mà ma trận $C$ có ít nhất một cặp $(i, j)$ "đổi vòng" rẻ hơn đổi thẳng – đây là các test bắt lỗi hiểu sai đề.

Đã nộp thử trên bộ chấm chính thức

Lời giải cuối cùng (cách 2, có Floyd) mình đã nộp lên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được 100/100 điểm (AC). Bản đổi trực tiếp (không Floyd) trước đó chỉ được 4 điểm.

Kết quả chạy thật các cách bên dưới theo từng subtask:

Subtask	Điều kiện	Test	Đổi trực tiếp (hiểu sai đề)	Cách 1 $O(N^2 T)$	Cách 2 $O(NT)$ C++	Cách 2 Python
Subtask 1 (20%)	$N, K \le 100$; $T \le 20$	1–4	2/4	4/4	4/4	4/4
Subtask 2 (20%)	$K = 2$	5–8	1/4	0/4	4/4	0/4
Subtask 3 (30%)	$N, K \le 500$	9–14	3/6	6/6	6/6	6/6
Subtask 4 (30%)	không ràng buộc thêm	15–20	3/6	1/6	6/6	1/6

Bẫy đềĐổi nhiều bước – chạy Floyd trước

Xét ví dụ $T = 3$ với ma trận chi phí:

$C_{i,j}$	sang 1	sang 2	sang 3
từ 1	0	9	2
từ 2	9	0	9
từ 3	9	1	0

Đổi thẳng bánh loại 1 sang loại 2 tốn 9, nhưng đổi $1 \to 3$ (tốn 2) rồi $3 \to 2$ (tốn 1) chỉ tốn 3. Vì đề cho phép đổi nhiều lần, chi phí thật để đổi $i$ thành $j$ là đường đi ngắn nhất từ đỉnh $i$ tới đỉnh $j$ trên đồ thị $T$ đỉnh, cạnh $i \to j$ có trọng số $C_{i,j}$. Với $T \le 100$ thì thuật toán Floyd $O(T^3) = 10^6$ phép tính là quá đủ:

for(int i = 1; i <= T; i++) c[i][i] = 0;
for(int k = 1; k <= T; k++)
    for(int i = 1; i <= T; i++)
        for(int j = 1; j <= T; j++)
            c[i][j] = min(c[i][j], c[i][k] + c[k][j]);

Dòng c[i][i] = 0 thể hiện "giữ nguyên loại thì không tốn gì" (trong bộ test $C_{i,i}$ luôn bằng 0, nhưng gán lại cho chắc).
Vòng k (đỉnh trung gian) phải nằm ngoài cùng – đặt sai chỗ là Floyd sai.

Sau bước này, mọi chỗ trong lời giải chỉ việc dùng c[x][y] như "chi phí đổi bánh loại $x$ thành loại $y$". Nếu bỏ 5 dòng này (đổi trực tiếp), quy hoạch động bên dưới vẫn chạy nhưng cho đáp án lớn hơn đáp án đúng: trên bộ test của mình, bản đó chỉ đúng 9/20 test, sai test 2, 4–5, 7–8, 11–13, 16–18 (các test đúng chạy lâu nhất 0.054s) – mất cả subtask 1, 2, 3, 4 (chỉ còn đúng các test mà Floyd không làm thay đổi gì). Đúng như bộ chấm chính thức chấm cho mình 4 điểm!

Ý tưởngChia dãy thành các khối dài ít nhất K

Dãy đẹp chính là dãy được chia thành các khối liên tiếp, mỗi khối dài ít nhất $K$ và mọi bánh trong khối cùng một loại. (Hai khối kề nhau cùng loại cũng không sao – ghép lại vẫn là một khối dài $\ge K$.) Mỗi khối $(l, i]$ đổi hết thành loại $j$ tốn:

$$\text{cost}(l, i, j) = \sum_{t = l+1}^{i} c[A_t][j].$$

Gọi $dp[i]$ = chi phí nhỏ nhất để đoạn đầu $1..i$ trở thành đẹp (khối cuối kết thúc đúng tại $i$). Khi đó $dp[0] = 0$ và:

$$dp[i] = \min_{0 \le l \le i - K} \ \min_{1 \le j \le T} \Big( dp[l] + \text{cost}(l, i, j) \Big).$$

Đáp án là $dp[N]$. Em nhập dữ liệu rồi bấm Tiếp để xem $dp$ được tính dần (mỗi ô màu là một chiếc bánh, màu = loại bánh; cuối cùng hiện cách đổi tốt nhất):

K = C (hàng cách nhau bởi ;) = Dãy A =

Ví dụ nhanh:

Cách 1QHĐ thẳng theo công thức – O(N²T) (Subtask 1, 3)

Để tính nhanh $\text{cost}(l, i, j)$, dùng mảng cộng dồn $pre[j][i]$ $= \sum_{t=1}^{i} c[A_t][j]$, khi đó $\text{cost}(l, i, j)$ $= pre[j][i] - pre[j][l]$. Ba vòng lặp lồng nhau $i$, $l$, $j$ cho đúng công thức.

C++▶ Chạy tay từng dòng codeCách 1: Floyd, rồi dp[i] = min theo l và j của dp[l] + chi phí đổi khối (l, i] thành loại j.

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

Dữ liệu mẫu:

dp[l] == INF nghĩa là đoạn $1..l$ không thể đẹp (ví dụ $0 < l < K$) nên bỏ qua.
Đề không nói chuyện $K > N$ (khi đó không có cách nào); bộ test không có trường hợp này, mình vẫn in -1 cho chắc.
Đáp án có thể tới $10^5 \cdot 10^6 \cdot$ (vài bước) – vượt int, dùng long long.

Không gian$O(NT + T^2)$

Thời gian$O(T^3 + N^2 T)$

Kết quả chạy thật: Bản C++ đúng 11/20 test, quá thời gian test 5–8, 16–20 (các test đúng chạy lâu nhất 0.079s) → 50 điểm (subtask 1 và 3). Với $N = 500$: $\frac{500^2}{2} \cdot 100 \approx 1{,}25 \cdot 10^7$ phép tính – rất nhanh; nhưng $N = 10^5$ thì $5 \cdot 10^{11}$ – quá xa. Test 15 vẫn qua vì $K = N$ nên chỉ có $l = 0$.

Cách 2Gộp vòng lặp l vào mảng val – O(NT) (full)

Nhìn kỹ công thức, với mỗi loại $j$ đặt

$$val_i[j] = \min_{0 \le l \le i - K} \Big( dp[l] + \text{cost}(l, i, j) \Big)$$

thì $dp[i] = \min_j val_i[j]$. Khi chuyển từ $i - 1$ sang $i$, ta cập nhật $val[j]$ trong $O(1)$:

Kéo dài mọi khối cũ thêm bánh $i$: mỗi giá trị $dp[l] + \text{cost}(l, i-1, j)$ đều cộng thêm đúng $c[A_i][j]$ → val[j] += c[a[i]][j].
Thêm lựa chọn mới $l = i - K$ (khối mới dài đúng $K$): val[j] = min(val[j], dp[i-K] + win[j]), với $win[j]$ = chi phí đổi $K$ bánh cuối $(i-K, i]$ thành loại $j$, duy trì bằng cửa sổ trượt: thêm bánh $i$, bỏ bánh $i - K$.

C++▶ Chạy tay từng dòng codeCách 2: Floyd, rồi duy trì val[j] (khối cuối loại j đang được kéo dài) và win[j] (cửa sổ K bánh cuối).

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

Dữ liệu mẫu:

Thứ tự trong vòng $i$: cập nhật win và kéo dài val trước, rồi mới thêm lựa chọn $l = i - K$ (cửa sổ lúc này đúng là $(i-K, i]$).
Không cộng vào val[j] khi nó còn là INF để tránh "INF + số" bị tràn hoặc thành giá trị giả.
Tổng cộng: Floyd $O(T^3) = 10^6$, vòng chính $O(NT) = 10^7$ – chạy khoảng 0,05 giây.

Không gian$O(N + T^2)$

Thời gian$O(T^3 + NT)$

Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.051s. Full điểm. Bản Python đúng 11/20 test, quá thời gian test 5–8, 15–19 (các test đúng chạy lâu nhất 0.144s) – Python làm $10^7$ phép tính trên danh sách mất khoảng 3 giây nên chỉ qua các test nhỏ (subtask 1, 3); đây là bài nên dùng C++.

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)	Điểm theo subtask
Đổi trực tiếp, không Floyd (hiểu sai đề)	C++	9/20	0.054s	0%
1. Floyd + QHĐ $O(N^2 T)$	C++	11/20	0.079s	50%
2. Floyd + QHĐ $O(N T)$	C++	20/20	0.051s	100%
	Python	11/20	0.144s	50%

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình (giới hạn 1 giây). Hai bài học: (1) đọc kỹ đề – một chữ "mỗi lần" biến bài từ 4 điểm thành 100 điểm, và khi chi phí "đổi" có thể đi qua trung gian thì hãy nghĩ ngay tới đường đi ngắn nhất; (2) với QHĐ dạng $\min_{l \le i-K}(dp[l] + \text{tổng đoạn})$, hãy thử gộp vòng lặp $l$ bằng một mảng "giá trị tốt nhất đang được kéo dài" – từ $O(N^2)$ xuống $O(N)$.

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