Tuyển sinh 🎓 Mình nhận đào tạo lập trình giải thuật thi đấu: thi vào lớp 10 chuyên tin · thi học sinh giỏi tin học cấp tỉnh/thành · thi vào đội tuyển quốc gia · Olympic tin học sinh viên / ICPC · phỏng vấn thuật toán. Bấm vào đây để xem thông tin khóa học → Xem khóa học
Việt Nam Sơn
ZaloĐăng ký họcNhắn Zalo cho thầy

Đa giác lồi (Tin học trẻ toàn quốc 2025 – Vòng chung kết toàn quốc – Bảng C2)

Đa giác lồi
Nguồn: Tin học trẻ toàn quốc 2025 – Chung kết – Bảng C2 Độ khó: Khó Ngăn xếp đơn điệu Duyệt nửa nhỏ

Đề bài

🏆
Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng chung kết toàn quốc – Bảng C2. Đề dưới đây mình viết lại theo lời của mình cho dễ hiểu, giữ nguyên ý nghĩa, giới hạn và ví dụ của đề gốc.

Một xưởng mộc có $N$ khúc gỗ xếp thành một hàng, đánh số $1..N$ từ trái sang phải; khúc thứ $i$ dài $l_i$.

Một đoạn các khúc gỗ liên tiếp $l_i, l_{i+1}, \ldots, l_j$ ($1 \le i \le j \le N$) gọi là đạt chuẩn nếu có thể dùng tất cả các khúc trong đoạn, mỗi khúc làm một cạnh, xếp theo thứ tự tuỳ ý để ghép thành một đa giác lồi. Hãy đếm số đoạn đạt chuẩn.

Dữ liệu vào:

  • Dòng đầu là số nguyên $N$ $(1 \le N \le 3 \cdot 10^5)$.
  • Dòng thứ hai gồm $N$ số nguyên $l_1, l_2, \ldots, l_N$ $(1 \le l_i \le 10^9)$.

Kết quả: một số nguyên – số đoạn đạt chuẩn.

Subtask:

  • Subtask 1 ($30\%$ số điểm): $N = 3$.
  • Subtask 2 ($30\%$ số điểm): $N \le 5000$.
  • Subtask 3 ($20\%$ số điểm): $N \le 8 \cdot 10^4$.
  • Subtask 4 ($20\%$ số điểm): không có ràng buộc gì thêm.

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

Ví dụ – input
7
2 3 20 4 5 9 10
Ví dụ – output
7

Giải thích: có 7 đoạn đạt chuẩn: $(2, 3, 20, 4, 5, 9)$, $(2, 3, 20, 4, 5, 9, 10)$, $(3, 20, 4, 5, 9)$, $(3, 20, 4, 5, 9, 10)$, $(20, 4, 5, 9, 10)$, $(4, 5, 9, 10)$ và $(5, 9, 10)$. Chẳng hạn đoạn $(20, 4, 5, 9)$ không đạt vì cạnh $20$ dài hơn tổng $4 + 5 + 9 = 18$ của các cạnh còn lại.

Lời mở đầu

Bài trông như hình học nhưng thực chất là bài đếm đoạn con. Bước 1 là biến điều kiện "ghép được đa giác lồi" thành một bất đẳng thức đơn giản. Bước 2 là đếm nhanh: từ $O(N^2)$ (subtask 1, 2) lên tới $O(N \log^2 N)$ bằng hai kỹ thuật rất đáng học: ngăn xếp đơn điệu để tìm miền mà mỗi phần tử là lớn nhất, và "duyệt nửa nhỏ" để chặn trường hợp xấu.

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

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

Bộ test26 testÝ tưởng2·max < tổngCách 1O(N²)Cách 2max làm tâmCách 3nửa nhỏTổng kếtkết quả

Bộ testBộ test có gì?

Bộ test trên CLUE gồm 26 test (mình tự sinh theo đúng ràng buộc và tỉ lệ subtask của đề):

NhómTest$N$$l_i$Đáp án lớn nhất
Subtask 1 (30%)2–83 – 31 – 1.000.000.0001
Subtask 2 (30%)1, 9–155 – 5.0001 – 1.000.000.00012.492.501
Subtask 3 (20%)16–2079.999 – 80.0001 – 1.000.000.0003.199.827.626
Subtask 4 (20%)21–26300.000 – 300.0001 – 1.000.000.00044.999.550.001
  • Test 1 là ví dụ của đề ($N = 7$) – xếp vào subtask 2. Subtask 1 có đủ các trường hợp $N = 3$: tam giác đều, "tam giác dẹt" $1, 2, 3$ (không được tính), cạnh $10^9$...
  • Các test "đặc biệt": dãy toàn bằng nhau (test 13, 21), dãy Fibonacci $1, 1, 2, 3, 5, 8, \ldots$ (test 12, 22 – rất nhiều đoạn "dẹt"), lũy thừa của 2 (test 17), xen kẽ $10^9$ và số nhỏ (test 24), và dãy tăng dần $N = 3 \cdot 10^5$ (test 25).
  • Đáp án lên tới khoảng $4{,}5 \cdot 10^{10}$ và $2 \cdot l_i$ tới $2 \cdot 10^9$ – phải dùng long long.

