Dãy số (Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 2 – Bảng B)

Nguồn: Tin học trẻ 2025 – Vòng loại quốc gia đợt 2 Độ khó: Khá Quy hoạch động Đệ quy có nhớ Kiểu dãy con chung

Đề bài

Cho hai dãy số nguyên $a_1, a_2, \ldots, a_m$ và $b_1, b_2, \ldots, b_n$. Ta chọn $k$ chỉ số tăng dần trên dãy $a$: $1 \le i_1 < i_2 < \cdots < i_k$ $\le m$ và $k$ chỉ số tăng dần trên dãy $b$: $1 \le j_1 < j_2 < \cdots < j_k$ $\le n$, rồi ghép thành $k$ cặp $(a_{i_1}, b_{j_1}),$ $(a_{i_2}, b_{j_2}),$ $\ldots,$ $(a_{i_k}, b_{j_k})$. Các cặp phải thoả một trong hai điều kiện:

$a_{i_1} \ge b_{j_1}$, $a_{i_2} \le b_{j_2}$, $a_{i_3} \ge b_{j_3}$, ... (dấu $\ge$ và $\le$ xen kẽ, bắt đầu bằng $\ge$);
$a_{i_1} \le b_{j_1}$, $a_{i_2} \ge b_{j_2}$, $a_{i_3} \le b_{j_3}$, ... (xen kẽ, bắt đầu bằng $\le$).

Hãy tìm $k$ lớn nhất có thể.

Dữ liệu vào:

Dòng đầu tiên chứa hai số nguyên $m, n$.
Dòng thứ hai chứa $m$ số nguyên $a_1, a_2, \ldots, a_m$ $(|a_i| \le 10^9)$.
Dòng thứ ba chứa $n$ số nguyên $b_1, b_2, \ldots, b_n$ $(|b_j| \le 10^9)$.

Kết quả: In ra một số nguyên là $k$ lớn nhất tìm được.

Subtask:

Subtask 1 (40% số điểm): $m \le 20$, $n \le 20$.
Subtask 2 (40% số điểm): $m \le 20$, $n \le 5000$.
Subtask 3 (20% số điểm): $m \le 5000$, $n \le 5000$.

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

Ví dụ – input

3 4
1 2 3
2 0 1 4

Ví dụ – output

Giải thích: chọn $i = (1, 2, 3)$ và $j = (1, 2, 4)$ theo điều kiện 2: $a_1 = 1 \le b_1 = 2$, $a_2 = 2 \ge b_2 = 0$, $a_3 = 3 \le b_4 = 4$. Vậy $k = 3$ (không thể hơn vì dãy $a$ chỉ có 3 phần tử).

Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 2 – Bảng B. Đề bài được mình viết lại bằng lời của mình cho dễ hiểu, giữ nguyên ý nghĩa và số liệu.

Lời mở đầu

Nếu em đã học bài dãy con chung dài nhất (LCS) thì bài này là "họ hàng" của nó: thay vì ghép hai phần tử bằng nhau, ta ghép hai phần tử thoả một phép so sánh, và phép so sánh đổi chiều sau mỗi cặp. Cái khó nằm ở giới hạn thời gian cực chặt: 0,1 giây cho $m = n = 5000$, tức $2{,}5 \cdot 10^7$ ô bảng – viết QHĐ "bình thường" chạy sát nút giới hạn. Mình sẽ đi từ đệ quy vét cạn → đệ quy có nhớ → QHĐ bảng → tối ưu hằng số để chắc chắn qua.

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 Ý tưởngtrạng thái (i, j, s)Cách 1đệ quy Cách 2đệ quy có nhớ Cách 3QHĐ bảng Cách 4tối ưu 0,1 s

Bộ testBộ test có gì?

Bộ test mình dùng có 20 test, chia đúng tỉ lệ 40% – 40% – 20% của đề (test 1 là ví dụ của đề). Mình đã kiểm tra: test 1–8 có $m, n \le 20$, test 9–16 có $m \le 20$ và $n$ tới 5000, test 17–20 có $m, n$ tới 5000.

