Ốc biển
Đề 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.
6
6 5 8 8 3 648
6 1 2 2 7 6 2 55Lờ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à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ộ 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$ |
- 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.
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:
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.
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.
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ỏ.
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.
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 |
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ố.
Nhận xét
Đăng nhận xét