Spring Contest 2020 SPC1

Nguồn: CLUE OJ – Chương 22: Quy hoạch động (TopAlgo – Spring Contest 2020) Độ khó: Khá Quy hoạch động Dãy con chung dài nhất

Đề bài

Ta định nghĩa dãy $c$ là một dãy con của một dãy số nguyên $a$ khi dãy $c$ được tạo nên bởi việc xóa đi 0, 1 hoặc nhiều số trong dãy $a$.

Ví dụ: những dãy $c = \{1, 2\}$, $\{1, 3, 4\}$, $\{2, 3, 4\}$ đều là những dãy con của dãy $a = \{1, 2, 3, 5, 4\}$ bởi vì dãy $c = \{1, 2\}$ được tạo nên từ dãy $a$ bằng việc xóa đi các số 3, 5, 4; dãy $c = \{1, 3, 4\}$ được tạo nên từ dãy $a$ bằng việc xóa đi các số 2, 5 và dãy $c = \{2, 3, 4\}$ được tạo nên từ việc xóa đi 2 số 1, 5 của dãy $a$.

Dãy $c = \{1, 3, 2\}$ không phải là một dãy con của dãy $a = \{1, 2, 3, 5, 4\}$ bởi vì không tồn tại cách xóa số nào trong dãy $a$ để ra được dãy $c$ cả.

Bạn được cho 2 dãy số nguyên $a$ và $b$, dãy $a$ gồm $N$ phần tử, dãy $b$ gồm $M$ phần tử. Bạn hãy tìm một dãy $c$ có độ dài dài nhất mà dãy $c$ vừa là dãy con của dãy $a$ vừa là dãy con của dãy $b$. Hãy in ra độ dài của dãy $c$ thỏa mãn.

Dữ liệu đầu vào:

• Dòng đầu tiên gồm một số nguyên dương $T$ $(1 \le T \le 40)$ là số lượng bộ dữ liệu.
• $T$ bộ dữ liệu tiếp theo, mỗi bộ gồm: dòng đầu chứa 2 số nguyên dương $N$ và $M$ là số phần tử của dãy $a$ và dãy $b$; dòng thứ hai chứa $N$ số nguyên dương $a_1, \ldots, a_N$; dòng thứ ba chứa $M$ số nguyên dương $b_1, \ldots, b_M$.

Dữ liệu đầu ra: gồm $T$ dòng, mỗi dòng là một số nguyên duy nhất – độ dài dài nhất của dãy $c$ thỏa mãn.

Bài toán được chia thành 2 Dataset:

• Small Dataset: $1 \le N, M \le 2000$.
• Large Dataset: $1 \le M \le 2000$, $1 \le N \le 200\,000$.
• Trong mọi Dataset: $1 \le a_i \le 2000$ (bộ test thật cũng có $b_i \le 2000$).

Giới hạn: 1 giây, 512 MB cho mỗi Dataset.

Ví dụ – input

5
1 1
2
3
5 4
1 2 5 4 3
1 5 4 3
4 4
4 3 2 1
1 2 3 4
7 7
20 20 20 20 20 20 20
20 20 20 20 20 20 20
7 7
1 5 2 4 8 9 3
2 5 4 9 2 5 6

Ví dụ – output

0
4
1
7
3

Giải thích test ví dụ:

• Bộ 1: dãy $a$ chỉ có 1 phần tử $\{2\}$, dãy $b$ chỉ có $\{3\}$, khác nhau nên độ dài dãy con chung dài nhất là 0.
• Bộ 2: dãy $b$ chính là một dãy con của dãy $a$, do đó đáp án là độ dài dãy $b$ = 4.
• Bộ 3: có nhiều dãy con chung là $\{1\}$, $\{2\}$, $\{3\}$ hoặc $\{4\}$, dãy nào cũng có độ dài 1.
• Bộ 4: hai dãy giống nhau nên đáp án là độ dài của cả 2 dãy = 7.
• Bộ 5: dãy con chung dài nhất là $\{5, 4, 9\}$, độ dài 3.

