Spring Contest 2020 SPC1
Đề 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.
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 60
4
1
7
3Giả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à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 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])$.
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$):
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):
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]$.
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$.
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$ ô):
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$:
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_boundtrênpos[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 + 1xuống 1, vớibestlà độ 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$:
pos chỉ hiện các giá trị có trong a.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++.
Nhận xét
Đăng nhận xét