Tập đoạn tốt (HSG 9 Hà Nội 2024)

Nguồn: Đề thi HSG lớp 9 thành phố Hà Nội 2024 (Bài V) Độ khó: Khá Gộp đoạn Nghịch đảo modulo map

Đề bài

Một đoạn thẳng được mô tả bằng một cặp số nguyên $[L, R]$. Hai đoạn thẳng được gọi là giao nhau nếu chúng có ít nhất một điểm chung.

Một tập đoạn tốt là tập các đoạn thẳng sao cho với mỗi một đoạn thẳng trong tập, đều giao nhau với ít nhất một đoạn thẳng khác trong tập đó (coi tập đoạn thẳng chỉ có một đoạn thẳng duy nhất là tập đoạn tốt). Ví dụ, tập $\{[1,3], [4,5], [5,7], [3,4]\}$ hay $\{[1,4], [2,3]\}$ là một tập đoạn tốt, còn $\{[1,4], [3,5], [6,7]\}$ thì không phải là tập đoạn tốt. Độ tốt của một tập đoạn tốt là số lượng các đoạn trong tập đó.

Lưu ý: hai tập đoạn tốt có ít nhất một điểm chung sẽ được gộp thành một tập đoạn tốt.

Yêu cầu: ban đầu tập đoạn thẳng không có đoạn thẳng nào. Cho $N$ đoạn thẳng, mỗi lần lấy một đoạn thẳng theo thứ tự thêm vào tập đoạn thẳng, yêu cầu tính tích độ tốt của các tập đoạn tốt được sinh ra từ tập đoạn thẳng hiện tại. Do kết quả rất lớn, in ra phần dư của đáp án sau khi chia cho $10^9 + 7$.

Dữ liệu vào từ file văn bản DOANTOT.INP: dòng đầu tiên chứa số nguyên dương $N$ $(N \le 10^5)$ là số đoạn thẳng lần lượt được thêm vào; $N$ dòng tiếp, mỗi dòng chứa hai số nguyên dương $L, R$ $(L \le R \le 10^9)$ mô tả một đoạn thẳng.

Kết quả ghi ra file văn bản DOANTOT.OUT gồm $N$ dòng, dòng thứ $i$ $(1 \le i \le N)$ chứa một số nguyên là kết quả theo yêu cầu đề bài khi thêm đoạn thẳng thứ $i$.

Ràng buộc:

• Có $20\%$ số test có $L = R$; $N \le 30$;
• Có $30\%$ số test có $R \le 1000$;
• Có $20\%$ số test có $N \le 2000$;
• Có $30\%$ số test không có ràng buộc gì thêm.

Ví dụ – input

6
1 3
4 5
5 7
3 4
8 10
9 11

Ví dụ – output

1
1
2
4
4
8

Giải thích: lần 1 có 1 tập $\{[1,3]\}$ → $1$. Lần 2 có $\{[1,3]\}$ và $\{[4,5]\}$ → $1 \times 1 = 1$. Lần 3 có $\{[1,3]\}$ và $\{[4,5], [5,7]\}$ → $1 \times 2 = 2$. Lần 4 đoạn $[3,4]$ nối tất cả thành 1 tập 4 đoạn → $4$. Lần 5 thêm tập $\{[8,10]\}$ → $4 \times 1 = 4$. Lần 6 có $\{[8,10], [9,11]\}$ → $4 \times 2 = 8$.

Lưu ý nộp bài: trên CLUE OJ bài này đọc từ bàn phím và in ra màn hình. Code của mình có dòng if (fopen("DOANTOT.INP", "r")) { … } nên nộp đi thi đọc tệp cũng được.

Lời mở đầu

"Tập đoạn tốt" thực chất là các nhóm đoạn dính liền nhau (thành phần liên thông nếu nối hai đoạn giao nhau). Mỗi lần thêm một đoạn, đoạn mới có thể "dán" nhiều nhóm lại với nhau. Có hai khó khăn: tìm nhanh các nhóm bị dán, và cập nhật tích theo modulo khi một số thừa số biến mất – việc này cần đến nghịch đảo modulo, kiến thức trọng tâm của chương đồng dư.

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ộ test40 test tự sinhÝ tưởngnhóm = khoảng liềnCách 1DSU O(N²)Cách 2map + nghịch đảoTổng kếtkết quả chạy thật