Kết quả chạy thật của 3 cách (C++) theo từng subtask:

SubtaskĐiều kiệnTestCách 1
$O(N^2)$		Cách 2
max làm tâm		Cách 3
duyệt nửa nhỏ
Subtask 1 (30%)$N = 3$2–8quaquaqua
Subtask 2 (30%)$N \le 5000$1, 9–15quaquaqua
Subtask 3 (20%)$N \le 8 \cdot 10^4$16–20quá thời gianquaqua
Subtask 4 (20%)$N \le 3 \cdot 10^5$21–26quá thời gian5/6 testqua

Lời giải cách 3 (C++) mình đã nộp thử trên hệ thống chấm chính thức của hội thi (tinhoctre.vn) và đạt AC 100/100 điểm.

Ý tưởngĐa giác lồi ⇔ 2·max < tổng

Định lý (bất đẳng thức đa giác)
Các đoạn thẳng dài $c_1, c_2, \ldots, c_k$ ghép được thành một đa giác (không suy biến) khi và chỉ khi cạnh dài nhất nhỏ hơn tổng các cạnh còn lại: $\max c < S - \max c$, tức là $2 \cdot \max c < S$ với $S$ là tổng. Khi đó luôn có thể xếp thành đa giác lồi (ví dụ đặt các đỉnh trên một đường tròn đủ lớn).
  • Chiều "chỉ khi": trong một đa giác, mỗi cạnh là đường thẳng nối hai đỉnh, còn các cạnh còn lại là một đường gấp khúc nối hai đỉnh đó – đường thẳng luôn ngắn hơn (bất đẳng thức tam giác mở rộng). Trường hợp bằng nhau thì đa giác "dẹt" thành đoạn thẳng – không phải đa giác lồi.
  • Đoạn 1 hay 2 khúc gỗ tự động bị loại: 1 khúc thì $2c > c$; 2 khúc thì $2\max \ge c_1 + c_2$.
  • Với tam giác ($N = 3$) đây chính là bất đẳng thức tam giác quen thuộc: $3, 4, 5$ được; $1, 2, 3$ không được (dẹt).

Vậy bài toán trở thành: đếm số đoạn $[i, j]$ có $2 \cdot \max(l_i..l_j) < l_i$ $+ \ldots + l_j$.

Đếm nhanh: cho mỗi phần tử làm "max". Với mỗi vị trí $m$, xét các đoạn mà $l_m$ là phần tử lớn nhất (nếu có nhiều phần tử bằng nhau thì quy ước lấy cái bên trái nhất để mỗi đoạn được đếm đúng một lần). Gọi $L[m]$ là vị trí gần nhất bên trái có $l \ge l_m$, $R[m]$ là vị trí gần nhất bên phải có $l > l_m$. Các đoạn nhận $m$ làm max chính là $[i, j]$ với $L[m] < i \le m \le j < R[m]$. Với tổng tiền tố $P$, điều kiện là

$$P[j] - P[i-1] > 2 \cdot l_m.$$

Vì $l_k \ge 1$ nên $P$ tăng ngặt: cố định $i$ thì các $j$ thoả mãn là một đoạn cuối của $[m, R[m]-1]$, tìm ranh giới bằng chặt nhị phân. Em nhập dãy rồi bấm Tiếp để xem từng phần tử làm "tâm" (ô vàng), miền của nó (ô tím), và các đoạn đạt chuẩn được đếm:

Chú thích: ô vàng = vị trí m làm max, ô tím = miền mà lm là max, viền cam = đầu đang duyệt, ô xanh = phía bên kia ghép được đoạn đạt chuẩn.
Ví dụ nhanh:

Cách 1Duyệt mọi đoạn – O(N²)

Cố định đầu trái $i$, kéo dài đầu phải $j$ và cập nhật tổng, max theo từng bước – mỗi đoạn kiểm tra trong $O(1)$.

C++▶ Chạy tay từng dòng codeCách 1: cố định i, kéo dài j và cập nhật tổng, max – kiểm tra 2·max < tổng.
Dữ liệu mẫu:
Không gian$O(N)$
Thời gian$O(N^2)$

Kết quả chạy thật: bản C++ đúng 15/26 test – quá thời gian test 16–26 (test đúng chạy lâu nhất 0,018 giây). Bản Python đúng 10/26 test – quá thời gian test 11–26 (test đúng chạy lâu nhất 0,021 giây). C++ qua subtask 1, 2 ($N \le 5000$, khoảng $1{,}25 \cdot 10^7$ đoạn); với $N = 8 \cdot 10^4$ đã là $3{,}2 \cdot 10^9$ đoạn – quá chậm.

Cách 2Mỗi phần tử làm max + chặt nhị phân

