Đ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)
Đề bài
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.
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.
6 4
1 3 4 53Giả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.
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 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}$).
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.$$
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:
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ẻ.
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.
(n + 1) / 2chính là $\lceil n/2 \rceil$,n / 2là $\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 –
breakluôn.
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)$.
- Điều kiện
r < i + kgiữ 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!
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% |