Đếm cực tiểu địa phương

Nguồn: CLUE OJ Độ khó: Dễ Mảng 1 chiều So sánh phần tử kề

Đề bài

Cho số nguyên dương $N$ và dãy số nguyên $A_1, A_2, \ldots, A_N$. Phần tử $A_i$ được gọi là cực tiểu địa phương nếu nó nhỏ hơn hẳn các phần tử kề với nó:

• Nếu $i = 1$ thì $A_1 < A_2$.
• Nếu $i = N$ thì $A_N < A_{N-1}$.
• Còn lại ($1 < i < N$) thì $A_i < A_{i-1}$ và $A_i < A_{i+1}$.

Hãy đếm số lượng phần tử là cực tiểu địa phương có trong dãy $A$.

Dữ liệu vào:

• Dòng đầu là số nguyên dương $N$.
• Dòng thứ hai gồm $N$ số nguyên $A_1, A_2, \ldots, A_N$.

Kết quả:

In ra số lượng cực tiểu địa phương đếm được.

Giới hạn:

• $2 \le N < 35$
• $|A_i| < 10^{18}$ (các $A_i$ là số nguyên, có thể bằng nhau)

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

5
6 2 3 1 8

Ví dụ 1 – output

2

Các phần tử cực tiểu địa phương là $2$ (nhỏ hơn cả $6$ và $3$) và $1$ (nhỏ hơn cả $3$ và $8$).

Nguồn: phỏng theo bài "MẢNG 5.11" – vinhdinhcoder.net (chủ đề Mảng 1 chiều).

Lời mở đầu

Một phần tử là cực tiểu địa phương nếu nó nhỏ hơn hẳn các "hàng xóm" kề bên. Phần khó không nằm ở phép so sánh mà ở hai đầu dãy: phần tử đầu chỉ có hàng xóm bên phải, phần tử cuối chỉ có hàng xóm bên trái. Ghi chú: đề gốc ghi "dãy số thực" nhưng phần dữ liệu và ràng buộc lại là số nguyên tới $10^{18}$ – mình giữ số nguyên (đọc bằng double sẽ mất chính xác). Với $N = 1$ thì không có phần tử $A_2$ để so nên mình chốt $N \ge 2$.

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ưởng3 trường hợp: đầu, giữa, cuốiLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

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

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau.

Test	Nội dung kiểm tra
1	Ví dụ của đề
2–4	$N = 2$, các phần tử bằng nhau – so sánh <= thay cho < bị sai
5–8	Dãy tăng, giảm, răng cưa – cực trị nằm ở hai đầu dãy
9, 13	Có các cặp số bằng nhau kề nhau, số âm
10–12, 15, 18	Các số cỡ $10^{18}$ hoặc quanh $2^{32}$ chỉ hơn kém nhau 1–2 đơn vị – double và int so sánh sai
14–20	Dãy ngẫu nhiên tới 34 phần tử

Ý tưởngXét đúng 3 trường hợp vị trí

Duyệt $i$ từ 1 tới $N$, với mỗi $i$ kiểm tra theo đúng định nghĩa:

• $i = 1$: chỉ cần a[1] < a[2].
• $i = N$: chỉ cần a[N] < a[N-1].
• Còn lại: a[i] < a[i-1] && a[i] < a[i+1].

Chú ý

Phần tử đầu và cuối cũng có thể là cực tiểu: dãy 1 2 3 có cực tiểu là 1 (đầu dãy). Và "hẳn" nghĩa là so sánh nghiêm ngặt (<), hai số bằng nhau thì không phải cực trị.

Em nhập dãy rồi bấm Tiếp để xem từng phần tử được so với hàng xóm:

Dãy A =

Ví dụ nhanh:

Lời giảiMột vòng lặp với ba nhánh if

Mảng kiểu long long, đọc chính xác số nguyên tới $10^{18}$.

C++▶ Chạy tay từng dòng codeKiểm tra từng vị trí theo 3 trường hợp: đầu, cuối, giữa.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Không được dùng a[i-1] khi i = 1 hay a[i+1] khi i = N: đó là ô ngoài dãy (trong C++ thường chứa số 0 hoặc rác) – vì thế mới cần tách hai đầu ra riêng.
2. Python: a[i-1] với i = 0 là a[-1] – phần tử cuối dãy! Không lỗi chạy nhưng sai kết quả, nên càng phải tách riêng hai đầu.

Không gian$O(N)$

Thời gian$O(N)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.003s. Bản Python đúng 20/20 test, chạy lâu nhất 0.019s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Đọc bằng double (vì đề gốc ghi "số thực")	16/20	sai test 10, 11, 15, 18
Chỉ xét các phần tử ở giữa, bỏ hai đầu dãy	10/20	sai test 2, 5, 6, 7, 11, 13, 14, 15, 17, 19
So sánh <= thay cho <	13/20	sai test 3, 4, 9, 15, 16, 18, 19
Dùng int	14/20	sai test 10, 11, 12, 15, 18, 20

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ú
Lời giải chuẩn	C++	20/20	0.003s	Full điểm
	Python	20/20	0.019s	Full điểm
Dùng double	C++	16/20	–	Mất 4 test
Bỏ hai đầu	C++	10/20	–	Mất 10 test
So sánh <=	C++	13/20	–	Mất 7 test
Dùng int	C++	14/20	–	Mất 6 test

Ghi chú của mình: bài nào có công thức "khác" ở phần tử đầu và cuối thì hãy viết riêng ba trường hợp cho rõ ràng; gộp chung cho gọn rất dễ đọc ra ngoài mảng.

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 😇