Nhóm	Test	$m$ lớn nhất	$n$ lớn nhất	Giá trị nhỏ nhất – lớn nhất	Số giá trị khác nhau (ít nhất)	Đáp án $k$
Subtask 1	1–8	20	20	-1.000.000.000 – 1.000.000.000	1	1 – 20
Subtask 2	9–16	20	5.000	-1.000.000.000 – 1.000.000.000	2	1 – 20
Subtask 3	17–20	5.000	5.000	-1.000.000.000 – 1.000.000.000	7	2.484 – 4.999

Có test chỉ có 1 hoặc 2 giá trị khác nhau (rất nhiều phần tử bằng nhau – khi $a_i = b_j$ thì cả hai dấu $\ge$, $\le$ đều đúng), test giá trị chỉ trong $[-3, 3]$, test giá trị sát $\pm 10^9$.
Có test "bẫy" mà mọi phần tử $a$ đều lớn hơn mọi phần tử $b$ (chỉ ghép được 1 cặp), và test có $m = 1$.

Lời giải cuối cùng (cách 4) mình đã nộp thử trên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được AC (100 điểm). Kết quả chạy thật các cách bên dưới trên bộ test của mình, theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 đệ quy	Cách 2 có nhớ	Cách 3 QHĐ bảng	Cách 4 tối ưu
Subtask 1 (40%)	$m, n \le 20$	1–8	3/8	8/8	8/8	8/8
Subtask 2 (40%)	$m \le 20$, $n \le 5000$	9–16	1/8	8/8	8/8	8/8
Subtask 3 (20%)	$m, n \le 5000$	17–20	0/4	0/4	2/4	4/4

Ý tưởngTrạng thái (i, j, dấu tiếp theo)

Hãy nghĩ như LCS: đứng ở vị trí $i$ của dãy $a$ và $j$ của dãy $b$, cặp tiếp theo phải thoả dấu $s$ ($s = 0$: $\ge$, $s = 1$: $\le$). Có 3 lựa chọn:

Bỏ $a_i$ (không dùng nó): sang trạng thái $(i + 1, j, s)$.
Bỏ $b_j$: sang trạng thái $(i, j + 1, s)$.
Ghép cặp $(a_i, b_j)$ nếu đúng dấu $s$: được thêm 1 cặp, sang $(i + 1, j + 1, 1 - s)$ – dấu đổi chiều.

Công thức quy hoạch động

Gọi $f[i][j][s]$ = số cặp nhiều nhất ghép được từ $a_i..a_m$ và $b_j..b_n$ khi cặp đầu tiên phải đúng dấu $s$:
$f[i][j][s]$ $= \max\big(f[i+1][j][s],\ f[i][j+1][s],\ 1 + f[i+1][j+1][1-s]$ (nếu $a_i, b_j$ đúng dấu $s$)$\big)$
Khi $i > m$ hoặc $j > n$: $f = 0$. Đáp án $= \max(f[1][1][0],\ f[1][1][1])$ – hai điều kiện của đề chính là bắt đầu bằng $\ge$ hoặc $\le$.

Vì $f[i][j]$ phụ thuộc các ô có $i$ lớn hơn hoặc $j$ lớn hơn, ta điền bảng từ góc dưới phải ngược lên. Em nhập hai dãy (mỗi dãy tối đa 6 số) rồi bấm Tiếp để xem hai bảng $f[\cdot][\cdot][0]$ (cặp đầu $\ge$) và $f[\cdot][\cdot][1]$ (cặp đầu $\le$) được điền dần; ô vàng là ô đang tính, ô tím là các ô nó dùng tới. Bước cuối truy vết ra các cặp được ghép:

Dãy a: Dãy b:

Ví dụ nhanh:

Cách 1Đệ quy vét cạn

Viết thẳng ý tưởng trên thành hàm đệ quy go(i, j, s), chưa nhớ gì cả:

C++▶ Chạy tay từng dòng codeCách 1: đệ quy vét cạn go(i, j, s) – để ý số lời gọi tăng rất nhanh.

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

