Ốc biển

Nguồn: Đề chọn đội tuyển HSG tỉnh – THPT Lê Văn Hưu (Thanh Hoá) 2024–2025 Độ khó: Dễ Map Set Đếm giá trị khác nhau

Đề bài

Bài 1 – Ốc biển (chương trình BAI1.*, dữ liệu BAI1.INP, kết quả BAI1.OUT).

Tiên Trang là vùng biển huyện Quảng Xương, tỉnh Thanh Hoá. Nơi đây đang được đầu tư xây dựng và hứa hẹn trở thành một điểm du lịch, nghỉ dưỡng hấp dẫn.

Trong một lần đến thăm Tiên Trang, Nam đi dạo dọc bờ biển và nhặt được những vỏ ốc có kích thước tương ứng là các số $a_1, a_2, \ldots, a_n$. Nam muốn lựa chọn một số vỏ ốc để xâu lại thành một chuỗi, sao cho khi tính từ đầu chuỗi đến cuối chuỗi các vỏ ốc phía sau có kích thước lớn hơn vỏ ốc phía trước.

Yêu cầu: Hãy tìm số vỏ ốc nhiều nhất mà Nam có thể chọn được.

Dữ liệu vào: File BAI1.INP gồm 2 dòng:

• Dòng đầu là số nguyên dương $n$ $(1 \le n \le 10^6)$.
• Dòng thứ hai ghi dãy các số nguyên dương $a_1, a_2, \ldots, a_n$ $(a_i \le 10^9, 1 \le i \le n)$, mỗi số cách nhau 1 khoảng trắng.

Dữ liệu ra: File BAI1.OUT ghi số vỏ ốc nhiều nhất mà Nam có thể xâu được thành chuỗi.

Giới hạn dữ liệu: Trong bộ test của bài sẽ có:

• 60% test với $0 < n$, $a_i \le 10^3$;
• 20% test với $10^3 < n$, $a_i \le 10^5$;
• (phần còn lại của ảnh đề bị cắt mất – theo giới hạn chung thì 20% test còn lại có $n \le 10^6$, $a_i \le 10^9$).

Giới hạn: 1 giây, 256 MB. Trên CLUE OJ dữ liệu đọc/ghi qua file BAI1.INP / BAI1.OUT.

Ví dụ 1 – input

6
6 5 8 8 3 6

Ví dụ 1 – output

4

Ví dụ 2 – input

8
6 1 2 2 7 6 2 5

Ví dụ 2 – output

5

Lời mở đầu

Đây là bài 1 (bài dễ nhất) của đề chọn đội tuyển HSG tỉnh Thanh Hoá. Nhiều bạn đọc thấy "phía sau lớn hơn phía trước" là nghĩ ngay tới dãy con tăng dài nhất (LIS) – và thế là sai ngay test ví dụ! Mình sẽ phân tích vì sao, rồi đi qua 4 cách cài đặt, mỗi cách đều chạy thật trên 20 test của CLUE OJ.

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ộ test20 testÝ tưởngĐếm khác nhauCách 1O(n²)Cách 2Mảng đánh dấuCách 3setCách 4Sắp xếp

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

Bộ test chỉ có 20 test, mình liệt kê hết:

Test	n	Số lượng số thực có	ai nhỏ nhất	ai lớn nhất	Đáp án
1	6	6	2	8	4
2	8	8	1	7	5
3	1	1	11	11	1
4	2	2	1	1	1
5	10	10	1	10	10
6	10	10	1	10	10
7	10	10	1	10	2
8	10	10	1	2	2
9	99.999	100.000	0	99.998	63.322
10	10.000	10.000	1	10.000	10.000
11	9.999	9.999	1	9.999	9.999
12	1.000.000	1.000.000	1	1.000.000	1.000.000
13	1.000.000	1.000.000	2.947	999.999.436	999.467
14	1.000.000	1.000.000	1	1.000.000	999.995
15	10	10	3	19	6
16	15	15	3	8	4
17	20	20	1	1	1
18	40	40	1	147	12
19	100	100	0	147	30
20	80	80	1	147	27

