Nguồn: Tin học trẻ toàn quốc 2025Độ khó: KháKiến tạoBiểu diễn nhị phân
Đề bài
Có ba bình nước đánh số 1, 2, 3; mỗi bình chứa được tối đa $V$ lít. Lúc đầu bình 1 có $v_1$ lít, bình 2 có $v_2$ lít, bình 3 có $v_3$ lít nước, với $v_1 + v_2 + v_3 < V$ (nên không bao giờ có bình bị tràn).
Người ta cần lấy ra một bình để dùng việc khác, nên phải đổ nước qua lại giữa các bình sao cho có một bình trở nên rỗng. Mỗi lượt được chọn hai bình $i \ne j$ thoả mãn $v_i \ge v_j$, rồi đổ từ bình $i$ sang bình $j$ đúng $v_j$ lít – tức là lượng nước trong bình $j$ tăng gấp đôi, còn bình $i$ giảm đi đúng lượng đó.
Yêu cầu: đưa ra một dãy các lượt đổ để cuối cùng có ít nhất một bình rỗng.
Dữ liệu vào: một dòng gồm ba số nguyên dương $v_1, v_2, v_3$.
Kết quả:
Dòng đầu ghi số nguyên dương $k$ – số lượt đổ.
$k$ dòng tiếp theo, mỗi dòng ghi hai số $i, j$: lượt đó đổ từ bình $i$ sang bình $j$.
Nếu có nhiều cách, in ra cách bất kỳ (không yêu cầu $k$ nhỏ nhất).
Subtask:
Subtask 1 (20% số điểm): $v_1, v_2, v_3 \le 100$.
Subtask 2 (20% số điểm): $v_1, v_2, v_3 \le 2000$.
Subtask 3 (60% số điểm): $v_1, v_2, v_3 \le 10^6$.
Giới hạn thời gian: 1 giây. Dữ liệu nhập từ bàn phím và in ra màn hình.
Ví dụ – input
1 2 3
Ví dụ – output
2
3 1
2 3
Giải thích: ban đầu $(v_1, v_2, v_3) = (1, 2, 3)$. Đổ từ bình 3 sang bình 1 được $(2, 2, 2)$; sau đó đổ từ bình 2 sang bình 3 được $(2, 0, 4)$ – bình 2 đã rỗng.
Lưu ý: bài có nhiều đáp án đúng, trình chấm sẽ mô phỏng các lượt đổ của em để kiểm tra (mỗi lượt phải có $i \ne j$, $v_i \ge v_j$, và cuối cùng có bình rỗng). Đáp án in ra không cần giống ví dụ. Số $V$ không có trong dữ liệu vào và không ảnh hưởng gì tới bài.
Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 3 – Bảng B (bài POUR). Đề được mình viết lại cho dễ đọc, giữ nguyên ý và số liệu.
Lời mở đầu
Đây là một bài kiến tạo rất đẹp (ý tưởng rất giống các bài toán Olympic Toán về "ba hộp bi"): đề không hỏi số, mà bắt ta tự xây dựng một dãy thao tác. Với dữ liệu nhỏ ta có thể để máy tự tìm bằng BFS; còn với $v \le 10^6$ thì cần một nhận xét toán học: viết thương ⌊b/a⌋ dưới dạng nhị phân. Mình đi lần lượt từng cách nhé.
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.
Bộ test của mình gồm 20 test, chia theo đúng tỉ lệ subtask: test 1–4 (subtask 1), 5–8 (subtask 2), 9–20 (subtask 3). Test 1 là ví dụ của đề (file đáp án mẫu là đáp án của lời giải mình, khác ví dụ nhưng đều đúng). Vì nhiều đáp án nên bộ test chấm bằng checker mô phỏng lại các lượt đổ. Lời giải cách 2 đã được nộp thử trên hệ thống chấm chính thức tinhoctre.vn và đạt 100/100 điểm.
Nhóm
Test
$v$ nhỏ nhất – lớn nhất
$k$ của cách 2 (lớn nhất)
$k$ ngắn nhất (BFS) lớn nhất
Subtask 1
1–4
1 – 100
29
7
Subtask 2
5–8
1 – 2.000
66
9
Subtask 3
9–20
1 – 1.000.000
218
12
Có các test đặc biệt: ba bình bằng nhau (1 lượt là xong), $(1, 1, 10^6)$, $(10^6, 10^6 - 1, 10^6 - 2)$, ba số Fibonacci liên tiếp $(832040, 514229, 317811)$, lũy thừa của 2, ba số nguyên tố lớn...
Cột cuối là số lượt ít nhất (BFS tìm được, chỉ với các test BFS chạy kịp). Cách 2 không tối ưu số lượt nhưng đề không yêu cầu; nó dùng nhiều nhất 218 lượt trên bộ test.
Kết quả chạy thật (chấm bằng checker) của các cách theo từng subtask:
Subtask
Điều kiện
Test
Cách 1 BFS C++
Cách 1 BFS Python
Cách 2 C++
Cách 2 Python
Subtask 1 (20%)
$v_i \le 100$
1–4
4/4
4/4
4/4
4/4
Subtask 2 (20%)
$v_i \le 2000$
5–8
4/4
4/4
4/4
4/4
Subtask 3 (60%)
$v_i \le 10^6$
9–20
5/12
5/12
12/12
12/12
Ý tưởngLàm bình nhỏ nhất nhỏ đi bằng phép chia lấy dư
Sắp xếp lại để lượng nước $A \le B \le C$ (ở các bình $a$, $b$, $c$). Nhận xét quan trọng: mọi lượt đổ vào bình $a$ đều làm $a$ gấp đôi: $A \to 2A \to 4A \to 8A \to \ldots$ Như vậy nếu đổ vào $a$ liên tiếp $L$ lần, lượng nước đổ ra ở lượt thứ $t$ ($t = 0, 1, \ldots, L-1$) là đúng $A \cdot 2^t$.
Ta muốn rút từ bình $b$ tổng cộng đúng $A \cdot q$ lít, với $q = \lfloor B / A \rfloor$ – khi đó bình $b$ chỉ còn $B \bmod A < A$, tức là giá trị nhỏ nhất giảm hẳn. Mà $q$ viết được dưới dạng nhị phân: $q = \sum 2^t$ (với các bit $t$ bằng 1). Vậy:
Một vòng của thuật toán
Duyệt các bit của $q$ từ thấp lên cao. Ở bit thứ $t$: nếu bit bằng 1 thì đổ từ $b$ sang $a$, nếu bit bằng 0 thì đổ từ $c$ sang $a$. Sau vòng này, bình $b$ còn đúng $B \bmod A$. Lặp lại (sắp xếp lại, làm vòng mới) cho tới khi có bình rỗng.
Tại sao các lượt đổ luôn hợp lệ?
Lấy từ $b$ ở bit $t$ (bit này bằng 1): trước đó $b$ đã mất $A \cdot (q \bmod 2^t)$, nên còn $B - A(q \bmod 2^t)$ $\ge A \cdot q - A(q \bmod 2^t)$ $\ge A \cdot 2^t$ = lượng nước của $a$ lúc đó ✔.
Lấy từ $c$ ở bit $t$ (bit bằng 0, và $t$ nhỏ hơn bit cao nhất $L - 1$ vì bit cao nhất luôn là 1): tổng $c$ đã đưa ra cộng lượt này không quá $A(2^{t+1} - 1) < A \cdot 2^{L-1}$ $\le A \cdot q$ $\le B$ $\le C$ ✔.
Tại sao thuật toán dừng? Mỗi vòng, giá trị nhỏ nhất trong ba bình giảm thực sự (bình $b$ còn $B \bmod A < A$), mà nó là số nguyên không âm nên sau hữu hạn vòng phải về 0. Trên thực tế số vòng rất ít (giống thuật toán Euclid), mỗi vòng $\le 20$ lượt.
Em nhập ba số rồi bấm Tiếp để xem từng lượt đổ (thanh nước cao thấp, các bit của $q$):
Ví dụ nhanh:
Cách 1BFS trên trạng thái (subtask 1, 2)
Coi mỗi bộ $(v_1, v_2, v_3)$ là một đỉnh của đồ thị, mỗi lượt đổ hợp lệ là một cạnh. Tổng $S = v_1 + v_2 + v_3$ không đổi nên chỉ cần lưu $(v_1, v_2)$, số trạng thái không quá $(S + 1)^2$. BFS từ trạng thái đầu cho tới khi gặp trạng thái có bình rỗng, rồi truy vết ngược để in ra dãy lượt đổ – được luôn dãy ngắn nhất.
C++▶ Chạy tay từng dòng codeCách 1: BFS trên các trạng thái (v1, v2, v3), truy vết ra dãy lượt đổ ngắn nhất.
Dữ liệu mẫu:
Mỗi trạng thái được mã hoá thành một số enc(v1, v2) = v1·(S+1) + v2 để làm khoá của unordered_map. Bảng trace vừa đánh dấu đã thăm, vừa lưu trạng thái cha và lượt đổ (mã hoá i·3 + j) để truy vết.
Không cần kiểm tra "không tìm thấy" vì bài toán luôn có lời giải (chứng minh ở phần ý tưởng).
Một vài test nhỏ, so sánh số lượt ít nhất (BFS) và số lượt của cách 2:
Test
$v_1\ v_2\ v_3$
BFS (ít nhất)
Cách 2
1
1 2 3
2
2
3
100 99 97
7
7
4
55 46 78
3
29
7
1480 1501 1730
9
66
8
1024 1536 2000
3
23
13
832040 514229 317811
2
36
Không gian$O(S^2)$ trạng thái
Thời gian$O(S^2)$, $S = v_1 + v_2 + v_3$
Kết quả chạy thật: Bản C++ đúng 13/20 test, quá thời gian test 12, 14–18, 20, chạy lâu nhất 3.972s. Bản Python đúng 13/20 test, quá thời gian test 12, 14–18, 20, chạy lâu nhất 4.024s. BFS ăn trọn subtask 1, 2 và cả vài test lớn "may mắn" (ví dụ ba bình bằng nhau, hoặc có bình bằng 1), nhưng với ba số lớn ngẫu nhiên thì số trạng thái lên tới hàng triệu – vượt thời gian.
Cách 2Nhị phân của ⌊b/a⌋ (full điểm)
Cài đặt đúng thuật toán ở phần ý tưởng: mỗi vòng sắp xếp ba chỉ số bình theo lượng nước, tính $q = \lfloor v_b / v_a \rfloor$, rồi duyệt các bit của $q$ (dùng q & 1 và q >>= 1).
C++▶ Chạy tay từng dòng codeCách 2: mỗi vòng duyệt các bit của q = v[b] / v[a]; bit 1 lấy nước từ b, bit 0 lấy từ c.
Dữ liệu mẫu:
Mảng id lưu số hiệu bình (1, 2, 3), sắp xếp theo v[] – nhờ vậy khi in ra ta in đúng số hiệu gốc của bình.
Hàm pour(i, j) thực hiện đúng luật: bình $j$ gấp đôi, bình $i$ mất $v_j$ (cập nhật v[i] trước khi v[j] đổi).
Lượng nước tối đa là tổng ban đầu ($\le 3 \cdot 10^6$), dùng long long cho chắc.
Không gian$O(k)$
Thời gian$O(k)$, $k$ = số lượt (vài trăm)
Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.004s – full điểm. Bản Python đúng 20/20 test, chạy lâu nhất 0.026s.
Tổng kếtKết quả chạy thật trên bộ test
Cách
Ngôn ngữ
Đúng
Lâu nhất
Ghi chú
1. BFS trên trạng thái
C++
13/20
3.972s
40 điểm (theo subtask)
1. BFS trên trạng thái
Python
13/20
4.024s
40 điểm (theo subtask)
2. Nhị phân của ⌊b/a⌋
C++
20/20
0.004s
100 điểm (theo subtask)
2. Nhị phân của ⌊b/a⌋
Python
20/20
0.026s
100 điểm (theo subtask)
Ghi chú của mình: chấm bằng checker (mô phỏng các lượt đổ), thời gian là thời gian CPU trên máy mình, giới hạn 1 giây; điểm tính theo subtask. BFS là "vũ khí vạn năng" cho bài kiến tạo với dữ liệu nhỏ – vừa lấy điểm, vừa giúp kiểm tra lời giải chính. Còn ý tưởng full là một mẹo kinh điển: muốn rút đúng $q$ lần lượng $A$ trong khi $A$ cứ gấp đôi, hãy viết $q$ ở hệ nhị phân. Lời giải cách 2 đã đạt 100/100 trên tinhoctre.vn.
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 😇
Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Bắc & miền Trung – Bảng C1Độ khó: KhóQuy hoạch động đoạnTrieXâu
Đề 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.
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
abbaa
3
bb 5
aaa 1
ba 4
Ví dụ – output
2
2 3
1 2
Giả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.
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.
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
Kết quả trên trang chấm chính thức tinhoctre.vn
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 đó.
Lời giải khớp với chương trình vét cạn trên hàng nghìn test ngẫu nhiên nhỏ và đạt tối ưu trên toàn bộ bộ test của mình. Vì không xem được 3 test 19, 24, 25 nên mình chưa biết chắc nguyên nhân – có thể là test quá nặng khiến phần dự phòng phải dùng lời giải gần đúng, một cách hiểu đề khác của Ban giám khảo, hoặc đáp án của Ban giám khảo ở các test đó chưa tối ưu (khi đó trình chấm có thể báo sai lúc thí sinh tốt hơn đáp án). Các bạn tìm ra lý do thì nhắn mình với nhé!
Ý 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:
Ví dụ nhanh:
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)$.
C++▶ Chạy tay từng dòng codeCách 1: đệ quy có nhớ theo xâu hiện tại, rồi truy vết.
Dữ liệu mẫu:
Không giansố xâu con sinh ra (mũ)
Thời gianmũ theo $|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$.
C++▶ Chạy tay từng dòng codeCách 2: QHĐ đoạn, mỗi hàng l tính bằng một lượt đi trên trie; truy vết bằng delFull / delPrim.
Dữ liệu mẫu:
Mỗi lượt pass(l) được gộp thành một bước (khung "Ghi chú" liệt kê vài trạng thái đầu); các vòng lặp nhỏ khi tính bảng cũng được gộp.
Không gian$O(|S|^2)$ cho hai bảng
Thời gian$O\left(\sum_l \text{số trạng thái} \times \text{số khe}\right)$ – xấu nhất rất lớn
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.
C++▶ Chạy tay từng dòng codeCách 3: bỏ mẫu bị trội, gom trạng thái theo nút trie và bỏ trạng thái bị trội; truy vết trên các trạng thái đã lưu.
Dữ liệu mẫu:
Mỗi mẫu được kiểm tra "bị trội" bằng chính bộ giải trên xâu của mẫu – gộp thành một bước. Mỗi lượt pass(l) cũng gộp thành một bước.
Không gian$O(|S|^2 + \text{số trạng thái})$
Thời giannhư Cách 2 nhưng ít trạng thái hơn nhiều; thực tế $\le 0{,}5$ giây
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.
C++▶ Chạy tay từng dòng codeCách 4 (bản được 90 điểm): như Cách 3 + nén bảng chữ cái, tỉa bằng cận trên/cận dưới, dự phòng thời gian.
Dữ liệu mẫu:
Các lượt bounds(l)/pass(l) và việc kiểm tra mẫu bị trội được gộp thành một bước mỗi lần; khung chạy tay tính bảng F giống hệt Cách 3 (các kỹ thuật tỉa không làm đổi giá trị). Với dữ liệu nhỏ phần dự phòng thời gian không bao giờ được dùng.
Không gian$O(|S|^2)$
Thời giannhư Cách 3, ít trạng thái hơn; luôn dừng trước 1 giây
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
Ghi chú của mình: thời gian là thời gian CPU trên máy mình (giới hạn 1 giây), điểm tính bằng trình chấm theo công thức của đề – mọi test "qua" đều đạt đúng lợi ích tối ưu ($s = d$) – nhưng như đã thấy, bộ test của mình nhẹ hơn bộ chính thức: Cách 3 đúng 20/20 ở đây mà chỉ 60 điểm ở đó. Kỹ thuật cốt lõi của bài – nhìn các thao tác xoá trên xâu gốc và QHĐ đoạn theo "thao tác cuối cùng" – là một dạng kinh điển (giống các bài xoá dãy ngoặc, Zuma...). Còn về 90 điểm chính thức: mình đã kể ở mục Bộ test, nếu bạn nào biết 3 test 19, 24, 25 "khó" ở chỗ nào thì chia sẻ giúp mình nhé.
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 😇
