Đa giác đều (Tin học trẻ toàn quốc 2024 – Vòng chung kết toàn quốc – Bảng B, C2)

Nguồn: Tin học trẻ 2024 Độ khó: Khá Tổ hợp Đếm phần bù Hai con trỏ

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2024 – Vòng chung kết toàn quốc – Bảng B và Bảng C2 (bài Đa giác đều). Đề bên dưới do mình viết lại bằng lời của mình cho dễ hiểu (giữ đúng nghĩa, đúng số liệu và ví dụ của đề gốc).

Cho một đa giác đều $n$ đỉnh, các đỉnh đánh số $1, 2, \dots, n$ theo chiều kim đồng hồ. Có $k$ đỉnh đã được tô màu.

Hãy đếm số cách chọn ba đỉnh khác nhau, cả ba đều là đỉnh được tô màu, sao cho tam giác tạo bởi ba đỉnh đó chứa tâm của đa giác. Tâm nằm trên cạnh của tam giác cũng được tính là chứa.

Lục giác đều đánh số 1 đến 6, tam giác 1-3-5 chứa tâm

Dữ liệu vào:

Dòng 1: hai số nguyên dương $n, k$ ($3 \le k \le n \le 10^6$).
Dòng 2: $k$ số nguyên $p_1 < p_2 < \dots < p_k$ ($1 \le p_i \le n$) – các đỉnh được tô màu.

Kết quả: một số nguyên là số cách chọn ba đỉnh thoả mãn.

Subtask:

Subtask 1 (25%): $n, k \le 500$;
Subtask 2 (25%): $n, k \le 5000$;
Subtask 3 (25%): $k = n$;
Subtask 4 (25%): 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

6 4
1 3 4 5

Ví dụ – output

Giải thích: các đỉnh tô màu là 1, 3, 4, 5. Có 4 bộ ba: $(1, 3, 4)$, $(1, 3, 5)$, $(1, 4, 5)$, $(3, 4, 5)$. Ba bộ đầu chứa tâm – trong đó với $(1, 3, 4)$ và $(1, 4, 5)$ tâm nằm đúng trên cạnh nối đỉnh 1 và đỉnh 4 (đường kính). Bộ $(3, 4, 5)$ nằm gọn ở nửa dưới nên không chứa tâm. Đáp án $3$.

Lời mở đầu

Bài này không cần tính toán hình học số thực chút nào: chỉ cần nhìn các cung mà ba đỉnh chia đường tròn ngoại tiếp. Mình đi từ duyệt mọi bộ ba $O(k^3)$, qua cố định hai đỉnh $O(k^2)$, tới đếm phần bù bằng hai con trỏ $O(n + k)$ – kỹ thuật đếm rất hay gặp.

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ộ test25 test Ý tưởngba cung Cách 1O(k³) – 25đ Cách 2O(k²) – 50đ Cách 3O(n + k) – 100đ Tổng kếtkết quả

Bộ testBộ test có gì?

Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ subtask của đề: 25 test (test 1 là ví dụ của đề). Ngoài dữ liệu ngẫu nhiên còn có: các đỉnh tô màu dồn trong nửa vòng tròn (đáp án 0), các cặp đỉnh đối xứng tâm (rất nhiều tam giác có tâm nằm trên cạnh), các đỉnh cách đều nhau.

Nhóm	Test	$n$ lớn nhất	$k$ nhỏ nhất – lớn nhất	Test có $k = n$	Số test $n$ chẵn	Đáp án = 0	Đáp án lớn nhất
Subtask 1	1–7	500	3 – 500	test 2, 6	5	test 4, 7	5.270.500
Subtask 2	8–13	5.000	714 – 5.000	test 8	4	test 13	5.214.580.000
Subtask 3	14–19	1.000.000	3 – 1.000.000	test 14–19	4	không có	41.666.916.666.000.000
Subtask 4	20–25	1.000.000	300.002 – 900.000	không có	5	test 23	30.374.995.992.605.356

Đáp án lên tới khoảng $4{,}2 \cdot 10^{16}$ – bắt buộc dùng long long. Riêng $\binom{k}{3}$ với $k = 10^6$: tích $k(k-1)(k-2) \approx 10^{18}$ vẫn vừa long long (tối đa khoảng $9{,}2 \cdot 10^{18}$).

Đã nộp thử trên bộ chấm chính thức

Lời giải cuối cùng trong bài mình đã nộp lên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được 100/100 điểm (AC).

