Trồng cây

Nguồn: CLUE OJ – Chương 15: Ngăn xếp, Hàng đợi, Hàng đợi 2 đầu Độ khó: Trung bình Hàng đợi 2 đầu (deque) Sàng nguyên tố

Đề bài

Bác Bình có một khu vườn rất nhiều cây, mỗi cây có một chiều cao khác nhau. Bác Bình muốn chọn tất cả các cây đặc biệt trong vườn để trồng thành một hàng cây mới (cây đặc biệt là cây có chiều cao là một số nguyên tố). Hơn nữa để cây tiếp xúc tốt với ánh sáng bác có ý tưởng bố trí vị trí các cây đặc biệt theo quy tắc thực hiện lần lượt như sau:

• B1: Chọn cây cao nhất đặt làm mốc;
• B2: Cây cao tiếp theo đặt ở bên trái của mốc;
• B3: Cây cao tiếp theo nữa ở bên phải của mốc;

Thực hiện lặp đi lặp lại B2, B3 cho đến khi hết số cây đặc biệt.

Yêu cầu: cho trước số lượng và chiều cao của các cây trong vườn, hãy giúp bác Bình trồng hàng các cây đặc biệt theo đúng ý tưởng của bác.

Dữ liệu vào: từ tệp văn bản TRONGCAY.INP gồm hai dòng:

• Dòng thứ nhất chứa số nguyên $N$ $(1 \le N \le 10^6)$ là số lượng cây trong vườn.
• Dòng thứ hai chứa $N$ số nguyên $a_i$ $(1 \le a_i \le 10^7,\ 1 \le i \le N)$ là chiều cao của cây thứ $i$.

Kết quả: ghi ra tệp văn bản TRONGCAY.OUT gồm các số trên cùng một dòng là chiều cao của các cây đặc biệt trong hàng cây mới. Nếu không có cây đặc biệt nào thì ghi ra tệp giá trị $-1$. Các số cách nhau ít nhất một dấu cách trống.

Giới hạn:

• $75\%$ số test với $1 \le N \le 10^4$;
• $25\%$ số test với $10^4 < N \le 10^6$.

Ví dụ 1 – input

8
2 55 23 16 53 5 20 17

Ví dụ 1 – output

5 23 53 17 2

Ví dụ 2 – input

3
25 18 9

Ví dụ 2 – output

-1

Giải thích ví dụ 1: các cây đặc biệt (chiều cao nguyên tố) là $2, 23, 53, 5, 17$. Xếp giảm dần: $53, 23, 17, 5, 2$. Lần 1 đặt $53$ làm mốc; lần 2 đặt $23$ bên trái; lần 3 đặt $17$ bên phải; lần 4 đặt $5$ bên trái (ngoài cùng); lần 5 đặt $2$ bên phải (ngoài cùng) → hàng cây $5\ 23\ 53\ 17\ 2$. Ví dụ 2 không có số nguyên tố nào ($25 = 5^2$, $18$, $9 = 3^2$) nên in $-1$.

Lưu ý nộp bài: trên CLUE OJ bài này đọc/ghi qua tệp TRONGCAY.INP / TRONGCAY.OUT, còn trên Codeforces thì đọc/ghi bàn phím – màn hình. Trong code mình dùng if (fopen("TRONGCAY.INP", "r")) { freopen(...); freopen(...); }: có tệp thì đọc tệp, không có thì tự động đọc từ bàn phím, nộp ở đâu cũng được.

Lời mở đầu

Bài này ghép 3 kiến thức quen thuộc: kiểm tra số nguyên tố (với $10^6$ số tới $10^7$ thì nên dùng sàng Eratosthenes), sắp xếp giảm dần, và cấu trúc hàng đợi 2 đầu (deque) để "thêm vào bên trái / thêm vào bên phải" trong $O(1)$. Mình sẽ đi từ cách mô phỏng đúng từng chữ của đề (ăn subtask 1) tới cách full điểm, kèm kết quả chạy thật trên bộ test của CLUE.

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