Lời mở đầu

Dãy con chung dài nhất (Longest Common Subsequence – LCS) là bài QHĐ kinh điển với bảng $N \times M$. Phần Small của bài này đúng là LCS cơ bản. Cái hay nằm ở phần Large: $N$ lên tới $200\,000$ thì bảng $N \times M$ vừa quá to vừa quá chậm. Ta sẽ phải "lật ngược" trạng thái QHĐ – thay vì hỏi "dài nhất bao nhiêu", ta hỏi "để đạt độ dài $k$ thì cần đi tới đâu trong dãy $a$". Mình đi lần lượt 4 cách, mỗi cách đều chạy thật trên 2 file test.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

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 fileÝ tưởngBảng LCSCách 1Đệ quy 0/2Cách 2Bảng 1/2Cách 32 dòng 1/2Cách 4g[k] 2/2

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

Bài này chỉ có 2 file test, mỗi file chứa nhiều bộ dữ liệu, và mỗi file được chấm như 1 test với giới hạn 1 giây cho cả file. Mình đọc từng bộ trong 2 file để thống kê:

File	Số bộ $T$	$N$	$M$	Số bộ có $N > 2000$	Tổng $N \cdot M$	Đáp án lớn nhất
1	25	1 – 2,000	1 – 2,000	0	0,026 tỉ	80
2	40	147 – 200,000	104 – 2,000	20	2,298 tỉ	788

File 1 đúng là Small Dataset (5 bộ đầu chính là test ví dụ, 20 bộ ngẫu nhiên $N, M \le 2000$). File 2 là Large Dataset: 20 bộ đầu giống hệt 20 bộ ngẫu nhiên của file 1, 20 bộ sau có $N$ tới $200\,000$ (bộ cuối $N = 200\,000$, $M = 2000$). Mọi giá trị $a_i, b_i \le 2000$. File 2 nặng gần 11 MB nên phải đọc nhanh.

Con số quan trọng là cột tổng $N \cdot M$: file 2 cần tới 2,3 tỉ ô nếu làm bảng QHĐ thông thường – không thể chạy trong 1 giây. Ta phải khai thác $M \le 2000$ nhỏ.

Dataset	Điều kiện	File	Cách 1 đệ quy	Cách 2 bảng N×M	Cách 3 bảng 2 dòng	Cách 4 đổi trạng thái
Small	$N, M \le 2000$	1	quá thời gian	qua	qua	qua
Large	$M \le 2000,\ N \le 2 \cdot 10^5$	2	quá thời gian	không đủ bộ nhớ	quá thời gian	qua

Ý tưởngNhìn vào 2 phần tử cuối

Gọi $f[i][j]$ = độ dài dãy con chung dài nhất của $a_1..a_i$ và $b_1..b_j$. Xét 2 phần tử cuối $a_i$ và $b_j$:

• Nếu $a_i = b_j$: cho cả hai cùng làm phần tử cuối của dãy chung, phần còn lại là LCS của $a_1..a_{i-1}$ và $b_1..b_{j-1}$: $f[i][j] = f[i-1][j-1] + 1$.
• Nếu $a_i \ne b_j$: ít nhất một trong hai không được dùng, bỏ $a_i$ hoặc bỏ $b_j$: $f[i][j]$ $= \max(f[i-1][j],\ f[i][j-1])$.

Công thức QHĐ

$f[0][j] = f[i][0] = 0;\quad f[i][j] = \begin{cases} f[i-1][j-1] + 1 & a_i = b_j \\ \max(f[i-1][j],\ f[i][j-1]) & a_i \ne b_j \end{cases}$. Đáp án là $f[N][M]$.

Em nhập 2 dãy rồi bấm Tiếp để xem bảng được điền từng ô (ô vàng đang tính, ô xanh dương là ô nó lấy giá trị; hàng là $a$, cột là $b$):

Dãy a Dãy b

Ví dụ nhanh:

Cách 1Đệ quy thuần (chỉ chạy được test rất nhỏ)

Viết thẳng công thức thành hàm đệ quy L(i, j):

C++▶ Chạy tay từng dòng codeCách 1: đệ quy thuần L(i, j) – chỉ chạy được với dãy rất ngắn.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Mỗi dãy em nhập tối đa 4 số: đệ quy thuần tách nhánh rất nhanh, số bước tăng vọt.

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

Thời giantới $O(2^{N+M})$

Khi $a_i \ne b_j$ hàm tách làm 2 nhánh, nên số lời gọi có thể lên tới cỡ $2^{N+M}$; cùng một L(i, j) bị tính lại rất nhiều lần. Đệ quy còn sâu tới $N + M$ tầng.

Kết quả chạy thật: 0/2 file – cả hai đều quá thời gian (bộ ngẫu nhiên đầu tiên đã có $N = 1141$, $M = 939$). Cách này chỉ để hiểu công thức; muốn chạy được thì phải nhớ lại kết quả (đệ quy có nhớ) – mà nhớ cho mọi cặp $(i, j)$ thì chính là cái bảng của cách 2.

Cách 2QHĐ bảng $N \times M$ (Small Dataset)

Điền bảng $f$ theo từng hàng $i$, mỗi hàng từ trái sang phải. Ba ô $f[i-1][j-1]$, $f[i-1][j]$, $f[i][j-1]$ luôn được tính trước $f[i][j]$.

C++▶ Chạy tay từng dòng codeCách 2: điền bảng f (n + 1) × (m + 1) theo hàng.

Dữ liệu vào (stdin) – sửa thoải mái5 1 1 2 3 5 4 1 2 5 4 3 1 5 4 3 4 4 4 3 2 1 1 2 3 4 7 7 20 20 20 20 20 20 20 20 20 20 20 20 20 20 7 7 1 5 2 4 8 9 3 2 5 4 9 2 5 6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(N \cdot M)$

Thời gian$O(N \cdot M)$

Kết quả chạy thật: file 1 (Small) đúng, 0,07 giây. File 2 sai: code khai báo bảng f[2005][2005] nên bộ có $N > 2000$ ghi tràn ra ngoài mảng. Muốn đủ chỗ cho $N = 200\,000$ thì bảng cần $200\,001 \times 2001$ số int $\approx$ 1,6 GB, vượt xa 512 MB. Và kể cả có đủ bộ nhớ thì 2,3 tỉ ô cũng quá thời gian (xem cách 3).

Cách 3Chỉ giữ 2 dòng của bảng (vẫn chỉ qua Small)

Để tính hàng $i$ chỉ cần hàng $i - 1$. Vậy giữ 2 mảng pre (hàng cũ) và cur (hàng đang tính), mỗi mảng $M + 1$ ô. Bộ nhớ giảm từ $O(N \cdot M)$ xuống $O(M)$, và giờ đọc được dãy $a$ dài $200\,000$.

C++▶ Chạy tay từng dòng codeCách 3: chỉ giữ 2 dòng pre (dòng i−1) và cur (dòng i).

Dữ liệu vào (stdin) – sửa thoải mái1 7 7 1 5 2 4 8 9 3 2 5 4 9 2 5 6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(N + M)$

Thời gian$O(N \cdot M)$

Kết quả chạy thật: file 1 đúng (0,06 giây). File 2 quá thời gian: chạy hết khoảng 2,5 giây vì vẫn phải tính 2,3 tỉ ô. Tối ưu bộ nhớ không làm giảm số phép tính – ta cần một ý tưởng khác. Bản Python của cách này còn quá thời gian ngay ở file 1 (3,3 giây).

Cách 4Đổi trạng thái: "đạt độ dài k thì cần đi tới đâu trong a?" (full điểm)