Subtask	Điều kiện (theo đề)	Các test	Thực tế
1 (60%)	$n, a_i \le 10^3$	1, 2, 3, 4, 5, 6, 7, 8, 15–20 (14 test)	$n \le 100$, $a_i \le 147$
2 (20%)	$n, a_i \le 10^5$	9, 10, 11 (3 test)	$n$ từ 9.999 đến 99.999, $a_i \le$ 99.998
3 (20%)	(ảnh đề bị cắt) $n \le 10^6$, $a_i \le 10^9$	12, 13, 14 (3 test)	$n = 10^6$; chỉ test 13 có $a_i$ tới gần $10^9$

Hai điều "lạ" trong bộ test (các dòng tô đỏ ở bảng trên)

• Test 9 ghi $n = 99999$ nhưng dòng 2 lại có 100000 số. Đáp án của test chỉ tính $n$ số đầu, nên code phải đọc đúng $n$ số. Nếu đọc "tới hết file" (kiểu Python split() rồi lấy hết) sẽ đếm thừa 1 giá trị và sai test này.
• Test 9 và test 19 có giá trị $a_i = 0$, dù đề nói là số nguyên dương. Mảng đánh dấu nhớ dùng được cả chỉ số 0.

Ý tưởngKhông phải dãy con tăng – mà là đếm giá trị khác nhau

Thử với ví dụ 1: 6 5 8 8 3 6. Nếu bắt buộc giữ nguyên thứ tự thì dãy con tăng dài nhất chỉ dài 2 (ví dụ 5 8 hay 3 6). Nhưng đáp án là 4! Vì Nam đã nhặt các vỏ ốc lên tay rồi mới xâu, nên Nam được sắp xếp lại tuỳ ý: chuỗi 3 – 5 – 6 – 8 dài 4.

Mấu chốt

Chuỗi phải tăng ngặt nên không thể có 2 vỏ cùng kích thước. Ngược lại, mỗi kích thước khác nhau lấy đúng 1 vỏ rồi xếp tăng dần là được một chuỗi hợp lệ. Vậy đáp án = số giá trị khác nhau trong dãy $a$.

Ví dụ 2: 6 1 2 2 7 6 2 5 có các giá trị khác nhau $\{1, 2, 5, 6, 7\}$ → đáp án 5 ✓. Em nhập dãy kích thước rồi bấm Tiếp để xem Nam xâu chuỗi:

Kích thước các vỏ

Ví dụ nhanh:

Bài toán "đếm số giá trị khác nhau" có nhiều cách làm, tuỳ giới hạn $n$ và $a_i$:

Cách 1Kiểm tra từng số đã xuất hiện trước đó chưa – O(n²)

Một giá trị được đếm đúng 1 lần nếu ta chỉ đếm ở lần xuất hiện đầu tiên của nó: với mỗi $i$, duyệt lại các $j < i$ xem có $a_j = a_i$ không.

C++▶ Chạy tay từng dòng codeCách 1: với mỗi a[i], duyệt lại các vị trí trước xem đã có giá trị đó chưa.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(n)$

Thời gian$O(n^2)$

Kết quả chạy thật: bản C++ đúng 16/20 test – ăn trọn Subtask 1; sai các test 9, 12, 13, 14 (quá thời gian); test đúng chậm nhất chạy 0,03s. Bản Python đúng 14/20 test – ăn trọn Subtask 1; sai các test 9, 10, 11, 12, 13, 14 (quá thời gian); test đúng chậm nhất chạy 0,02s. Với $n = 10^4$ (test 10, 11) thì $\frac{n^2}{2} = 5 \cdot 10^7$ phép so sánh vẫn kịp, còn $n \ge 10^5$ thì không.

Cách 2Mảng đánh dấu – O(n + max a)

Khi $a_i$ nhỏ, ta dùng mảng mark[x] đánh dấu giá trị $x$ đã gặp chưa. Mỗi số chỉ tốn $O(1)$. Mảng bool $10^6 + 1$ phần tử chỉ tốn 1 MB.

C++▶ Chạy tay từng dòng codeCách 2: mảng đánh dấu mark[x].

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(\max a_i)$

Thời gian$O(n)$