Dành cho tất cả mọi ngườiNộp bài trên Codeforces

Bạ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 Codeforces

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 test, 2 mứcÝ tưởngtrái – phải xen kẽCách 1mô phỏng O(k²)Cách 2sàng + dequeTổng kếtkết quả chạy thật

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

Test	N	Chiều cao $a_i$	Số cây đặc biệt $k$	Có cây cao 1
1 – 20	3 … 20	1 … 99	0 … 9	16/20
21 – 75	10.000	1 … 9.999.885	851 … 1.003	55/55
76 – 85	100.000	1 … 9.999.991	8.020 … 8.294	10/10
86 – 100	1.000.000	1 … 9.999.996	72.141 … 73.100	15/15

• Bộ test có 100 test, khớp đúng 2 mức giới hạn của đề: test 1–75 có $N \le 10^4$ (20 test đầu chỉ có $N \le 20$), test 76–85 có $N = 10^5$ và test 86–100 có $N = 10^6$.
• Ở mọi test các chiều cao đều đôi một khác nhau đúng như đề nói, nên thứ tự "cây cao tiếp theo" luôn rõ ràng.
• Chỉ có test 2 (chính là ví dụ 2) phải in $-1$. Có 96 test chứa cây cao $1$ – nhớ rằng $1$ không phải số nguyên tố, ai quên điều kiện x < 2 sẽ sai ngay.
• Số cây đặc biệt $k$ lớn nhất là 73.100 (khoảng 7% số cây – đúng mật độ số nguyên tố quanh $10^7$).

Các subtask khớp với bộ test như sau (ô ghi số test đúng của từng cách – chạy thật):

Subtask	Điều kiện	Các test	Cách 1 C++	Cách 2 C++	Cách 1 Python	Cách 2 Python
1 (75%)	$N \le 10^4$	1 – 75	75/75	75/75	75/75	75/75
2 (25%)	$10^4 < N \le 10^6$	76 – 100	10/25	25/25	0/25	25/25

Ý tưởngCao nhất ở giữa, thấp dần ra hai bên

Nhìn lại cách bác Bình trồng: cây thứ $1$ (cao nhất) làm mốc ở giữa; các lần chẵn (lần 2, 4, 6, ...) luôn đặt vào đầu bên trái của hàng; các lần lẻ từ lần 3 trở đi (lần 3, 5, 7, ...) luôn đặt vào đầu bên phải. Vậy thuật toán gồm 3 bước:

Thuật toán

1. Lọc ra các chiều cao là số nguyên tố → mảng p (rỗng thì in $-1$).
2. Sắp xếp p giảm dần: p[0] là cây trồng lần 1, p[1] là lần 2, ...
3. Cho cây p[i] ($i$ đếm từ 0) vào hàng: $i$ lẻ (lần chẵn) thì thêm vào đầu trái, $i$ chẵn thì thêm vào đầu phải.

Thao tác "thêm vào đầu trái / đầu phải" chính là push_front / push_back của hàng đợi 2 đầu deque. Em nhập chiều cao các cây rồi bấm Tiếp để xem từng bước:

Chiều cao các cây:

Ví dụ nhanh:

Cách 1Mô phỏng đúng từng chữ của đề – O(k²)

Cách "nghe sao làm vậy": kiểm tra nguyên tố bằng cách thử chia tới $\sqrt{x}$; sau đó lặp $k$ lần, mỗi lần tìm cây cao nhất chưa trồng (duyệt cả mảng), rồi đặt vào bên trái bằng res.insert(res.begin(), ...) hoặc bên phải bằng push_back.

C++▶ Chạy tay từng dòng codeCách 1: thử chia kiểm tra nguyên tố, mỗi lần tìm cây cao nhất chưa trồng rồi chèn trái / thêm phải vào vector – O(k²).