Dãy $b$ ngắn ($M \le 2000$), đáp án cũng $\le M$. Còn dãy $a$ thì dài. Ý tưởng: duyệt theo $b$, và thay vì lưu "độ dài lớn nhất" theo vị trí trong $a$ (tốn $N$ ô), ta lưu vị trí nhỏ nhất trong $a$ theo độ dài (chỉ tốn $M$ ô):

Trạng thái mới

Sau khi xét xong $b_1..b_j$: $g[k]$ = vị trí $p$ nhỏ nhất sao cho $a_1..a_p$ và $b_1..b_j$ có dãy con chung độ dài $k$ ($g[k] = \infty$ nếu chưa làm được). $g[0] = 0$.

Khi xét thêm $b_j$, dãy chung độ dài $k$ hoặc không dùng $b_j$ (giữ $g[k]$ cũ), hoặc dùng $b_j$ làm phần tử thứ $k$: lấy một dãy chung độ dài $k - 1$ kết thúc sớm nhất ở $g[k-1]$, rồi tìm vị trí đầu tiên sau $g[k-1]$ trong $a$ có giá trị bằng $b_j$:

g[k] = min( g[k], vị trí đầu tiên > g[k−1] có a_p = b_j )

Chọn vị trí sớm nhất luôn có lợi (đuôi càng sớm càng để lại nhiều chỗ cho các phần tử sau) – đây là cùng một kiểu suy nghĩ với mảng $d$ của bài dãy con tăng dài nhất. Hai chi tiết cài đặt:

• Vì $a_i \le 2000$ nên ta gom vị trí theo giá trị: pos[v] là danh sách tăng dần các vị trí có $a_p = v$. "Vị trí đầu tiên > $g[k-1]$" chính là upper_bound trên pos[b[j]] – chặt nhị phân $O(\log N)$.
• Duyệt $k$ giảm dần để khi tính $g[k]$ thì $g[k-1]$ vẫn là giá trị cũ (chưa dùng $b_j$) – mỗi phần tử $b_j$ chỉ được dùng 1 lần trong một dãy. Và chỉ cần $k$ từ best + 1 xuống 1, với best là độ dài đạt được hiện tại.

Em thử với ví dụ nhỏ – bấm Tiếp để xem mảng $g$ thay đổi khi lần lượt xét $b_1, b_2, \ldots$:

Dãy a (dài) Dãy b (ngắn)

Ví dụ nhanh:

C++▶ Chạy tay từng dòng codeCách 4: g[k] = vị trí nhỏ nhất trong a để có dãy chung dài k; cập nhật bằng upper_bound.

Dữ liệu vào (stdin) – sửa thoải mái1 7 7 1 5 2 4 8 9 3 2 5 4 9 2 5 6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Dòng đọc dãy a được gộp thành 1 bước; khung pos chỉ hiện các giá trị có trong a.

Không gian$O(N + M)$

Thời gian$O(N + M^2 \log N)$

Tổng số lần chặt nhị phân không quá $M \cdot (\text{đáp án} + 1) \le M^2$; với $M = 2000$ đó là tối đa $4 \cdot 10^6$ lần mỗi bộ, mỗi lần $\log_2 N \approx 18$ bước. Cộng cả file 2 chỉ vài chục triệu phép tính.

Kết quả chạy thật: 2/2 file đúng, chậm nhất 0,23 giây (file 2, phần lớn là thời gian đọc 11 MB dữ liệu). Bản Python cùng ý tưởng đúng cả 2 file nhưng file 2 mất 1,87 giây – quá giới hạn 1 giây, nên với bài này các bạn nên nộp C++.

Ghi chú của mình: bài chỉ có 2 file test (Small: 25 bộ; Large: 40 bộ, $N$ tới $2 \cdot 10^5$). Kết quả chạy thật (C++): đệ quy 0/2, bảng $N \times M$ 1/2 (không đủ bộ nhớ cho Large), bảng 2 dòng 1/2 (Large mất 2,5 s), đổi trạng thái + chặt nhị phân 2/2 trong 0,23 s. Python: cách 4 đúng nhưng file Large mất 1,87 s.

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 😇