Xử lí chuỗi sinh học (Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Bắc & miền Trung – Bảng C1)
Đề bài
Alice có một xâu $S$ mô tả một đoạn ADN (chỉ gồm chữ cái thường a–z, các kí tự đánh số từ 0) và một tập $n$ mẫu $w_1, w_2, \dots, w_n$; mẫu $w_i$ có trọng số $p_i > 0$.
Mỗi khi một mẫu $w_i$ xuất hiện như một đoạn con liên tiếp trong xâu hiện tại, Alice được phép trích xuất nó: xoá đoạn đó khỏi xâu, nối phần bên trái và bên phải lại với nhau, và nhận được lợi ích $p_i$. Cứ thế lặp lại cho tới khi trong xâu không còn mẫu nào.
Yêu cầu: đưa ra một chiến lược trích xuất có tổng lợi ích lớn nhất.
Dữ liệu vào:
- Dòng 1: xâu $S$ ($|S| \le 1000$).
- Dòng 2: số nguyên $n$ ($n \le 3000$).
- $n$ dòng sau: dòng thứ $i$ gồm xâu $w_i$ (dài không quá 30, chỉ gồm
a–z) và số nguyên $p_i$ ($0 < p_i \le 10^4$).
Kết quả: dòng đầu là số thao tác $k$; $k$ dòng sau, mỗi dòng hai số $L\ R$: thao tác đó xoá các kí tự từ vị trí $L$ tới $R$ của xâu hiện tại (đánh số từ 0), đoạn này phải trùng với một mẫu.
Chấm điểm: gọi $s$ là tổng lợi ích của em, $d$ là kết quả của Ban giám khảo. Nếu $d - s \le 100$ thì em được $0{,}95^{\max(0,\ d - s)}$ số điểm của test, ngược lại được 0 điểm.
Subtask: Subtask 1 (40%): $|S| \le 100$. Subtask 2 (60%): $|S| \le 1000$.
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.
abbaa
3
bb 5
aaa 1
ba 42
2 3
1 2Giải thích: xoá đoạn $[2, 3]$ = ba của abbaa được 4, xâu còn aba; xoá tiếp đoạn $[1, 2]$ = ba được thêm 4, xâu còn a. Tổng lợi ích 8. Nếu tham lam xoá bb (5 điểm) trước thì xâu còn aaa, chỉ được thêm 1 – tổng 6.
Lời mở đầu
Đây là bài khó nhất của vòng khu vực miền Bắc & miền Trung bảng C1. Ví dụ đã cho thấy tham lam không ăn thua: xoá một mẫu có thể làm hai mảnh xa nhau "dính" lại thành mẫu mới. Ta cần một quy hoạch động trên đoạn của xâu gốc, kết hợp với trie để duyệt nhiều mẫu cùng lúc. Mình sẽ đi từ vét cạn, tới QHĐ đoạn cơ bản, rồi tới bản có tỉa nhánh chạy kịp $|S| = 1000$, $n = 3000$. Mình cũng kể thật về kết quả nộp trên trang chấm chính thức: Cách 3 được 60 điểm, Cách 4 được 90 điểm.
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test có gì?
Bộ test của mình có 20 test (giống bộ trên CLUE): test 1–8 thuộc subtask 1 ($|S| \le 100$), test 9–20 thuộc subtask 2 ($|S|$ = 1000). Có nhiều chiến lược tối ưu khác nhau nên bài chấm bằng trình chấm: mô phỏng lại các thao tác của em (đoạn $[L, R]$ phải trùng một mẫu), tính $s$ rồi cho điểm theo công thức $0{,}95^{d-s}$. Các mẫu trùng nhau thì trình chấm lấy trọng số lớn nhất.
| Test | $|S|$ | Số loại kí tự | $n$ mẫu (khác nhau) | Độ dài mẫu | Trọng số | Lợi ích tối ưu | Số thao tác |
|---|---|---|---|---|---|---|---|
| 1 | 5 | 2 | 3 (3) | 2 – 3 | 1 – 5 | 8 | 2 |
| 2 | 1 | 1 | 2 (2) | 1 – 2 | 3 – 7 | 0 | 0 |
| 3 | 100 | 2 | 3000 (2148) | 1 – 30 | 1 – 9.999 | 989.856 | 100 |
| 4 | 100 | 4 | 50 (46) | 2 – 6 | 606 – 1.968 | 32.768 | 43 |
| 5 | 100 | 3 | 200 (113) | 2 – 5 | 1 – 10 | 429 | 50 |
| 6 | 100 | 26 | 3000 (2253) | 1 – 30 | 2 – 9.999 | 781.431 | 96 |
| 7 | 97 | 2 | 40 (29) | 2 – 8 | 216 – 9.530 | 406.755 | 48 |
| 8 | 100 | 4 | 300 (233) | 1 – 10 | 300 – 3.320 | 33.251 | 48 |
| 9 | 1000 | 26 | 3000 (2862) | 1 – 30 | 1 – 10.000 | 7.627.481 | 933 |
| 10 | 1000 | 4 | 3000 (2721) | 1 – 30 | 2 – 9.998 | 9.585.188 | 1000 |
| 11 | 1000 | 4 | 3000 (2793) | 2 – 30 | 4 – 9.997 | 4.767.068 | 500 |
| 12 | 1000 | 2 | 3000 (2458) | 2 – 30 | 2 – 9.996 | 4.903.202 | 500 |
| 13 | 1000 | 26 | 3000 (2985) | 2 – 30 | 5 – 9.993 | 1.281.327 | 204 |
| 14 | 1000 | 3 | 1500 (1043) | 1 – 12 | 1 – 10 | 10.000 | 1000 |
| 15 | 1000 | 2 | 3000 (2391) | 1 – 30 | 300 – 9.990 | 333.000 | 475 |
| 16 | 1000 | 4 | 3000 (998) | 1 – 30 | 2 – 9.998 | 9.866.600 | 1000 |
| 17 | 1000 | 4 | 3000 (1196) | 2 – 30 | 12 – 9.998 | 4.747.887 | 500 |
| 18 | 1000 | 26 | 1500 (1453) | 3 – 30 | 16 – 9.998 | 946.710 | 133 |
| 19 | 1000 | 4 | 3000 (2811) | 2 – 30 | 1 – 10.000 | 4.893.298 | 500 |
| 20 | 1000 | 2 | 1 (1) | 1 – 1 | 6.748 – 6.748 | 3.427.984 | 508 |
- Có test với bảng chữ cái rất nhỏ (2–4 kí tự, kiểu ADN
acgt) và 3000 mẫu dài tới 30: các mẫu chồng chéo nhau dày đặc – đây là các test "nặng" nhất. - Có test nhiều mẫu trùng nhau (cột số mẫu khác nhau nhỏ hơn $n$), test chỉ có 1 mẫu, test mẫu toàn là đoạn con của $S$ (26 chữ cái).
Kết quả chạy thật của 3 cách bên dưới theo từng subtask (đáp án được trình chấm kiểm tra, "qua" nghĩa là đạt đúng lợi ích tối ưu):
| Subtask | Điều kiện | Test | Cách 1 vét cạn | Cách 2 QHĐ đoạn cơ bản | Cách 3 QHĐ đoạn + tỉa | Cách 4 + cận, dự phòng |
|---|---|---|---|---|---|---|
| Subtask 1 (40%) | $|S| \le 100$ | 1–8 | 2/8 test | 7/8 test | qua | qua |
| Subtask 2 (60%) | $|S| \le 1000$ | 9–20 | 0/12 test | 1/12 test | qua | qua |
- Cách 3 (bài nộp 3039) chỉ được 60 điểm: quá thời gian các test 19–24, 26–30 và sai test 25. Trên bộ test của mình nó chạy dưới nửa giây, nhưng máy chấm chính thức chậm hơn máy mình khoảng 1,5–2 lần và bộ test chính thức có những test nặng hơn bộ của mình.
- Cách 4 (cùng thuật toán, thêm tỉa bằng cận trên/cận dưới, tối ưu hằng số và dự phòng thời gian khi sắp hết giờ) được 90 điểm: sai 3 test 19, 24, 25. Mình đã thử thêm 5 biến thể theo các cách hiểu khác nhau của đề – mẫu trùng nhau lấy trọng số lần đầu / lần cuối / cộng dồn, dùng số 64 bit phòng tràn, tắt hẳn phần dự phòng thời gian – tất cả đều đúng 90 điểm, sai đúng 3 test đó.
Ý tưởngNhìn các thao tác trên xâu gốc
Đánh dấu mỗi kí tự bằng vị trí của nó trong xâu gốc $S$. Một thao tác xoá một đoạn liên tiếp của xâu hiện tại – nhưng trên xâu gốc, đó là các vị trí $i_1 < i_2 < \dots < i_m$ mà mọi kí tự nằm giữa chúng đã bị xoá trước đó. Ở ví dụ: thao tác 1 xoá vị trí gốc $\{2, 3\}$, thao tác 2 xoá vị trí gốc $\{1, 4\}$ – "khe" $[2, 3]$ ở giữa đã được dọn sạch từ trước.
Từ đó định nghĩa hai bảng trên các đoạn $[l, r]$ của xâu gốc:
- $full[l][r]$ = lợi ích lớn nhất để xoá sạch đoạn $S[l..r]$ chỉ bằng các thao tác nằm gọn trong đoạn (bằng $-\infty$ nếu không xoá sạch được).
- $prim[l][r]$ = như trên, nhưng thao tác cuối cùng xoá một mẫu chứa cả $S[l]$ lẫn $S[r]$: mẫu $w$ khớp ở các vị trí $l = i_1 < \dots < i_m = r$ ($S[i_j] = w_j$), mỗi khe giữa hai vị trí liên tiếp được xoá sạch trước: $$prim[l][r] = \max_{w,\ i_1..i_m}\Big(p(w) + \sum_{\text{khe}} full[\text{khe}]\Big).$$
Xét thao tác xoá kí tự $S[l]$ trong một cách xoá sạch $[l, r]$; mẫu của nó kết thúc ở vị trí gốc $m$. Phần $[l, m]$ được xoá hết bởi thao tác đó cùng các khe, phần $[m+1, r]$ phải được xoá sạch độc lập (một thao tác không thể "vắt" qua $m$ vì vị trí $m$ chỉ biến mất ở thao tác cuối của $[l, m]$). Vậy: $$full[l][r] = \max\Big(prim[l][r],\ \max_{l \le m < r} prim[l][m] + full[m+1][r]\Big).$$
Cuối cùng, các kí tự không bị xoá chia xâu thành các đoạn được xoá sạch rời nhau, nên đáp án là QHĐ trên tiền tố: $best[i]$ $= \max(best[i-1],\ \max_l best[l] + full[l][i-1])$. Vì mọi trọng số dương nên xâu còn lại của lời giải tối ưu chắc chắn không còn mẫu nào (còn thì xoá thêm sẽ được lợi hơn). Truy vết từ các bảng sẽ ra dãy thao tác: khe nào cũng xoá trước, mẫu "bao ngoài" xoá sau.
Em nhập xâu và các mẫu (dạng mẫu:trọng_số) rồi bấm Tiếp để xem bảng $full$ được điền từ dưới lên (hàng $l$ giảm dần), sau đó là dãy thao tác truy vết được:
Cách 1Vét cạn, nhớ theo xâu hiện tại
Hàm $f(s)$ = lợi ích lớn nhất thu được từ xâu hiện tại $s$: thử mọi mẫu, mọi vị trí xuất hiện, xoá rồi gọi đệ quy; lưu kết quả vào map theo chính xâu $s$ để không tính lại. Truy vết: từ $S$, mỗi lần chọn một thao tác $t$ có $p + f(t) = f(s)$.
Kết quả chạy thật: bản C++ đúng 2/20 test, quá thời gian test 3–20; các test đúng chạy lâu nhất 0,003 giây. Bản Python đúng 2/20 test, quá thời gian test 3–20; các test đúng chạy lâu nhất 0,019 giây.
Số xâu con có thể sinh ra tăng theo cấp số mũ, nên chỉ test 1, 2 (xâu dài 5 và 1) chạy được. Lưu ý quá thời gian là 0 điểm – công thức $0{,}95^{d-s}$ chỉ cứu được khi em in ra kịp một chiến lược gần tối ưu.
Cách 2QHĐ đoạn + duyệt trie từ mỗi vị trí l
Tính $prim[l][\ast]$ cho mọi $r$ cùng lúc: đi từ $S[l]$ trên trie của các mẫu. Trạng thái $(u, p, g)$: đã khớp tiền tố mẫu ứng với nút $u$, kí tự khớp sau cùng ở vị trí $p$, lợi ích các khe đã xoá là $g$. Từ đó khớp kí tự tiếp theo ở vị trí $q > p$ nếu khe $[p+1, q-1]$ rỗng hoặc xoá sạch được ($full[p+1][q-1] \ge 0$ – đã biết vì $p + 1 > l$) và trie có cạnh $S[q]$ từ $u$. Gặp nút là cuối một mẫu thì cập nhật $prim[l][p]$.
- Duyệt $l$ giảm dần, nên mọi $full[x][\ast]$ với $x > l$ đã có.
- Các trạng thái được xử lí theo "tầng" (độ dài tiền tố); trạng thái trùng $(u, q)$ chỉ giữ lợi ích lớn nhất (cùng nút cha để truy vết).
okEnd[x]lưu các $y$ mà $S[x..y]$ xoá sạch được – chỉ duyệt các khe hợp lệ thay vì mọi $q$.
Kết quả chạy thật: bản C++ đúng 8/20 test, quá thời gian test 3, 9–19; các test đúng chạy lâu nhất 0,091 giây.
Cách này đúng (mình đã đối chiếu với vét cạn trên 1500 test ngẫu nhiên nhỏ) nhưng số trạng thái bùng nổ khi bảng chữ cái nhỏ và mẫu dày: test 3 ($|S| = 100$, chỉ 2 loại kí tự, 3000 mẫu) đã quá thời gian, và hầu hết subtask 2 cũng vậy.
Cách 3Thêm tỉa nhánh: mẫu bị trội và trạng thái bị trội
Hai nhận xét giúp bỏ đi phần lớn công việc mà không làm mất đáp án tối ưu:
- Mẫu bị trội. Nếu bản thân xâu $w$ xoá sạch được bằng các mẫu ngắn hơn với tổng lợi ích $\ge p(w)$ thì mỗi lần xoá $w$ ta thay bằng dãy thao tác đó, không thiệt gì → bỏ hẳn $w$. Kiểm tra bằng chính bộ giải trên xâu $w$ (dài $\le 30$), xét mẫu theo độ dài tăng dần. Với bảng chữ cái nhỏ, hầu hết mẫu dài bị loại ở bước này.
- Trạng thái bị trội. Gom các trạng thái cùng nút $u$ theo vị trí tăng dần. Gọi $R[q]$ = lợi ích tốt nhất để "đứng ở nút $u$, sắp khớp $S[q]$" (tức $\max g + full[\text{khe}]$). Trạng thái $(u, p, g)$ với $x = p + 1$ mà đã có $R[x] \ge g$ thì vô dụng: mọi thứ nó tạo ra, trạng thái trước tạo được với lợi ích không nhỏ hơn (vì hai đoạn xoá sạch nối nhau vẫn xoá sạch, lợi ích cộng lại).
Thêm vài kỹ thuật cài đặt: mảng R tính theo hàng liền nhau (máy vectơ hoá được nhờ #pragma GCC optimize("O3")), chỉ quét các vị trí có kí tự là con của $u$ (mảng nxt), dùng danh sách khe theo kí tự kế tiếp (okBy) khi số khe hợp lệ ít, và lưu lại trạng thái của từng $l$ để truy vết khỏi phải chạy lại.
Kết quả chạy thật: bản C++ đúng 20/20 test; các test đúng chạy lâu nhất 0,461 giây. Bản Python đúng 11/20 test, quá thời gian test 9, 11–13, 15–19; các test đúng chạy lâu nhất 0,644 giây.
Bản C++ đạt lợi ích tối ưu ở cả 20 test, chậm nhất chưa tới nửa giây. Mình cũng đối chiếu Cách 3 với vét cạn (1500 test nhỏ) và với Cách 2 (400 test $|S| \le 70$): khớp hết. Bản Python cùng thuật toán chỉ kịp subtask 1 và vài test lớn "dễ".
Nhưng trên trang chấm chính thức, bản C++ này (bài nộp 3039) chỉ được 60 điểm: quá thời gian 11 test (19–24, 26–30) và sai test 25. Bộ test chính thức nặng hơn bộ của mình, máy chấm lại chậm hơn – nên cần thêm tỉa và một "lưới an toàn" về thời gian, đó là Cách 4.
Cách 4Thêm cận trên/cận dưới, tối ưu hằng số và dự phòng thời gian
Đây là bản mình nộp được 90 điểm (điểm cao nhất của mình ở bài này). Thuật toán vẫn là QHĐ đoạn của Cách 3, thêm:
- Tỉa bằng cận (tỉa 3). $B[x][r]$ = lợi ích lớn nhất của các thao tác nằm gọn trong $[x, r-1]$ (không bắt buộc xoá sạch) – một cận trên. $LB[r]$ = một cận dưới của $full[l][r]$, lấy từ các lượt duyệt nhanh chỉ cho phép khe dài $\le 2, 12, 48$ (lượt sau được tỉa bằng cận của lượt trước). Trạng thái $(u, x, g)$ bị bỏ nếu với mọi $r$: $g + ext{maxBelow}(u)$ $+ B[x][r] < LB[r]$ – mọi $prim$ sinh ra từ nó đều nhỏ hơn hẳn $full$ nên không bao giờ được dùng.
- Tối ưu hằng số: nén bảng chữ cái về các kí tự có trong $S$, trie dạng mảng phẳng, chọn giữa duyệt thưa (danh sách khe theo kí tự kế tiếp) và duyệt dày (cập nhật cả hàng – dùng lệnh AVX2 nếu CPU hỗ trợ, kiểm tra lúc chạy).
- Dự phòng thời gian: đếm giờ bằng
clock(); nếu tới 0,85 giây vẫn chưa xong thì bỏ, chạy lại với khe dài tối đa 8 (gần đúng, nhanh hơn nhiều); tới 0,92 giây vẫn chưa xong thì chạy với khe 0 (chỉ xoá các mẫu đứng liền). Như vậy luôn in kịp một chiến lược hợp lệ, và nhờ công thức $0{,}95^{d-s}$ vẫn có điểm nếu kết quả gần tối ưu. - Đọc dữ liệu "chịu lỗi" (cả dòng, bỏ
\r, kí tự lạ), cuối cùng xoá tham lam mọi mẫu còn sót để xâu cuối chắc chắn không còn mẫu nào.
Kết quả chạy thật: bản C++ đúng 20/20 test; các test đúng chạy lâu nhất 0,409 giây. Trên bộ test của mình phần dự phòng không bao giờ phải dùng tới (mọi test đều đạt đúng tối ưu). Trên tinhoctre.vn: 90 điểm (sai test 19, 24, 25 – xem hộp ở mục Bộ test).
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. Vét cạn, nhớ theo xâu hiện tại | C++ | 2/20 | 0,003s | Quá thời gian test 3–20 |
| Python | 2/20 | 0,019s | Quá thời gian test 3–20 | |
| 2. QHĐ đoạn + duyệt trie (cơ bản) | C++ | 8/20 | 0,091s | Quá thời gian test 3, 9–19 |
| 3. QHĐ đoạn + tỉa mẫu/trạng thái bị trội | C++ | 20/20 | 0,461s | Full điểm |
| Python | 11/20 | 0,644s | Quá thời gian test 9, 11–13, 15–19 | |
| 4. Cách 3 + cận trên/dưới, tối ưu hằng số, dự phòng thời gian | C++ | 20/20 | 0,409s | Full điểm |
Nhận xét
Đăng nhận xét