Kết quả chạy thật các cách bên dưới theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 $O(k^3)$ C++	Cách 1 Python	Cách 2 $O(k^2)$ C++	Cách 3 $O(n + k)$ C++	Cách 3 Python
Subtask 1 (25%)	$n, k \le 500$	1–7	7/7	5/7	7/7	7/7	7/7
Subtask 2 (25%)	$n, k \le 5000$	8–13	1/6	0/6	6/6	6/6	6/6
Subtask 3 (25%)	$k = n$	14–19	3/6	2/6	3/6	6/6	6/6
Subtask 4 (25%)	không ràng buộc thêm	20–25	0/6	0/6	0/6	6/6	6/6

Ý tưởngBa cung và nửa vòng tròn

Ba đỉnh $a < b < c$ chia đường tròn ngoại tiếp thành 3 cung, đo bằng số cạnh của đa giác:

$$c_1 = b - a, \quad c_2 = c - b, \quad c_3 = n - (c - a), \qquad c_1 + c_2 + c_3 = n.$$

Nhận xét

Tam giác chứa tâm (kể cả tâm nằm trên cạnh) $\iff$ không có cung nào dài hơn nửa vòng, tức là $2c_1 \le n$, $2c_2 \le n$, $2c_3 \le n$.
Nếu có một cung dài hơn nửa vòng thì cả ba đỉnh nằm trong nửa vòng tròn còn lại – tam giác "lệch" hẳn về một phía, không chứa tâm. Nếu có cung dài đúng nửa vòng ($n$ chẵn, $2c = n$) thì cạnh tương ứng là một đường kính – tâm nằm trên cạnh, vẫn được tính.

Kiểm tra với ví dụ $n = 6$: bộ $(1, 3, 4)$ có các cung $2, 1, 3$ – cung lớn nhất bằng $3 = n/2$ nên tâm nằm trên cạnh 1–4, được tính. Bộ $(3, 4, 5)$ có cung $1, 1, 4$ mà $4 > 3$ nên không chứa tâm.

Đếm phần bù còn dễ hơn: một bộ ba "xấu" có đúng một cung lớn hơn nửa vòng. Đi theo chiều kim đồng hồ ngay sau cung lớn đó là đỉnh "đầu tiên" $x$ của bộ; hai đỉnh còn lại nằm trong cung ngắn $(x, x + D]$ với $D = \lfloor (n-1)/2 \rfloor$. Vậy với mỗi đỉnh tô màu $x$, đếm $cnt$ = số đỉnh tô màu trong $(x, x + D]$ (đi vòng), cộng $\binom{cnt}{2}$ – mỗi bộ xấu được đếm đúng một lần:

$$\text{đáp án} = \binom{k}{3} - \sum_{x} \binom{cnt_x}{2}.$$

Em nhập đa giác rồi bấm Tiếp: mỗi bước chọn một đỉnh tô màu $x$ (vàng), tô cam các đỉnh trong cung $(x, x + D]$, rồi cộng số bộ xấu có $x$ là đỉnh đầu:

n = Các đỉnh tô màu =

Ví dụ nhanh:

Cách 1Duyệt mọi bộ ba – O(k³) (Subtask 1)

Ba vòng lặp chọn $x < y < z$ trong dãy đỉnh tô màu, tính ba cung và kiểm tra điều kiện "mọi cung $\le n/2$". Viết 2 * c1 <= n thay cho c1 <= n / 2 để không bị lỗi chia nguyên khi $n$ lẻ.

C++▶ Chạy tay từng dòng codeCách 1: duyệt mọi bộ ba, tam giác chứa tâm khi cả ba cung ≤ n/2 (xanh = chứa tâm, đỏ = không).

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

Dữ liệu mẫu:

Không gian$O(k)$

Thời gian$O(k^3)$

Kết quả chạy thật: Bản C++ đúng 11/25 test, quá thời gian test 8–11, 13–15, 18, 20–25 (các test đúng chạy lâu nhất 0.199s). Bản Python đúng 7/25 test, quá thời gian test 2, 5, 8–15, 18–25 (các test đúng chạy lâu nhất 0.639s) (bản Python có thêm break khi cung thứ nhất đã quá nửa vòng nhưng vẫn chậm). Bản C++ ăn subtask 1 (25 điểm); với $k = 5000$ có khoảng $2 \cdot 10^{10}$ bộ ba – quá chậm. Vài test lẻ ở nhóm sau vẫn qua vì $k$ nhỏ.

Cách 2Cố định hai đỉnh, đếm đỉnh thứ ba bằng mảng cộng dồn – O(k²) (Subtask 1, 2)

Cố định $a = p_x < b = p_y$ với $2(b - a) \le n$. Đỉnh thứ ba $c > b$ phải thoả:

$2(c - b)$ $\le n \iff c$ $\le b + \lfloor n/2 \rfloor$;
$2(n - (c - a))$ $\le n \iff c$ $\ge a + \lceil n/2 \rceil$.

Vậy $c$ nằm trong đoạn $[lo, hi]$ với $lo = \max(b + 1, a + \lceil n/2 \rceil)$, $hi = \min(n, b + \lfloor n/2 \rfloor)$. Đếm số đỉnh tô màu trong một đoạn bằng mảng cộng dồn dau.

C++▶ Chạy tay từng dòng codeCách 2: cố định a, b; các đỉnh c hợp lệ là đoạn [lo, hi] (viền cam), đếm bằng mảng cộng dồn dau.

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

Dữ liệu mẫu:

(n + 1) / 2 chính là $\lceil n/2 \rceil$, n / 2 là $\lfloor n/2 \rfloor$.
Vì dãy $p$ tăng, khi $2(b - a) > n$ thì mọi $b$ sau còn xa hơn – break luôn.

Không gian$O(n)$

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

Kết quả chạy thật: Bản C++ đúng 16/25 test, quá thời gian test 14–15, 18, 20–25 (các test đúng chạy lâu nhất 0.018s) – qua subtask 1, 2 (50 điểm); với $k = 10^6$ thì $k^2/2$ cặp là quá nhiều.

Cách 3Đếm phần bù bằng hai con trỏ – O(n + k) (full)

Làm đúng như phần ý tưởng: đáp án $= \binom{k}{3} - \sum \binom{cnt}{2}$. Để đếm $cnt$ khi đi vòng, nhân đôi dãy: $q_{i + k} = p_i + n$. Khi $i$ tăng, đầu mút $q_i + D$ tăng nên con trỏ $r$ (đỉnh đầu tiên vượt quá $q_i + D$) chỉ tiến, không lùi – tổng cộng $O(k)$.

Gợi ý cho Subtask 3 ($k = n$)

Khi mọi đỉnh đều được tô thì $cnt = D$ với mọi đỉnh, nên đáp án là $\binom{n}{3} - n \binom{D}{2}$ – một công thức $O(1)$. Cách 3 chính là tổng quát hoá công thức này cho trường hợp chỉ một số đỉnh được tô.

C++▶ Chạy tay từng dòng codeCách 3: với mỗi đỉnh tô màu (vàng), con trỏ r đếm số đỉnh tô màu trong cung (q[i], q[i] + D] (ô xanh trên mảng q).

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

Dữ liệu mẫu:

Điều kiện r < i + k giữ cho cung đang xét không "vòng quá" một vòng (không đếm lại chính đỉnh $i$).
Kiểm tra ví dụ: $n = 6$, $D = 2$. Đỉnh 1: cung $(1, 3]$ có đỉnh 3 → $cnt = 1$; đỉnh 3: $(3, 5]$ có 4, 5 → $cnt = 2$, cộng 1; đỉnh 4: $(4, 6]$ có 5 → 0; đỉnh 5: $(5, 7]$ có đỉnh $7 \equiv 1$ → 0. Tổng bộ xấu $= 1$, đáp án $\binom{4}{3} - 1 = 3$. Đúng!

Không gian$O(k)$

Thời gian$O(k)$ (hai con trỏ)

Kết quả chạy thật: Bản C++ đúng 25/25 test, chạy lâu nhất 0.061s. Bản Python đúng 25/25 test, chạy lâu nhất 0.675s – Python cũng full nhờ đọc dữ liệu bằng sys.stdin.buffer và vòng lặp chỉ $O(k)$.

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)	Điểm theo subtask
1. Duyệt mọi bộ ba $O(k^3)$	C++	11/25	0.199s	25%
	Python	7/25	0.639s	0%
2. Cố định 2 đỉnh + mảng đếm $O(k^2)$	C++	16/25	0.018s	50%
3. Đếm phần bù + hai con trỏ	C++	25/25	0.061s	100%
	Python	25/25	0.675s	100%

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình (giới hạn 1 giây). Hai kỹ thuật đáng nhớ của bài: (1) biến điều kiện hình học "tam giác chứa tâm" thành điều kiện số nguyên "mọi cung ≤ nửa vòng" – không cần số thực, không lo sai số; (2) khi đếm trực tiếp khó, hãy đếm phần bù và tìm cho mỗi bộ "xấu" một đại diện duy nhất (ở đây là đỉnh đầu tiên sau cung lớn) để không đếm trù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 😇

Lập Trình Thuật Toán