Trộn xâu

Nguồn: CLUE OJ – Chương 22: Quy hoạch động (VNOJ) Độ khó: Khá Quy hoạch động 2 chiều Đệ quy có nhớ

Đề bài

Cho 2 xâu ký tự $X = x_1, x_2, \ldots, x_m$ và $Y = y_1, y_2, \ldots, y_n$. Cần xây dựng xâu $T = t_1, t_2, t_3, \ldots, t_{n+m}$ gồm tất cả các ký tự trong xâu $X$ và tất cả các ký tự trong xâu $Y$, sao cho các ký tự trong $X$ xuất hiện trong $T$ theo thứ tự xuất hiện trong $X$ và các ký tự trong $Y$ xuất hiện trong $T$ theo đúng thứ tự xuất hiện trong $Y$, đồng thời với tổng chi phí trộn là nhỏ nhất. Tổng chi phí trộn hai xâu $X$ và $Y$ để thu được xâu $T$ được tính bởi công thức $c(T) = \sum_{k=1}^{n+m-1} c(t_k, t_{k+1})$; trong đó, các chi phí $c(t_k, t_{k+1})$ được tính như sau:

• Nếu hai ký tự liên tiếp $t_k, t_{k+1}$ được lấy từ cùng một xâu $X$ hoặc $Y$ thì $c(t_k, t_{k+1}) = 0$.
• Nếu hai ký tự liên tiếp $t_k, t_{k+1}$ là $x_i, y_j$ thì chi phí phải trả là $c(x_i, y_j)$. Nếu hai ký tự liên tiếp $t_k, t_{k+1}$ là $y_j, x_i$ thì chi phí phải trả là $c(y_j, x_i) = c(x_i, y_j)$.

Input

Dòng đầu tiên chứa $Q$ là số lượng bộ dữ liệu, tiếp đến là $Q$ $(Q \le 10)$ nhóm dòng, mỗi nhóm cho thông tin về 1 bộ dữ liệu theo khuôn dạng sau:

• Dòng thứ nhất chứa 2 số nguyên dương $m, n$ $(m, n \le 1000)$;
• Dòng thứ $i$ trong $m$ dòng tiếp theo chứa $n$ số nguyên dương, mỗi số không vượt quá $10^9$: $c(x_i, y_1),$ $c(x_i, y_2),$ $\ldots,$ $c(x_i, y_n)$, $i = 1, 2, \ldots, m$.

Output

• Gồm $Q$ dòng, mỗi dòng chứa một số nguyên là tổng chi phí theo cách xây dựng xâu $T$ tìm được tương ứng với bộ dữ liệu vào.

Giới hạn: có 60% số test ứng với 60% số điểm của bài có $m, n \le 10$.

Ví dụ – input

1
2 3
3 2 30
15 5 4

Ví dụ – output

6

Giải thích ví dụ: $m = 2$, $n = 3$, bảng chi phí $c(x_1, \cdot) = 3, 2, 30$ và $c(x_2, \cdot) = 15, 5, 4$. Chọn $T = y_1\, y_2\, x_1\, x_2\, y_3$: chỉ có 2 chỗ "đổi xâu" là $y_2 \to x_1$ (tốn $c(x_1, y_2) = 2$) và $x_2 \to y_3$ (tốn $c(x_2, y_3) = 4$), tổng $2 + 4 = 6$. Để ý rằng trộn đơn giản "hết $X$ rồi tới $Y$" ($x_1 x_2 y_1 y_2 y_3$) tốn $c(x_2, y_1) = 15$ – đắt hơn dù chỉ đổi xâu 1 lần.

Lời mở đầu

Bài toán này là ví dụ rất đẹp cho con đường kinh điển của chương Quy hoạch động: viết hàm quay lui thử mọi cách trộn → nhận ra hàm đó bị gọi lặp lại với cùng tham số nên thêm bảng nhớ (đệ quy có nhớ) → viết lại thành QHĐ bảng chạy từ nhỏ đến lớn. Cả 3 bước mình đều chạy thật trên bộ test để các bạn thấy rõ hiệu quả của từng bước.

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ộ test2 subtaskCách 1Quay lui 60%Cách 2Có nhớ 100%Ý tưởngBảng dpCách 3QHĐ 100%

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

Test	$Q$	$m$	$n$	Chi phí lớn nhất	Đáp án
1–20	1	5–10	5–10	9	1 … 4
21–60	1	5–10	5–10	999.512.175	101.817.132 … 569.406.371
61–80	1	109–288	134–295	999.999.889	111.965.898 … 298.790.097
81–100	1	826–1.000	815–1.000	999.999.958	113.058.920 … 245.764.083