Dữ liệu mẫu:

Khung này chỉ nhận m, n ≤ 3 vì số lời gọi tăng theo hàm mũ.

Mỗi lời gọi lại gọi tiếp tới 3 lời gọi con, và cùng một trạng thái $(i, j, s)$ bị tính đi tính lại rất nhiều lần (ví dụ $(i+1, j+1)$ đến được bằng "bỏ $a_i$ rồi bỏ $b_j$", "bỏ $b_j$ rồi bỏ $a_i$", hoặc ghép). Số lời gọi tăng theo hàm mũ: với $m = n = 20$ đã vào khoảng $10^{14}$ lời gọi – không bao giờ chạy xong.

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

Thời gianhàm mũ

Kết quả chạy thật: bản C++ đúng 4/20 test, quá thời gian test 4–12, 14–20, test đúng chạy lâu nhất 0,004 giây. Chỉ qua được các test rất nhỏ (ví dụ của đề, $m = 1$...), không ăn trọn subtask nào.

Cách 2Đệ quy có nhớ

Chỉ cần thêm một mảng memo lưu kết quả từng trạng thái: lần đầu tính xong thì ghi lại, lần sau gặp lại thì trả về luôn. Số trạng thái là $(m + 1)(n + 1) \cdot 2$, mỗi trạng thái tính $O(1)$.

C++▶ Chạy tay từng dòng codeCách 2: đệ quy có nhớ – mỗi trạng thái (i, j, s) chỉ tính một lần.

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

Dữ liệu mẫu:

int &r = memo[...] là tham chiếu tới ô nhớ của trạng thái, nên return r = res; vừa ghi vào bảng vừa trả kết quả.
Mảng 1 chiều memo đánh chỉ số $(i \cdot (n + 2) + j) \cdot 2 + s$ thay cho mảng 3 chiều. Với $m = n = 5000$ là $5 \cdot 10^7$ số int = 200 MB, vẫn dưới 1024 MB.
Độ sâu đệ quy tối đa $m + n \approx 10^4$ – C++ chịu được. Bản Python phải tăng setrecursionlimit, và không dùng lru_cache (với Python 3.12+ nó làm tràn ngăn xếp C ở độ sâu vài nghìn).

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

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

Kết quả chạy thật: bản C++ đúng 16/20 test, quá thời gian test 17–20, test đúng chạy lâu nhất 0,006 giây → trọn subtask 1 và 2 (80% điểm). Ở subtask 3, $5 \cdot 10^7$ trạng thái với lời gọi hàm và truy cập bộ nhớ lung tung mất gần 1 giây. Bản Python đúng 9/20 test, quá thời gian test 9–12, 14–20, test đúng chạy lâu nhất 0,025 giây.

Cách 3QHĐ bảng, chỉ giữ 2 dòng

Bỏ đệ quy, điền bảng bằng vòng lặp: $i$ chạy từ $m$ về 1, $j$ chạy từ $n$ về 1. Để tính dòng $i$ chỉ cần dòng $i + 1$, nên chỉ giữ 2 dòng nxt (dòng $i+1$) và cur (dòng $i$), mỗi ô có 2 giá trị cho $s = 0, 1$. Bộ nhớ giảm từ 200 MB xuống vài chục KB, và truy cập bộ nhớ liên tiếp nên nhanh hơn nhiều.

C++▶ Chạy tay từng dòng codeCách 3: QHĐ bảng từ cuối về đầu, chỉ giữ 2 dòng.

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

Dữ liệu mẫu:

cur[n + 1] = {0, 0}: cột "lính canh" $j = n + 1$ (hết dãy $b$) luôn bằng 0. Dòng nxt ban đầu toàn 0 chính là dòng lính canh $i = m + 1$.
swap(cur, nxt) đổi hai vector trong $O(1)$ (chỉ đổi con trỏ), sau đó nxt là dòng vừa tính.

Không gian$O(n)$

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