Dữ liệu vào (stdin) – sửa thoải mái8 2 55 23 16 53 5 20 17

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Hàm isPrime trả về false ngay với $x < 2$ (số $1$ không nguyên tố), rồi thử chia $d = 2, 3, \ldots$ khi $d^2 \le x$.
2. Mảng used đánh dấu cây đã trồng để lần sau không chọn lại.
3. Hai chỗ chậm: tìm max mất $O(k)$ mỗi lần, và insert vào đầu vector phải dời cả mảng sang phải, cũng $O(k)$ → tổng $O(k^2)$. Với $k \approx 7 \cdot 10^4$ (test $N = 10^6$) là khoảng $5 \cdot 10^9$ phép → quá thời gian.

Không gian$O(N)$

Thời gian$O(N\sqrt{V} + k^2)$

Kết quả chạy thật: bản C++ đúng 85/100 test (quá 1 giây ở các test 86–100), test đúng chạy lâu nhất 0.189s; bản Python đúng 75/100 test (quá thời gian ở các test 76–100), lâu nhất 0.23s.

Thử nghiệm thêm (Cách 1b): nếu chỉ thay "tìm max mỗi lần" bằng một lần sort giảm dần (vẫn thử chia và vẫn insert vào đầu vector) thì trên bộ test này đã đúng 100/100 test, lâu nhất 0,49 giây. Lý do: insert đầu vector dời bộ nhớ bằng lệnh sao chép khối rất nhanh, còn thử chia chỉ tốn nhiều với các số nguyên tố. Tuy vậy về lý thuyết nó vẫn là $O(k^2)$, nên mình vẫn khuyên dùng deque như Cách 2.

Cách 2Sàng Eratosthenes + sắp xếp + deque

Ba cải tiến:

• Sàng Eratosthenes tới $10^7$ một lần ($O(V \log \log V)$, mảng bool 10 MB), sau đó kiểm tra mỗi số chỉ $O(1)$.
• Sắp xếp giảm dần một lần $O(k \log k)$ thay cho $k$ lần tìm max.
• deque: push_front và push_back đều $O(1)$.

C++▶ Chạy tay từng dòng codeCách 2: sàng Eratosthenes, sắp xếp giảm dần rồi push_front / push_back vào deque.

Dữ liệu vào (stdin) – sửa thoải mái8 2 55 23 16 53 5 20 17

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Vòng sàng chỉ cần chạy $i$ tới $\sqrt{10^7} \approx 3162$ và bắt đầu gạch từ $i \cdot i$ (các bội nhỏ hơn đã bị gạch bởi ước nhỏ hơn).
2. Mảng notPrime khai báo toàn cục nên tự động bằng false; nhớ gán notPrime[0] = notPrime[1] = true.
3. sort(..., greater<int>()) sắp xếp giảm dần.
4. $i$ đếm từ 0 nên i % 2 == 1 ứng với lần trồng thứ $i + 1$ chẵn → đặt bên trái.

Mẹo không cần deque: hàng cây kết quả chính là các phần tử có chỉ số lẻ của p viết theo thứ tự ngược ($\ldots, p_5, p_3, p_1$), nối với các phần tử chỉ số chẵn theo thứ tự xuôi ($p_0, p_2, p_4, \ldots$). Nhưng dùng deque thì code "kể lại" đúng câu chuyện của đề, dễ hiểu hơn.

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

Thời gian$O(V \log \log V + N + k \log k)$

Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.251s; bản Python đúng 100/100 test, lâu nhất 0.73s.

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. Mô phỏng đúng đề	C++	85/100	0.189s	Quá thời gian ở test 86–100
	Python	75/100	0.226s	Quá thời gian ở test 76–100
1b. Thử chia + sắp xếp + chèn đầu vector	C++	100/100	0.493s	Full điểm
2. Sàng + sắp xếp + deque	C++	100/100	0.251s	Full điểm
	Python	100/100	0.729s	Full điểm

Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy của mình (giới hạn 1 giây/test), với C++ thời gian Cách 2 phần lớn là để sàng tới $10^7$ và đọc $10^6$ số. Hai bẫy hay gặp của bài: quên rằng $1$ không phải số nguyên tố, và quên in $-1$ khi không có cây đặc biệt nào.

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 😇