Kết quả chạy thật: bản C++ đúng 19/20 test – ăn trọn Subtask 1, Subtask 2; sai test 13 (lỗi chạy); test đúng chậm nhất chạy 0,08s. Bản Python đúng 19/20 test – ăn trọn Subtask 1, Subtask 2; sai test 13 (lỗi chạy); test đúng chậm nhất chạy 0,55s. Test 13 có $a_i$ tới gần $10^9$ nên mark[x] truy cập ra ngoài mảng → lỗi. Không thể khai mảng $10^9$ phần tử trong 256 MB.

Cách 3Dùng set – gọn nhất

set tự động loại phần tử trùng, nên chỉ cần bỏ hết vào set rồi in s.size(). Không quan tâm $a_i$ lớn hay nhỏ.

C++▶ Chạy tay từng dòng codeCách 3: bỏ hết vào set, in kích thước set.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(n)$

Thời gian$O(n \log n)$

Kết quả chạy thật: bản C++ đúng 19/20 test – ăn trọn Subtask 1, Subtask 2; sai test 13 (quá thời gian); test đúng chậm nhất chạy 0,40s. Riêng test 13 ($10^6$ số gần như khác nhau hết, giá trị tới $10^9$) mất khoảng 1,65s CPU trên máy mình: set là cây đỏ đen, mỗi lần chèn phải cấp phát một nút và đi qua khoảng 20 nút rải rác trong bộ nhớ, nên hằng số rất lớn. Bản Python dùng set (bảng băm) của Python lại đúng 20/20 test – ăn trọn Subtask 1, Subtask 2, Subtask 3; test đúng chậm nhất chạy 0,34s.

Cách 4Sắp xếp rồi đếm – Full điểm, nhanh nhất

Sau khi sắp xếp, các giá trị bằng nhau đứng liền nhau. Một giá trị mới xuất hiện tại vị trí $i$ khi $i = 0$ hoặc $a_i \ne a_{i-1}$. Sắp xếp một mảng liên tục trong bộ nhớ nhanh hơn chèn vào set rất nhiều.

C++▶ Chạy tay từng dòng codeCách 4 (full điểm): sắp xếp, đếm các vị trí có giá trị khác phần tử đứng trước.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(n)$

Thời gian$O(n \log n)$

Kết quả chạy thật: bản C++ đúng 20/20 test – ăn trọn Subtask 1, Subtask 2, Subtask 3; test đúng chậm nhất chạy 0,18s. Bản Python đúng 20/20 test – ăn trọn Subtask 1, Subtask 2, Subtask 3; test đúng chậm nhất chạy 0,96s. (Trong C++ còn có thể viết gọn sort + unique: n2 = unique(a.begin(), a.end()) - a.begin().)

Tổng kếtKết quả chạy thật của các cách

Cách	Subtask 1 test 1, 2, 3, 4, 5, 6, 7, 8, 15–20	Subtask 2 test 9, 10, 11	Subtask 3 test 12, 13, 14	Tổng	Chậm nhất (test đúng)
Cách 1 – C++	14/14	2/3 quá thời gian	0/3 quá thời gian	16/20	0,03s
Cách 1 – Python	14/14	0/3 quá thời gian	0/3 quá thời gian	14/20	0,02s
Cách 2 – C++	14/14	3/3	2/3 lỗi chạy	19/20	0,08s
Cách 2 – Python	14/14	3/3	2/3 lỗi chạy	19/20	0,55s
Cách 3 – C++	14/14	3/3	2/3 quá thời gian	19/20	0,40s
Cách 3 – Python	14/14	3/3	3/3	20/20	0,34s
Cách 4 – C++	14/14	3/3	3/3	20/20	0,18s
Cách 4 – Python	14/14	3/3	3/3	20/20	0,96s

Ghi chú của mình: số liệu trên là chạy thật trên 20 test của CLUE OJ với giới hạn 1 giây; thời gian là thời gian CPU trên máy của mình (biên dịch g++ -O2), máy chấm thật có thể nhanh hơn nên bản set có thể vẫn qua. Cách 4 (sắp xếp) bản C++ đạt 20/20 test và an toàn nhất. Nhớ đọc đúng $n$ số vì test 9 bị thừa 1 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 😇