Kết quả chạy thật: bản C++ đúng 18/20 test, quá thời gian test 17–18, test đúng chạy lâu nhất 0,082 giây. Đúng hết nhưng 2 test lớn chạy sát/vượt nhẹ 0,1 giây – trên máy chấm khác có thể qua hoặc không, quá mạo hiểm. Bản Python đúng 16/20 test, quá thời gian test 17–20, test đúng chạy lâu nhất 0,047 giây (đủ subtask 1, 2).

Cách 4Tối ưu hằng số để chắc chắn qua 0,1 giây

Độ phức tạp $O(m \cdot n)$ không thể giảm thêm, nên ta làm cho mỗi ô chạy nhanh hơn. Điểm "nghẽn" của cách 3 là ô cur[j] phụ thuộc cur[j + 1] vừa tính, nên CPU phải tính tuần tự từng ô. Mẹo:

Tách thành 2 vòng lặp

$f[i][j][s]$ $= \max\big(\underbrace{f[i+1][j][s],\ \text{ghép}(i, j)}_{\text{chỉ dùng dòng } i+1},\ f[i][j+1][s]\big)$
Lấy max với $f[i][j+1][s]$ rồi lại max với $f[i][j+2][s]$... chính là max hậu tố. Nên:
• Vòng 1: c[j] = max(nx[j], ghép(i, j)) cho mọi $j$ – các ô độc lập nhau, trình biên dịch tự vector hoá (xử lí 8–16 ô một lúc bằng lệnh SIMD).
• Vòng 2: c[j] = max(c[j], c[j + 1]) từ phải sang trái – một vòng max hậu tố rất đơn giản.

Thêm hai mẹo nhỏ: nén giá trị $a, b$ về thứ hạng (chỉ cần so sánh lớn bé, tối đa 10 000 giá trị) để lưu bằng kiểu short 2 byte – một lệnh SIMD xử lí được gấp đôi số ô so với int; và viết phép "ghép nếu đúng dấu" không có if: ge * (nx1[j + 1] + 1) bằng 0 khi sai dấu.

C++▶ Chạy tay từng dòng codeCách 4: nén giá trị + tách 2 vòng lặp (vòng 1 vector hoá được, vòng 2 max hậu tố).

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

Dữ liệu mẫu:

#pragma GCC optimize("O3") bật mức tối ưu cao nhất (có vector hoá vòng lặp) ngay trong file nguồn.
Khi ghép $(i, j)$ với dấu $\ge$ ($s = 0$), cặp sau phải là $\le$ nên lấy nx1[j + 1]; ngược lại với $s = 1$ lấy nx0[j + 1].
Giá trị $f \le 5000$ và thứ hạng $< 10\,000$ đều vừa kiểu short (tới 32 767).

Không gian$O(m + n)$

Thời gian$O(m \cdot n)$, hằng số nhỏ

Kết quả chạy thật: bản C++ đúng 20/20 test, test đúng chạy lâu nhất 0,053 giây – nhanh gấp đôi cách 3, dư sức trong 0,1 giây. Đây cũng là ý tưởng của lời giải mình đã nộp chính thức (AC).

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
1. Đệ quy vét cạn	C++	4/20	0,004 s	0%
2. Đệ quy có nhớ	C++	16/20	0,006 s	80%
	Python	9/20	0,025 s	40%
3. QHĐ bảng, 2 dòng	C++	18/20	0,082 s	80%
	Python	16/20	0,047 s	80%
4. QHĐ tối ưu hằng số	C++	20/20	0,053 s	100%

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 0,1 giây. Đệ quy có nhớ đã cho 80% điểm; QHĐ bảng đúng hết nhưng chạy sát giới hạn; tối ưu hằng số (tách vòng lặp để vector hoá + kiểu short) giúp nhanh gấp đôi. Python không thể chạy $2{,}5 \cdot 10^7$ ô trong 0,1 giây nên chỉ đủ hai subtask đầu. Bài học: khi giới hạn thời gian rất chặt mà độ phức tạp đã tối ưu, hãy nghĩ tới việc bỏ phụ thuộc giữa các ô liền nhau để CPU tính song song.

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