Bộ testBộ test tự sinh

Không có bộ test chính thức để tải

Bài này trên CLUE OJ dùng chung (mirror) bộ test của bài gốc ở hệ thống khác, nên không tải được bộ test chính thức. Để vẫn có "kết quả chạy thật", mình tự sinh 40 test bám đúng 4 mức ràng buộc của đề, và kiểm tra đáp án bằng 3 cách độc lập: một chương trình "trâu" tính lại các nhóm từ đầu sau mỗi lần thêm (test nhỏ), cách 1 ($N \le 2000$) và bản Python của cách 2 (mọi test).

Test	Mức	$N$	Toạ độ lớn nhất
1 – 8	$L = R$, $N \le 30$	10 – 28	59
9 – 20	$R \le 1000$	50 000 – 100 000	1 000
21 – 28	$N \le 2000$	2 000	$\approx 10^9$
29 – 40	tổng quát	100 000	$10^9$

Ý tưởngMỗi tập đoạn tốt phủ đúng một khoảng liền

Các đoạn trong cùng một tập nối với nhau thành một dải không đứt, nên hợp của chúng là một khoảng $[\min L, \max R]$. Hai tập khác nhau thì hai khoảng rời nhau (nếu có điểm chung thì đã bị gộp). Vậy ta chỉ cần lưu danh sách các khoảng rời nhau, sắp theo đầu trái, kèm số đoạn của mỗi khoảng.

Khi thêm đoạn $[l, r]$: các khoảng có điểm chung với nó là các khoảng $[a, b]$ có $a \le r$ và $b \ge l$ – chúng nằm liền nhau trong danh sách. Gộp tất cả lại thành một khoảng mới, số đoạn bằng tổng cộng $+1$.

Cập nhật tích. Gọi $P$ là tích hiện tại (mod $p = 10^9+7$). Gộp các tập có kích thước $c_1, \ldots, c_t$ thành một tập kích thước $c = 1 + \sum c_j$: ta phải chia $P$ cho từng $c_j$ rồi nhân với $c$. Trong đồng dư không có phép chia, nhưng vì $p$ nguyên tố và $c_j < p$ nên có nghịch đảo modulo theo định lý Fermat nhỏ:

Nghịch đảo modulo (Fermat nhỏ)

$$c^{p-1} \equiv 1 \pmod p \;\Rightarrow\; c^{-1} \equiv c^{p-2} \pmod p, \qquad P_{\text{mới}} = P \cdot \prod_j c_j^{\,p-2} \cdot c \bmod p$$

Mỗi khoảng bị gộp thì biến mất, nên tổng số lần gộp trong cả quá trình không quá $N$. Em nhập các đoạn (mỗi đoạn "L-R", cách nhau dấu cách) rồi bấm Tiếp:

Các đoạn:

Ví dụ nhanh:

Cách 1DSU nối với mọi đoạn cũ – O(N²)

Dùng cấu trúc DSU (hợp nhất – tìm gốc): mỗi khi thêm đoạn $i$, duyệt mọi đoạn cũ $j < i$, nếu giao nhau ($L_j \le R_i$ và $L_i \le R_j$) thì hợp nhất hai tập. Sau đó duyệt mọi gốc để nhân kích thước các tập. Không cần nghịch đảo vì tính lại tích từ đầu.

C++▶ Chạy tay từng dòng codeCách 1: mỗi đoạn mới unite với mọi đoạn cũ giao nó, rồi nhân sz của mọi gốc.