Tìm $L[m]$, $R[m]$ cho mọi $m$ bằng ngăn xếp đơn điệu trong $O(N)$: duyệt từ trái sang phải, bỏ khỏi đỉnh ngăn xếp các phần tử nhỏ hơn $l_i$; phần tử còn lại ở đỉnh là vị trí gần nhất bên trái có $l \ge l_i$. Làm tương tự từ phải sang trái với điều kiện bỏ các phần tử $\le l_i$ (để phần tử bằng nhau bên phải không "chặn", đúng quy ước lấy max bên trái nhất). Sau đó với mỗi $m$, duyệt mọi đầu trái $i \in [L[m]+1, m]$ và chặt nhị phân đầu phải.

C++▶ Chạy tay từng dòng codeCách 2: ngăn xếp đơn điệu tìm miền [L+1, R−1] của mỗi max, duyệt đầu trái và chặt nhị phân đầu phải.
Dữ liệu mẫu:
  1. upper_bound(P.begin() + m, P.begin() + hi + 1, x) trả về vị trí $j$ đầu tiên trong $[m, hi]$ có $P[j] > x$ (hoặc $hi + 1$ nếu không có), nên số đầu phải hợp lệ là $hi + 1 - j$.
  2. Mỗi đoạn $[i, j]$ có đúng một max "bên trái nhất" nên được đếm đúng một lần.
Không gian$O(N)$
Thời gian$O(N^2 \log N)$ xấu nhất (dãy tăng)

Kết quả chạy thật: bản C++ đúng 25/26 test – quá thời gian test 25 (test đúng chạy lâu nhất 0,059 giây). Bản Python đúng 23/26 test – quá thời gian test 22–23, 25 (test đúng chạy lâu nhất 0,481 giây).

Trường hợp xấu: dãy tăng dần
Với dãy ngẫu nhiên, miền của mỗi phần tử khá ngắn nên cách 2 chạy rất nhanh. Nhưng với dãy tăng dần (test 25), phần tử thứ $m$ là max của mọi đoạn $[i, m]$, $i = 1..m$ – phía trái dài $m$, phía phải chỉ dài $1$. Duyệt phía trái tốn tổng $1 + 2 + \ldots + N \approx 4{,}5 \cdot 10^{10}$ lần chặt nhị phân → quá thời gian. Trong khi nếu duyệt phía phải (chỉ 1 phần tử) thì xong ngay!

Cách 3Duyệt nửa nhỏ – O(N log² N)

Sửa đúng một chỗ: với mỗi $m$, duyệt phía ngắn hơn trong hai phía $[L[m]+1, m]$ và $[m, R[m]-1]$, chặt nhị phân ở phía dài hơn:

  • Phía trái ngắn hơn: như cách 2.
  • Phía phải ngắn hơn: duyệt $j$, đếm số $k = i - 1 \in [L[m], m-1]$ có $P[k] < P[j] - 2l_m$ bằng lower_bound.
Vì sao chỉ O(N log² N)?
Hãy tưởng tượng chia đôi mảng tại vị trí max, rồi đệ quy hai nửa (đúng như cây "Cartesian"). Mỗi lần ta trả chi phí bằng nửa nhỏ hơn. Một phần tử mỗi khi bị "tính tiền" thì nó nằm ở nửa nhỏ, nên đoạn chứa nó lần sau có độ dài ít nhất gấp đôi ⇒ mỗi phần tử bị tính tối đa $\log_2 N$ lần. Tổng số lần duyệt $O(N \log N)$, mỗi lần chặt nhị phân thêm $O(\log N)$.
C++▶ Chạy tay từng dòng codeCách 3: như cách 2 nhưng luôn duyệt phía ngắn hơn, chặt nhị phân phía dài hơn.
Dữ liệu mẫu:
Phần tính L, R bằng ngăn xếp đã mô phỏng chi tiết ở cách 2 nên ở đây gộp thành 1 bước.
Không gian$O(N)$
Thời gian$O(N \log^2 N)$

Kết quả chạy thật: bản C++ đúng 26/26 test, chậm nhất 0,050 giây. Bản Python đúng 26/26 test, chậm nhất 0,776 giây.

Tổng kếtKết quả

CáchC++Python
1. Duyệt mọi đoạn $O(N^2)$15/26 test10/26 test
2. Max làm tâm, duyệt bên trái25/26 test23/26 test
3. Max làm tâm, duyệt nửa nhỏ26/26 test26/26 test
Ghi chú của mình: chỉ cách 3 qua trọn 4 subtask (C++ chậm nhất 0,050 giây); bản C++ này cũng đã đạt 100 điểm trên hệ thống chấm chính thức. Cách 2 "suýt" full điểm – chỉ trượt đúng test dãy tăng dần – một ví dụ rất rõ cho thấy tại sao cần kỹ thuật duyệt nửa nhỏ. Nhớ dùng long long cho tổng, cho $2 l_m$ và cho đáp án.
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 😇

Nhận xét

Đăng nhận xét

Đăng ký: Đăng Nhận xét (Atom)