Tất cả 100 test đều chỉ có $Q = 1$ bộ dữ liệu. 60 test đầu có $m, n \le 10$ đúng như 60% của đề (20 test đầu chi phí chỉ từ 1 đến 9, 40 test sau chi phí tới $10^9$). 40 test còn lại lớn dần: test 61–80 có $m, n$ khoảng 100–300, test 81–100 có $m, n$ từ 815 đến 1000 – mỗi test phải đọc tới $10^6$ số. Giới hạn thời gian của bài là 5 giây.

Subtask	Điều kiện	Test	Cách 1 (quay lui)	Cách 2 (đệ quy có nhớ)	Cách 3 (QHĐ bảng)
1 (60%)	$m, n \le 10$	1–60	qua	qua	qua
2 (40%)	$m, n \le 1000$	61–100	quá thời gian	qua	qua

Cách 1Quay lui thử mọi cách trộn (subtask 1)

Xây $T$ từ trái sang phải. Tại mỗi bước, trạng thái gồm: đã đặt $i$ ký tự đầu của $X$, $j$ ký tự đầu của $Y$, và ký tự cuối cùng của $T$ là $x_i$ (last = 0) hay $y_j$ (last = 1). Bước tiếp theo chỉ có 2 lựa chọn:

• Đặt $x_{i+1}$: nếu ký tự cuối đang là $y_j$ thì phải trả $c(x_{i+1}, y_j)$, còn nếu đang là $x_i$ thì miễn phí.
• Đặt $y_{j+1}$: nếu ký tự cuối đang là $x_i$ thì phải trả $c(x_i, y_{j+1})$, ngược lại miễn phí.

Ký tự đầu tiên của $T$ là $x_1$ hoặc $y_1$, nên mình gọi hàm 2 lần từ main. Số cách trộn là $\binom{m+n}{m}$ – với $m = n = 10$ là $184\,756$ cách, chạy rất nhanh; nhưng với $m = n = 100$ con số này đã khoảng $9 \cdot 10^{58}$.

C++▶ Chạy tay từng dòng codeCách 1: Try(i, j, last, cost) thử đặt x tiếp theo hoặc y tiếp theo.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Phía trên là xâu T đang xây (số đỏ là chi phí đổi xâu); ô vàng trong bảng c là chi phí vừa phải trả.

Không gian$O(m + n)$ (độ sâu đệ quy)

Thời gian$O\left(\binom{m+n}{m}\right)$ mỗi bộ dữ liệu

Kết quả chạy thật: bản C++ đúng 60/100 test – trọn 60% điểm của subtask $m, n \le 10$. Cả 40 test còn lại đều quá thời gian (mình để chạy tới 9–16 giây máy vẫn chưa xong thì bị dừng). Bản Python cũng qua 60 test đầu, chậm nhất 0,11 giây.

Cách 2Đệ quy có nhớ (full điểm)

Nhìn kỹ hàm quay lui: phần việc còn lại chỉ phụ thuộc vào bộ ba $(i, j, last)$, không phụ thuộc vào đường đi để tới đó. Nhưng có rất nhiều đường đi khác nhau cùng dẫn tới một bộ ba – cách 1 giải đi giải lại cùng một bài toán con. Ta đổi hàm thành trả về giá trị:

F(i, j, last) = chi phí nhỏ nhất để đặt nốt phần còn lại

$$F(i, j, last) = \min\Big(F(i+1, j, 0) + [last = 1] \cdot c_{i+1, j},\ \ F(i, j+1, 1) + [last = 0] \cdot c_{i, j+1}\Big), \qquad F(m, n, \cdot) = 0$$ (mỗi nhánh chỉ có khi còn ký tự để đặt). Đáp án: $\min\big(F(1, 0, 0),\ F(0, 1, 1)\big)$.

Chỉ có $(m+1)(n+1) \cdot 2 \approx 2 \cdot 10^6$ bộ ba khác nhau, nên ta lưu kết quả vào mảng memo: lần đầu tính xong thì ghi lại, lần sau gặp lại thì trả về ngay.

C++▶ Chạy tay từng dòng codeCách 2: F(i, j, last) trả về chi phí nhỏ nhất cho phần còn lại, nhớ kết quả vào memo.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Ô xanh lá trong bảng memo là lúc lấy lại kết quả đã tính – chỗ tiết kiệm so với cách 1.