Dữ liệu vào (stdin) – sửa thoải mái6 1 3 4 5 5 7 3 4 8 10 9 11

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Mỗi lần thêm duyệt $i$ đoạn cũ và $i$ gốc: tổng $O(N^2)$ – khoảng $4 \cdot 10^6$ bước khi $N = 2000$, nhưng $5 \cdot 10^9$ khi $N = 10^5$.
• Cách này đúng với mọi dữ liệu nên mình dùng nó để kiểm tra đáp án các test $N \le 2000$.

Không gian$O(N)$

Thời gian$O(N^2)$

Kết quả chạy thật (bộ test tự sinh): bản C++ đúng 16/40 test (Mức 1: 8/8, Mức 2: 0/12, Mức 3: 8/8, Mức 4: 0/12). Bản Python đúng 15/40 (Mức 1: 8/8, Mức 2: 0/12, Mức 3: 7/8, Mức 4: 0/12).

Cách 2map các khoảng rời nhau + nghịch đảo modulo – O(N log N)

Lưu các khoảng trong map<trái, (phải, số đoạn)>. Thêm $[l, r]$: tìm khoảng cuối cùng có đầu trái $\le r$ (bằng upper_bound(r) rồi lùi lại), lùi tiếp chừng nào khoảng còn có đầu phải $\ge l$; mỗi khoảng như vậy được gộp vào, xóa khỏi map, và tích được nhân với nghịch đảo kích thước của nó.

C++▶ Chạy tay từng dòng codeCách 2: map lưu các khoảng rời nhau; gộp các khoảng giao đoạn mới, chia tích bằng nghịch đảo Fermat.

Dữ liệu vào (stdin) – sửa thoải mái6 1 3 4 5 5 7 3 4 8 10 9 11

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Mỗi khoảng chỉ được thêm vào map một lần và xóa tối đa một lần, nên tổng số lần gộp $\le N$. Mỗi thao tác map và mỗi lần tính nghịch đảo tốn $O(\log)$: tổng $O(N \log N + N \log p)$.
• Kích thước tập luôn $\le 10^5 < p$ nên không bao giờ chia hết cho $p$ – nghịch đảo luôn tồn tại và tích không bao giờ bằng $0$.
• Điều kiện "không giao" là phải < l: hai đoạn chạm nhau tại một điểm (ví dụ $[3,4]$ và $[4,5]$) có giao nhau; còn $[1,3]$ và $[4,5]$ thì không.
• Bản Python dùng một danh sách đầu trái đã sắp xếp với bisect thay cho map, và gom các tập bị gộp để chỉ tính một lần nghịch đảo cho mỗi đoạn mới. Ở 3 test lớn nhiều đoạn ngắn (rất nhiều tập nhỏ) bản Python chạy sát 1 giây (1,0 – 1,1 giây CPU, chấm lại vẫn vậy) nên bị tính quá thời gian.

Không gian$O(N)$

Thời gian$O(N \log N)$

Kết quả chạy thật (bộ test tự sinh): bản C++ đúng 40/40 test, lâu nhất 0,169s; bản Python đúng 37/40, lâu nhất 0,835s.

Tổng kếtKết quả chạy thật trên bộ test tự sinh

Mình chấm cả 2 cách (C++ và Python) trên 40 test tự sinh với giới hạn 1 giây, đo thời gian CPU:

Lời giải	Mức 1 test 1–8	Mức 2 test 9–20	Mức 3 test 21–28	Mức 4 test 29–40	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	8/8	0/12	8/8	0/12	16/40	0,028s
Cách 1 – Python	8/8	0/12	7/8	0/12	15/40	0,928s
Cách 2 – C++	8/8	12/12	8/8	12/12	40/40	0,169s
Cách 2 – Python	8/8	12/12	8/8	9/12	37/40	0,835s

Ghi chú của mình: vì không có bộ test chính thức nên bảng trên dùng bộ test tự sinh (đáp án được kiểm chéo bằng 3 chương trình độc lập). Điểm mấu chốt của bài: "tập đoạn tốt" là các khoảng rời nhau, và khi tích cần "bớt" một thừa số thì nhân với nghịch đảo modulo $c^{p-2}$ chứ không chia thẳ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 😇