Dãy số đẹp
Đề bài
Dãy số đẹp là dãy các số nguyên dương có số ước số của các phần tử tăng dần. Cho một dãy gồm $n$ số nguyên dương $a_1, a_2, \dots, a_n$. Người ta cần xoá ít nhất các phần tử của dãy đã cho để các phần tử còn lại tạo thành một dãy số đẹp.
Yêu cầu: Xác định số lượng phần tử của dãy số đẹp thu được.
Dữ liệu vào: Đọc từ tệp văn bản DAYSODEP.INP gồm:
- Dòng đầu ghi số nguyên dương $n$ $(1 \le n \le 5 \times 10^5)$;
- Dòng thứ hai ghi $n$ số nguyên dương $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^9;\ 1 \le i \le n)$;
- Các số ghi trên một dòng cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra tệp văn bản DAYSODEP.OUT gồm một số duy nhất là số lượng các phần tử của dãy số đẹp thu được sau khi xoá.
Ràng buộc:
- Có 20% số điểm tương ứng với $n \le 20$ và $1 \le a_i \le 10^3$;
- Có 40% số điểm tương ứng với $20 < n \le 10^3$ và $1 \le a_i \le 10^6$;
- Có 20% số điểm tương ứng với $10^3 < n \le 5 \times 10^4$ và $1 \le a_i \le 10^6$;
- Có 20% số điểm tương ứng với $5 \times 10^4 < n \le 5 \times 10^5$ và $1 \le a_i \le 10^9$.
Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB.
5
10 3 5 6 123Giải thích: số ước của các phần tử lần lượt là:
| $a_i$ | 10 | 3 | 5 | 6 | 12 |
|---|---|---|---|---|---|
| Số ước | 4 | 2 | 2 | 4 | 6 |
Dãy số đẹp có thể thu được: 3 6 12 hoặc 5 6 12, đều có số ước là $2, 4, 6$ (tăng dần) → đáp án là 3.
DAYSODEP.INP / DAYSODEP.OUT. Code bên dưới dùng if(fopen("DAYSODEP.INP", "r")) { freopen(...); }: có file thì đọc/ghi file, không có thì đọc bàn phím, in ra màn hình. "Tăng dần" ở đây là tăng ngặt (số ước sau phải lớn hơn hẳn số ước trước) – ví dụ của đề cho thấy điều đó: nếu cho phép bằng nhau thì 3 5 6 12 (số ước $2, 2, 4, 6$) dài 4 chứ không phải 3. Nếu trên CLUE OJ không nộp được thì các bạn nộp ở link Codeforces bên dưới.Lời mở đầu
Bỏ lớp áo "số ước" ra thì đây chính là bài dãy con tăng dài nhất (LIS – Longest Increasing Subsequence) kinh điển: thay mỗi $a_i$ bằng $d_i$ = số ước của $a_i$, rồi tìm dãy con tăng ngặt dài nhất của $d$. Bài có 4 subtask, mỗi subtask "ép" ta tối ưu một chỗ: số dãy con → LIS $O(n^2)$ → LIS $O(n \log n)$ → đếm ước nhanh cho $a_i$ tới $10^9$. Mình đi lần lượt từng bước và chạy thật mọi cách trên bộ 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 OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ 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ộ test có 20 test, xếp đúng theo thứ tự subtask. Mình đã kiểm tra từng test thoả điều kiện của subtask tương ứng:
| Subtask | Điều kiện (đề) | Test | $n$ | $a_i$ lớn nhất | Đáp án |
|---|---|---|---|---|---|
| 1 (20%) | $n \le 20$, $a_i \le 10^3$ | 1–4 | 5 – 15 | 714 | 2 – 5 |
| 2 (40%) | $20 < n \le 10^3$, $a_i \le 10^6$ | 5–12 | 30 – 1.000 | 999.235 | 7 – 20 |
| 3 (20%) | $10^3 < n \le 5 \cdot 10^4$, $a_i \le 10^6$ | 13–16 | 30.000 – 50.000 | 999.980 | 40 – 46 |
| 4 (20%) | $5 \cdot 10^4 < n \le 5 \cdot 10^5$, $a_i \le 10^9$ | 17–20 | 80.000 – 400.000 | 999.998.111 | 54 – 73 |
- Đáp án lớn nhất chỉ là 73 dù $n$ tới 400 000: số ước của một số $\le 10^9$ không quá 1344, và các số ngẫu nhiên thường có rất ít ước, nên dãy con tăng của $d$ không thể dài.
- Subtask 4 có $n$ tới 400 000 và $a_i$ gần $10^9$: đếm ước kiểu thử tới $\sqrt{a_i} \approx 31\,623$ cho từng số đã tốn hơn $10^{10}$ phép chia – đây là "nút thắt" chứ không phải phần QHĐ.
Kết quả chạy thật của các cách bên dưới theo từng subtask:
| Subtask | Test | Cách 1 đệ quy chọn/xoá | Cách 2 LIS $O(n^2)$ | Cách 3 LIS $O(n \log n)$ | Cách 4 + phân tích thừa số |
|---|---|---|---|---|---|
| 1 (20%) | 1–4 | 4/4 | 4/4 | 4/4 | 4/4 |
| 2 (40%) | 5–12 | 4/8 | 8/8 | 8/8 | 8/8 |
| 3 (20%) | 13–16 | 0/4 | 0/4 | 4/4 | 4/4 |
| 4 (20%) | 17–20 | 0/4 | 0/4 | 0/4 | 4/4 |
Bảng trên là bản C++ (giới hạn 1 giây). Bản Python xem ở phần tổng kết.
Ý tưởngĐổi sang số ước rồi tìm dãy con tăng dài nhất
Xoá ít nhất ⇔ giữ lại nhiều nhất. Các phần tử giữ lại giữ nguyên thứ tự, tức là một dãy con. Gọi $d_i$ là số ước của $a_i$; dãy con đẹp ⇔ dãy $d$ tương ứng tăng ngặt. Vậy đáp án = độ dài dãy con tăng ngặt dài nhất của $d_1, d_2, \dots, d_n$.
Em nhập dãy rồi bấm Tiếp: ô vàng là $a_i$ đang tính, các ô xanh tím là những $a_j$ đứng trước có số ước nhỏ hơn (nối được), ô viền đậm là $a_j$ có $f[j]$ lớn nhất được chọn. Dòng cuối là mảng tail của cách 3 để em so sánh:
Cách 1Đệ quy chọn / xoá – subtask 1
Với $n \le 20$, ta thử mọi cách giữ/xoá: hàm thu(i, last, cnt) quyết định phần tử thứ $i$, trong đó last là số ước của phần tử giữ lại gần nhất. Xoá thì luôn được; giữ thì chỉ khi d[i] > last. Đếm ước thì thử mọi $i$ từ 1 tới $\sqrt{x}$: mỗi ước $i$ đi kèm ước $x / i$ (trừ khi $i = x / i$).
last = 0lúc đầu: mọi số đều có ít nhất 1 ước nên phần tử đầu tiên luôn giữ được.- Nhánh "giữ" bị cắt ngay khi số ước không tăng, nên số lời gọi bằng khoảng (số dãy con tăng) chứ không hẳn là $2^n$.
i * i <= xvới $x \le 10^9$: $i$ tối đa 31 623, $i \cdot i$ vẫn vừa kiểuint.
Kết quả chạy thật: Bản C++ đúng 8/20 test, quá thời gian ở test 9–20; test đúng chạy lâu nhất 0.06s. Nhờ cắt nhánh, cách này còn "lọt" được test 5–8 ($n \le 100$) vì số ước của các số ở đó nhỏ nên số dãy con tăng không nhiều; từ test 9 thì bùng nổ. Bản Python đúng 8/20 test, quá thời gian ở test 9–20; test đúng chạy lâu nhất 0.77s.
Cách 2QHĐ LIS $O(n^2)$ – subtask 1, 2
Cài đặt đúng công thức ở phần ý tưởng: với mỗi $i$, duyệt mọi $j < i$.
f[i] = 1: dãy chỉ gồm riêng $a_i$ luôn đẹp.- Điều kiện
d[j] < d[i](dấu nhỏ hơn hẳn) – viết<=là sai ngay ví dụ của đề. - Hai vòng lặp lồng nhau: $n^2 / 2$ phép so sánh. Với $n = 1000$ là $5 \cdot 10^5$ – tức thì; với $n = 5 \cdot 10^4$ đã là $1{,}25 \cdot 10^9$ – quá chậm.
Kết quả chạy thật: Bản C++ đúng 12/20 test, quá thời gian ở test 13–20; test đúng chạy lâu nhất 0.01s. Bản Python đúng 12/20 test, quá thời gian ở test 13–20; test đúng chạy lâu nhất 0.15s.
Cách 3LIS $O(n \log n)$ – subtask 1, 2, 3
Kỹ thuật LIS kinh điển: giữ mảng tail, trong đó tail[len - 1] là số ước nhỏ nhất có thể đứng cuối một dãy đẹp dài len. Mảng này luôn tăng ngặt. Với mỗi $d_i$:
- Tìm vị trí $p$ đầu tiên có
tail[p] >= d[i]bằnglower_bound(tìm kiếm nhị phân). - Nếu không có ($p$ = kích thước mảng): $d_i$ lớn hơn mọi đuôi → nối vào dãy dài nhất, dãy dài thêm 1.
- Ngược lại thay
tail[p] = d[i]: có một dãy dài $p + 1$ kết thúc bằng số nhỏ hơn – "đuôi nhỏ" thì sau này dễ nối thêm.
Đáp án là kích thước của tail. Dùng lower_bound (chứ không phải upper_bound) chính là để giữ tăng ngặt: số bằng nhau sẽ thay thế chứ không nối dài.
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.08s. Phần LIS giờ rất nhanh, nhưng đếm ước bằng cách thử tới $\sqrt{a_i}$ thì với $n = 4 \cdot 10^5$ số cỡ $10^9$ cần khoảng $4 \cdot 10^5 \times 31\,623 \approx 1{,}3 \cdot 10^{10}$ phép chia → quá thời gian ở subtask 4. Bản Python đúng 12/20 test, quá thời gian ở test 13–20; test đúng chạy lâu nhất 0.09s.
Cách 4Đếm ước bằng phân tích thừa số nguyên tố – full điểm
Nếu $x = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ thì số ước của $x$ là $(e_1 + 1)(e_2 + 1)\cdots(e_k + 1)$. Để phân tích, ta chỉ cần chia thử cho các số nguyên tố $\le \sqrt{x}$ thay vì mọi số:
- Sàng Eratosthenes trước các số nguyên tố $\le 31\,623$ (vì $31\,623^2 > 10^9$): chỉ có 3401 số – ít hơn gần 10 lần.
- Mỗi lần tìm được thừa số $p$ thì chia hết $x$ cho $p$, nên $x$ nhỏ dần và điều kiện dừng $p \cdot p > x$ đến rất sớm với đa số các số.
- Khi dừng, nếu $x > 1$ thì phần còn lại là một số nguyên tố (lớn hơn $\sqrt{}$ của nó), góp thêm thừa số $(1 + 1) = 2$.
Ví dụ $12 = 2^2 \cdot 3$: chia cho 2 hai lần ($e = 2$, res = 3), còn $x = 3$; tới $p = 3$ thì $3 \cdot 3 > 3$ nên dừng, $x = 3 > 1$ → res = 3 · 2 = 6 ước ✔.
Kết quả chạy thật: Bản C++ đúng 20/20 test; test đúng chạy lâu nhất 0.40s. Full điểm. Bản Python đúng 16/20 test, quá thời gian ở test 17–20; test đúng chạy lâu nhất 0.20s – bản Python đã nhanh hơn cách 3 nhiều nhưng 400 000 lần phân tích thừa số bằng vòng lặp Python vẫn quá chậm cho 1 giây, nên với subtask 4 các bạn nên dùng C++.
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. Đệ quy chọn/xoá | C++ | 8/20 | > 1s | 20 điểm / 100 |
| Python | 8/20 | > 1s | 20 điểm / 100 | |
| 2. LIS $O(n^2)$, ước $O(\sqrt{a})$ | C++ | 12/20 | > 1s | 60 điểm / 100 |
| Python | 12/20 | > 1s | 60 điểm / 100 | |
| 3. LIS $O(n \log n)$, ước $O(\sqrt{a})$ | C++ | 16/20 | > 1s | 80 điểm / 100 |
| Python | 12/20 | > 1s | 60 điểm / 100 | |
| 4. LIS $O(n \log n)$ + phân tích thừa số | C++ | 20/20 | 0.40s | 100 điểm / 100 |
| Python | 16/20 | > 1s | 80 điểm / 100 |
Nhận xét
Đăng nhận xét