1. long long &res = memo[i][j][last]; – res là "tên gọi khác" của ô nhớ, gán res = ... là ghi thẳng vào bảng.
2. memo = -1 đánh dấu "chưa tính" – an toàn vì chi phí luôn $\ge 0$.
3. Độ sâu đệ quy tối đa $m + n \le 2000$ tầng – không lo tràn ngăn xếp. Mảng c và memo khoảng 8 + 16 MB, khai báo toàn cục.

Không gian$O(m \cdot n)$

Thời gian$O(m \cdot n)$

Kết quả chạy thật: đúng 100/100 test, chậm nhất 0,10 giây (test $m = n = 1000$) – rất xa giới hạn 5 giây. Phần lớn thời gian là để đọc $10^6$ số.

Ý tưởng bảngLật ngược: QHĐ từ đầu xâu

Đệ quy có nhớ đã đủ điểm, nhưng mình muốn viết thêm phiên bản QHĐ bảng chạy bằng vòng lặp (không đệ quy – cũng là cách để viết bản Python chạy nhanh). Lần này định nghĩa theo phần đã xây thay vì phần còn lại:

Trạng thái và công thức

$dp[i][j][0]$ = chi phí nhỏ nhất để trộn $x_1..x_i$ với $y_1..y_j$ mà ký tự cuối là $x_i$;
$dp[i][j][1]$ = như trên nhưng ký tự cuối là $y_j$. $$dp[i][j][0] = \min\big(dp[i-1][j][0],\ \ dp[i-1][j][1] + c_{i,j}\big)$$ $$dp[i][j][1] = \min\big(dp[i][j-1][1],\ \ dp[i][j-1][0] + c_{i,j}\big)$$ Biên: $dp[i][0][0] = 0$ (chỉ toàn $X$), $dp[0][j][1] = 0$ (chỉ toàn $Y$), các trạng thái không tồn tại bằng $\infty$. Đáp án $\min(dp[m][n][0], dp[m][n][1])$.

Giải thích công thức đầu: ký tự cuối là $x_i$, ký tự đứng ngay trước nó là $x_{i-1}$ (miễn phí) hoặc $y_j$ (phải trả $c_{i,j}$). Điểm đẹp: cả hai lần đổi xâu đều tốn đúng $c_{i,j}$ – chi phí của cặp $(x_i, y_j)$ đứng cạnh nhau.

Em nhập bảng chi phí (mỗi dòng của $c$ cách nhau bởi dấu ;) rồi bấm Tiếp. Mỗi ô $(i, j)$ ghi 2 số: X = $dp[i][j][0]$ và Y = $dp[i][j][1]$. Bước cuối mình lần ngược để dựng lại xâu $T$ tối ưu:

ô đang tínhgiá trị được dùng tớiô chi phí c(x_i, y_j)đường lần ngược

Bảng c (dòng cách nhau bởi ;)

Ví dụ nhanh:

Cách 3QHĐ bảng 3 chiều (full điểm)

C++▶ Chạy tay từng dòng codeCách 3: điền bảng dp[i][j][0..1] theo thứ tự i tăng, j tăng.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Thứ tự duyệt $i$ tăng, $j$ tăng đảm bảo $dp[i-1][j]$ và $dp[i][j-1]$ đã có trước khi tính $dp[i][j]$.
2. INF = LLONG_MAX / 4 để phép INF + c[i][j] không bị tràn số.
3. Bản Python mình chỉ giữ 2 hàng (hàng $i-1$ và hàng $i$) và đọc từng hàng của $c$ khi cần, nên tốn ít bộ nhớ và chạy nhanh hơn hẳn.

Không gian$O(m \cdot n)$

Thời gian$O(m \cdot n)$

Kết quả chạy thật: đúng 100/100 test, chậm nhất 0,09 giây. Bản Python (chỉ giữ 2 hàng) cũng đúng 100/100, chậm nhất 0,38 giây.

Ghi chú của mình: Cách 1 (quay lui) 60/100; cách 2 (đệ quy có nhớ) và cách 3 (QHĐ bảng) đều 100/100, chậm nhất khoảng 0,1 giây; bản Python của cách 3 cũng 100/100 (0,38 giây). Dù đáp án trong bộ test đều dưới $10^9$, tổng chi phí trên một đường trộn có thể lên tới $1999 \cdot 10^9$ nên mình vẫn dùng long long cho chắc.

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 😇